希尔排序最快的间隙序列？

发布于 2024-08-26 23:46:46 字数 387 浏览 9 评论 0原文

根据 Marcin Ciura 的希尔排序算法的最佳（最著名）增量序列 , shellsort 的最佳序列是 1, 4, 10, 23, 57, 132, 301, 701..., 但我怎样才能生成这样的序列呢？在 Marcin Ciura 的论文中，他说：

Knuth 序列和 Hibbard 序列相对来说比较糟糕，因为它们是由简单的线性递推定义。

但我发现大多数算法书籍都倾向于使用 Knuth 序列：k = 3k + 1，因为它很容易生成。生成 shellsort 序列的方法是什么？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

千寻… 2024-09-02 23:46:46

Ciura 的论文根据经验生成了序列——也就是说，他尝试了一系列组合，这是效果最好的一个。事实证明，生成最佳的希尔排序序列是很棘手的，并且该问题迄今为止一直难以分析。

最著名的增量是 Sedgewick 的增量，您可以在此处阅读（参见第 7 页）。

回复收藏 0 原文

新人笑 2024-09-02 23:46:46

如果您的数据集的大小有明确的上限，那么您可以对步骤序列进行硬编码。如果您的数据集可能在没有上限的情况下增长，您可能应该只担心通用性。

显示的序列似乎大致呈指数级数增长，尽管有一些怪癖。似乎大多数都是素数，但也有非素数。我没有看到明显的生成公式。

假设您必须处理任意大的集合，一个有效的问题是您是否需要强调最坏情况性能、平均情况性能或几乎排序性能。如果是后者，您可能会发现使用二分搜索进行插入步骤的普通插入排序可能比 shellsort 更好。如果您需要良好的最坏情况性能，那么塞奇威克序列似乎更受青睐。您提到的序列针对平均情况性能进行了优化，其中比较次数超过了移动次数。

回复收藏 0 原文

来世叙缘 2024-09-02 23:46:46

我不会羞于接受维基百科的 Shellsort 文章中给出的建议，

相对于平均比较次数，最知名的差距
序列为 1、4、10、23、57、132、301、701 等相似，有间隙
实验发现。超过 701 的最佳差距仍然未知，但很好
将上述序列扩展可得结果
递归公式 h_k = \lfloor 2.25 h_{k-1} \rfloor。
Tokuda 序列 [1, 4, 9, 20, 46, 103, ...]，由简单公式 h_k = \lceil h'_k 定义
\rceil，其中 h'k = 2.25h'k − 1 + 1，h'1 = 1，可推荐用于
实际应用。

从笔名来看，这篇 WP 文章似乎是 Marcin Ciura 亲自编辑的。

回复收藏 0 原文

清晰传感 2024-09-02 23:46:46

受上述答案的启发，我编写了一个程序来对各种 Shellsort 间隙序列进行基准测试。当然，结果并不能证明什么，但我仍然觉得它们很有趣。

我的程序是用 C++ 编写的，可以在 https://github.com/riordanmr/sortbench。我用它对 1000 个不同的随机生成的数组进行排序；每个数组都使用几个间隙序列中的每一个进行排序。数组大小均为 1,000,000 或 1,000,001 个元素。（我听说有传言说某些间隙序列对数组大小的均匀性/奇数很敏感。）这些数组包含 64 位指针，指向使用加密质量伪随机数生成器生成的字符串。因此，与比较的成本相比，交换元素的成本相对较低。

测试的序列是：

Ciura22：众所周知的 Ciura 序列，以 701 结尾，后续的空位通过将前一个空位乘以 2.20 获得。
Ciura225：与Ciura22类似，但乘数为2.25。
Ciura235：与Ciura22类似，但乘数为2.35。
Ciura225Odd：与 Ciura225 相同，但 701 之后的数字与 1 进行或运算以强制它们为奇数。
Lee21：Ying Wai Lee 的序列。请参阅 SHELLSORT 中的经验改进的 TOKUDA GAP 序列：https://arxiv.org/pdf/2112.11112.pdf
Jdaw1：jdaw1 上面描述的序列。
Tokuda92：https://oeis.org/A108870
Knuth73：Knuth 序列 (3^k-1)/2 。

以下是一次运行的结果（1000 个阵列）：

间隙序列	Recs/sec	Ave dev	Rel Perf
Ciura225Odd	1210516.1	0.463%	1.2453
Ciura225	1205463.9	0.639%	1.2401
Lee21	1204745.6	0.5%	1.2393
Ciura22	200786.5	0.517%	1.2353
Ciura235	1198675.2	0.498%	1.2331
德田92	1195739.4	0.444%	1.2301
Jdaw1	1184954.4	0.46%	1.2190
Knuth73	972096.6	0.856%	1.0000

Rel Perf 给出 1M 元素数组的每秒数组元素的相对性能。
正如您所看到的，对随机数组进行排序的时间非常一致，1000 个不同数组与平均值的平均偏差小于 1%。

就其价值而言，我的测试系统具有 Intel Xeon W-2150B CPU @ 3.00GHz，并且我使用 Xcode 14.3 进行编译。

我使用不同的 PRNG 种子运行了该程序几次，结果略有不同。然而，Ciura225Odd 始终是最快的（勉强），而 Knuth73 始终是最慢的。

Inspired by the above answers, I wrote a program to benchmark various Shellsort gap sequences. The results don't really prove anything, of course, but I still found them interesting.

My program, which is written in C++, can be found at https://github.com/riordanmr/sortbench. I used it to sort 1000 different randomly-generated arrays; each array was sorted using each of several gap sequences. The array sizes were all either 1,000,000 or 1,000,001 elements. (I had heard it rumored that some gap sequences were sensitive to array size evenness/oddness.) The arrays contained 64-bit pointers to strings generated with a cryptographic-quality pseudo-random number generator. Thus, the cost of swapping elements was relatively low compared to the cost of a comparison.

The sequences tested were:

Ciura22: The well-known Ciura sequence that ends with 701, with subsequent gaps obtained by multiplying the previous gap by 2.20.
Ciura225: Similar to Ciura22, but the multiplier is 2.25.
Ciura235: Similar to Ciura22, but the multiplier is 2.35.
Ciura225Odd: Same as Ciura225, but the numbers after 701 are ORed with 1 to force them to be odd.
Lee21: Ying Wai Lee's sequence. See EMPIRICALLY IMPROVED TOKUDA GAP SEQUENCE IN SHELLSORT: https://arxiv.org/pdf/2112.11112.pdf
Jdaw1: The sequence described above by jdaw1.
Tokuda92: https://oeis.org/A108870
Knuth73: Knuth’s sequence (3^k-1)/2.

Here are the results from one run (1000 arrays):

Gap sequence	Recs/sec	Ave dev	Rel Perf
Ciura225Odd	1210516.1	0.463%	1.2453
Ciura225	1205463.9	0.639%	1.2401
Lee21	1204745.6	0.5%	1.2393
Ciura22	1200786.5	0.517%	1.2353
Ciura235	1198675.2	0.498%	1.2331
Tokuda92	1195739.4	0.444%	1.2301
Jdaw1	1184954.4	0.46%	1.2190
Knuth73	972096.6	0.856%	1.0000

Rel Perf gives the relative performance in array elements per second, for a 1M element array.
As you can see, the time to sort a random array was pretty consistent, with an average deviation from the mean of less than 1% over 1000 different arrays.

For what it’s worth, my test system has an Intel Xeon W-2150B CPU @ 3.00GHz, and I compiled using Xcode 14.3.

I ran the program several times with different seeds to the PRNG, and the results varied slightly. However, Ciura225Odd was always the fastest (barely), and Knuth73 was always the slowest.

回复收藏 0 原文

記柔刀 2024-09-02 23:46:46

序列为 1、4、10、23、57、132、301、701、1750。对于 1750 之后的每个下一个数字，将前一个数字乘以 2.25 并向下舍入。

回复收藏 0 原文

情绪少女 2024-09-02 23:46:46

我发现这个序列与 Marcin Ciura 的序列类似：

1, 4, 9, 23, 57, 138, 326, 749, 1695, 3785, 8359, 18298, 39744, etc.

例如，Ciura 的序列是：

1, 4, 10, 23, 57, 132, 301, 701, 1750

这是素数的平均值。求素数均值的 Python 代码如下：

import numpy as np

def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
vectorized_isprime = np.vectorize(isprime)

a = np.arange(10000000)
primes = a[vectorized_isprime(a)]
#print(primes)
for i in range(2,20):
    print(primes[0:2**i].mean())

输出为：

4.25
9.625
23.8125
57.84375
138.953125
326.1015625
749.04296875
1695.60742188
3785.09082031
8359.52587891
18298.4733887
39744.887085
85764.6216431
184011.130096
392925.738174
835387.635033
1769455.40302
3735498.24225

序列中的间隙从 2.5 慢慢减小到 2。
也许这个关联将来可以改进 Shellsort。

I've found this sequence similar to Marcin Ciura's sequence:

1, 4, 9, 23, 57, 138, 326, 749, 1695, 3785, 8359, 18298, 39744, etc.

For example, Ciura's sequence is:

1, 4, 10, 23, 57, 132, 301, 701, 1750

This is a mean of prime numbers. Python code to find mean of prime numbers is here:

import numpy as np

def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
vectorized_isprime = np.vectorize(isprime)

a = np.arange(10000000)
primes = a[vectorized_isprime(a)]
#print(primes)
for i in range(2,20):
    print(primes[0:2**i].mean())

The output is:

4.25
9.625
23.8125
57.84375
138.953125
326.1015625
749.04296875
1695.60742188
3785.09082031
8359.52587891
18298.4733887
39744.887085
85764.6216431
184011.130096
392925.738174
835387.635033
1769455.40302
3735498.24225

The gap in the sequence is slowly decreasing from 2.5 to 2.
Maybe this association could improve the Shellsort in the future.

回复收藏 0 原文

夜吻♂芭芘 2024-09-02 23:46:46

我讨论了这个问题

中间我写

shellsort 的一个令人讨厌的副作用是，当使用一组随机
n 个条目的组合（以节省处理/评估时间）进行测试
间隙，您最终可能会得到 n 个条目的最佳间隙，或者
您的一组组合的最佳间隙 - 很可能是后者。

问题在于测试所提出的差距，以便得出有效的结论。显然，测试所有 n 的差距！一组 n 个唯一值可以表示为不可行的排序。例如，以这种方式测试 n=16，意味着必须对 n 值的 20,922,789,888,000 个不同组合进行排序，以确定准确的平均值、最坏情况和逆排序情况 - 只是为了测试一组间隙，而该组间隙可能不是最好的。对于 n=16，可能有 2^(16-2) 组间隙，第一个是 {1}，最后一个是 {15,14,13,12,11,10,9,8,7,6,5,4 ,3,2,1}。

为了说明使用随机组合如何可能给出不正确的结果，假设 n=3，可以假设六种不同的排序 012、021、102、120、201 和 210。您生成一组两个随机序列来测试两个可能的间隙集，{1 }和{2,1}。假设这些序列是 021 和 201。对于 {1}，021 可以通过三个比较（02、21 和 01）排序，201 可以通过（20、21、01）排序，总共有 6 个比较，除以二瞧，平均值为 3，最坏情况为 3。使用 {2,1} 可以得到 021 的 (01, 02, 21 和 01)，得到 201 的 (21, 10 和 12)。与最坏情况的七次比较4，平均3.5。 {1] 的实际平均和最坏情况分别为 8/3 和 3。对于 {2,1}，值为 10/3 和 4。这两种情况的平均值都太高，最坏的情况是正确的。如果 012 是案例之一 {1}，平均分将是 2.5 - 太低了。

现在将其扩展到寻找 n=16 的一组随机序列，这样与其他组相比，没有一组测试的间隙会受到青睐，并且结果接近（或等于）真实值，同时将处理保持在最低限度。能做到吗？可能吧。毕竟，一切皆有可能——但有可能吗？我认为对于这个问题，随机是错误的方法。根据某些系统选择序列可能不会那么糟糕，甚至可能会更好。

I discussed this question here yesterday including the gap sequences I have found work best given a specific (low) n.

In the middle I write

A nasty side-effect of shellsort is that when using a set of random
combinations of n entries (to save processing/evaluation time) to test
gaps you may end up with either the best gaps for n entries or the
best gaps for your set of combinations - most likely the latter.

The problem lies in testing the proposed gaps such that valid conclusions can be drawn. Obviously, testing the gaps against all n! orderings that a set of n unique values can be expressed as is unfeasible. Testing in this manner for n=16, for example, means that 20,922,789,888,000 different combinations of n values must be sorted to determine the exact average, worst and reverse-sorted cases - just to test one set of gaps and that set might not be the best. 2^(16-2) sets of gaps are possible for n=16, the first being {1} and the last {15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}.

To illustrate how using random combinations might give incorrect results assume n=3 that can assume six different orderings 012, 021, 102, 120, 201 and 210. You produce a set of two random sequences to test the two possible gap sets, {1} and {2,1}. Assume that these sequences turn out to be 021 and 201. for {1} 021 can be sorted with three comparisons (02, 21 and 01) and 201 with (20, 21, 01) giving a total of six comparisons, divide by two and voilà, an average of 3 and a worst case of 3. Using {2,1} gives (01, 02, 21 and 01) for 021 and (21, 10 and 12) for 201. Seven comparisons with a worst case of 4 and an average of 3.5. The actual average and worst case for {1] is 8/3 and 3, respectively. For {2,1} the values are 10/3 and 4. The averages were too high in both cases and the worst cases were correct. Had 012 been one of the cases {1} would have given a 2.5 average - too low.

Now extend this to finding a set of random sequences for n=16 such that no set of gaps tested will be favored in comparison with the others and the result close (or equal) to the true values, all the while keeping processing to a minimum. Can it be done? Possibly. After all, everything is possible - but is it probable? I think that for this problem random is the wrong approach. Selecting the sequences according to some system may be less bad and might even be good.

回复收藏 0 原文

陌路终见情 2024-09-02 23:46:46

塞奇威克观察到互质性是好的。这听起来是正确的：如果存在单独的“流”，在间隙很小之前没有太多交叉比较，并且一个流包含大部分小元素，一个流大部分包含大元素，那么小间隙可能需要将元素移动很远。互质性最大化了跨流比较。

Gonnet 和 Baeza-Yates 建议增长约 2.2 倍；德田2.25。众所周知，如果在 2⅕ 和 2⁄4 之间存在一个数学常数，那么它必须恰好是 √5 ≈ 2.236。

因此从 {1, 3} 开始，然后每个后续都是最接近前一个·√5 的整数，该整数与除 1 之外的所有前一个互质。这个序列可以预先计算并嵌入到代码中。接下来的值高达 2⁶⁴ ≈ 18 quintillion。

<代码>{1、3、7、16、37、83、187、419、937、2099、4693、10499、23479、52501、117391、262495、586961、1312481、2934793、 14673961、32811973、73369801、 164059859、366848983、820299269、1834244921、4101496331、9171224603、20507481647、45856123009、102537408229、229280615033、 512687041133、1146403075157、2563435205663、5732015375783、12817176028331、28660076878933、64085880141667、143300384394667、 320429400708323、716501921973329、1602147003541613、3582509609866643、8010735017708063、17912548049333207、4005367508854030 3、 89562740246666023、200268375442701509、447813701233330109、1001341877213507537、2239068506166650537、5006709386067537661、 11195342530833252689}

（显然，忽略那些会溢出相关数组索引类型的内容。因此，如果这是一个有符号的 long long，则忽略最后一个。）

平均而言，这些有约 1.96 个不同质因数和约 2.07 个非不同质因数； 19/55 ≈ 35% 是质数；除三个之外，其余所有都是无平方的（2⁴, 13·19² = 4693, 3291992692409·23³ ≈ 4.0·10^⁶）。

我欢迎对这个序列进行正式推理。

† 这个“众所周知的……必须”有点恶作剧。选择 ∉ℚ 保证最接近的互质数不能是平局，但分母为奇数的有理数也能达到同样的效果。我喜欢 √5 的简单性，尽管其他可能性包括 e^⅘、11^⅓、π/√2 和 √π 除以 Chow-Robbins 常数。简单有利于√5。

Sedgewick observes that coprimality is good. This rings true: if there are separate ‘streams’ not much cross-compared until the gap is small, and one stream contains mostly smalls and one mostly larges, then the small gap might need to move elements far. Coprimality maximises cross-stream comparison.

Gonnet and Baeza-Yates advise growth by a factor of about 2.2; Tokuda by 2.25. It is well known that if there is a mathematical constant between 2⅕ and 2¼ then it must† be precisely √5 ≈ 2.236.

So start {1, 3}, and then each subsequent is the integer closest to previous·√5 that is coprime to all previous except 1. This sequence can be pre-calculated and embedded in code. There follow the values up to 2⁶⁴ ≈ eighteen quintillion.

{1, 3, 7, 16, 37, 83, 187, 419, 937, 2099, 4693, 10499, 23479, 52501, 117391, 262495, 586961, 1312481, 2934793, 6562397, 14673961, 32811973, 73369801, 164059859, 366848983, 820299269, 1834244921, 4101496331, 9171224603, 20507481647, 45856123009, 102537408229, 229280615033, 512687041133, 1146403075157, 2563435205663, 5732015375783, 12817176028331, 28660076878933, 64085880141667, 143300384394667, 320429400708323, 716501921973329, 1602147003541613, 3582509609866643, 8010735017708063, 17912548049333207, 40053675088540303, 89562740246666023, 200268375442701509, 447813701233330109, 1001341877213507537, 2239068506166650537, 5006709386067537661, 11195342530833252689}

(Obviously, omit those that would overflow the relevant array index type. So if that is a signed long long, omit the last.)

On average these have ≈1.96 distinct prime factors and ≈2.07 non-distinct prime factors; 19/55 ≈ 35% are prime; and all but three are square-free (2⁴, 13·19² = 4693, 3291992692409·23³ ≈ 4.0·10¹⁶).

I would welcome formal reasoning about this sequence.

† There’s a little mischief in this “well known … must”. Choosing ∉ℚ guarantees that the closest number that is coprime cannot be a tie, but rational with odd denominator would achieve same. And I like the simplicity of √5, though other possibilities include e^⅘, 11^⅓, π/√2, and √π divided by the Chow-Robbins constant. Simplicity favours √5.

回复收藏 0 原文

桃扇骨 2024-09-02 23:46:46

有关 jdaw1 帖子的更多信息：

Gonnet 和 Baeza-Yates 建议增长约 2.2 倍；德田2.25。众所周知，如果在 2⅕ 和 2¼ 之间存在一个数学常数，那么它一定†恰好是 √5 ≈ 2.236。

众所周知，√5 * √5 是 5，所以我认为其他所有指数都应该增加五倍。因此，第一个索引是 1 插入排序，第二个索引是 3，然后每个索引的因子都是 5。接下来的值高达 2⁶⁴ ≈ 18 quintillion。

{1, 3,, 15,, 75,, 375,, 1 875,, 9 375,, 46 875,, 234 375,, 1 171 875,, 5 859 375,, 29 296 875,, 146 484 375, , 732 421 875,, 3 662 109 375,, 18 310 546 875,, 91 552 734 375,, 457 763 671 875,, 2 288 818 359 375,, 11 444 091 796 875 ,, 57 220 458 984 375, , 286 102 294 921 875,, 1 430 511 474 609 375,, 7 152 557 373 046 875,, 35 762 786 865 234 375,, 178 813 934 326 171 875,, 894 069 671 630 859 375,, 4 470 348 358 154 296 875,}

间隙中的值可以简单地计算出来，方法是取之前的值并乘以 √5 四舍五入到整数，得到结果数组（使用 2.2360679775 * 5 ^ n * 3）：

{1, 3, 7, 15, 34, 75, 168, 375, 839, 1 875, 4 193, 9 375, 20 963, 46 875, 104 816, 234 375, 524 078, 1 171 875, 2 620 392, 5 859 375、 13 101 961、29 296 875、65 509 804、146 484 375、327 549 020、732 421 875、1 637 745 101、3 662 109 375、8 188 725 504、 310 546 875, 40 943 627 518, 91 552 734 375、204718137589、457763671875、1023590687943、2288818359 375, 5 117 953 439 713, 11 444 ;091796 875、25 589 767 198 563、57 220 458 984 375、127 948 835 992 813、286、102、294、921、875、639、744 ;179964 066、1 430 511 474 609 375、3 198 720 899 820 328、 557 373 046875, 15993 604 499 ;101 639, 35 762 786 865 234 375, 79 968 022 495 508 194, 178 813 934 326 171 875, 399 840 112 477 540 ;970、894 069 671 630 859 375、1 999 200 562 387 704 849 4 470 348 358 154 296 875, 9 996 002 811 ;938 524 246}

（显然，忽略那些会溢出相关数组索引类型的内容。因此，如果这是一个有符号的 long long，则忽略最后一个。）

More information regarding jdaw1's post:

Gonnet and Baeza-Yates advise growth by a factor of about 2.2; Tokuda by 2.25. It is well known that if there is a mathematical constant between 2⅕ and 2¼ then it must† be precisely √5 ≈ 2.236.

It is known that √5 * √5 is 5 so I think every other index should increase by a factor of five. So first index being 1 insertion sort, second being 3 then each other subsequent is of the factor 5. There follow the values up to 2⁶⁴ ≈ eighteen quintillion.

{1, 3,, 15,, 75,, 375,, 1 875,, 9 375,, 46 875,, 234 375,, 1 171 875,, 5 859 375,, 29 296 875,, 146 484 375,, 732 421 875,, 3 662 109 375,, 18 310 546 875,, 91 552 734 375,, 457 763 671 875,, 2 288 818 359 375,, 11 444 091 796 875,, 57 220 458 984 375,, 286 102 294 921 875,, 1 430 511 474 609 375,, 7 152 557 373 046 875,, 35 762 786 865 234 375,, 178 813 934 326 171 875,, 894 069 671 630 859 375,, 4 470 348 358 154 296 875,}

The values in the gaps can simply be calculated by taking the value before and multiply by √5 rounding to whole numbers giving the resulting array (using 2.2360679775 * 5 ^ n * 3):

{1, 3, 7, 15, 34, 75, 168, 375, 839, 1 875, 4 193, 9 375, 20 963, 46 875, 104 816, 234 375, 524 078, 1 171 875, 2 620 392, 5 859 375, 13 101 961, 29 296 875, 65 509 804, 146 484 375, 327 549 020, 732 421 875, 1 637 745 101, 3 662 109 375, 8 188 725 504, 18 310 546 875, 40 943 627 518, 91 552 734 375, 204 718 137 589, 457 763 671 875, 1 023 590 687 943, 2 288 818 359 375, 5 117 953 439 713, 11 444 091 796 875, 25 589 767 198 563, 57 220 458 984 375, 127 948 835 992 813, 286 102 294 921 875, 639 744 179 964 066, 1 430 511 474 609 375, 3 198 720 899 820 328, 7 152 557 373 046 875, 15 993 604 499 101 639, 35 762 786 865 234 375, 79 968 022 495 508 194, 178 813 934 326 171 875, 399 840 112 477 540 970, 894 069 671 630 859 375, 1 999 200 562 387 704 849, 4 470 348 358 154 296 875, 9 996 002 811 938 524 246}