c# - Shellsort，2.48^(k-1) vs Tokuda 的序列

Question

简介

Shellsort 是我不久前遇到的一种有趣的排序算法。最神奇的是，不同的空位序列可以显着提高算法的速度。我读了一些书(没有广泛阅读)，似乎 Tokuda 的序列被推荐用于实际应用。

另一个有趣的地方是比率2.20~2.25的序列往往效率更高。所以我做了一个小的搜索，考虑从 2.20 到 2.50 的比率序列，并尝试搜索哪个比率可以平均表现良好。我遇到了这个比率:2.48，在许多不同的试验中似乎平均表现良好。

然后，我想出了序列生成器:2.48^k-1(我们称它为 248 序列)并尝试将其与 Tokuda 的序列进行比较。事实证明，它们的速度平均相等。 248序列倾向于使用稍微多一些的比较。

基准方法

• 我没有使用毫秒作为度量标准，而是使用比较次数和交换次数。
• 我对以下数组大小(50,000；100,000；200,000；300,000；500,000；1,000,000)分别进行了 100 次试验，并跟踪它们的比较次数和交换次数。
• 以下是我的数据(here in CSV format)。
• 完整代码:http://pastebin.com/pm7Akpqh

问题

我知道我可能是错的，这就是为什么我来这里寻求更有经验的程序员的更多意见。如果您不明白问题，这里是我的简短问题:

• 2.48^k-1 和 Tokuda 的序列一样好吗？
• 如果它和 Tokuda 的序列一样好，使用它是否更实用，因为 2.48^k-1 序列比 Tokuda 的序列更容易生成。

---

248 Sequence:  ROUNDUP ( 2.48(k-1) )  eg: 1, 3, 7, 16, 38, 94, 233, 577, 1431, 3549, 8801, 21826, ...Tokuda's Sequence  ROUNDUP ( (9k - 4k) / (5 * 4k - 1) )  eg: 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, ...

---

As @woolstar suggested me to also test with edge cases such as reversed and sorted. As expectedly, 248 sequence is faster in edge cases because 248 sequence gap is larger so it moves the inverse faster.

---

Shellsort Implementation

public static int compare = 0;
public static int swap = 0;

public static bool greaterthan(int a, int b) {
    compare++;
    return a > b;
}

public static int shellsort(int[] a, int[] gaps) {
    // For keeping track of number of swap and comparison
    compare = 0;
    swap = 0;

    int temp, gap, i, j;

    // Finding a gap that is smaller than the length of the array
    int gap_index = gaps.Length - 1;
    while (gaps[gap_index] > a.Length) gap_index--;

    while (gap_index >= 0) {

        // h-sorting
        gap = gaps[gap_index];
        for (i = gap; i < a.Length; i++) {
            temp = a[i];
            for(j = i; (j >= gap) && (greaterthan(a[j - gap], temp)); j -= gap) {
                a[j] = a[j - gap];
            }

            // swapping
            a[j] = temp;
            swap++;
        }

        gap_index--;
    }

    return compare;
}

Answer 1

根据 this reserach : (Ciura，Marcin(2001 年)“Shellsort 平均案例的最佳增量”。在 Freiwalds，Rusins。第 13 届国际计算理论基础研讨会论文集。伦敦:Springer-Verlag。第 106-117 页) 对于大小小于 10⁸ 的数组，shell 排序中的主要操作应该是比较操作，而不是交换操作:

Knuth’s discussion assumes that the running time can be approximated as 9×number of moves, while Figures 3 and 4 show that for each sequence the number of key comparisons is a better measure of the running time than the number of moves. The asymptotic ratio of 9 cycles per move is not too precise for N ≤ 10⁸, and, if some hypothetical sequence makes Θ(NlogN) moves, it is never attained. Analogous plots for other computer architectures would lead to the same conclusion.

Treating moves as the dominant operation leads to mistaken conclusions about the optimal sequences.

在这种情况下，您的问题的答案是否定的:248 序列更糟糕，因为它使用了更多的比较。您还可以考虑将您的序列与本文中介绍的 Ciura 序列进行比较，因为这项研究似乎证明它比 Tokuda 的序列更好。