java - 为什么递归 MergeSort 比迭代 MergeSort 更快？

Question

我刚刚实现了这两种算法，当我绘制结果时我很惊讶!递归实现显然比迭代实现更快。 之后，我将插入排序与两者相结合，结果是一样的。

在讲座中，我们经常看到递归比阶乘计算中的迭代慢，但在这里似乎并非如此。我很确定我的代码是正确的。 这种行为的解释是什么？它看起来像 java (10) 在递归模式下自动实现多线程，因为当我显示小动画时，插入排序与合并操作并行工作。

如果这些代码还不足以理解这里是我的github:Github

编辑重新加载 正如评论中所说，我应该比较相似的东西，所以现在合并方法在迭代和递归中是相同的。

private void merge(ArrayToSort<T> array, T[] sub_array,
                   int min, int mid, int max) {
    //we make a copy of the array.
    if (max + 1 - min >= 0) System.arraycopy(array.array, min, sub_array, min, max + 1 - min);

    int i = min, j = mid + 1;

    for (var k = min; k <= max; k++) {

        if (i > mid) {
            array.array[k] = sub_array[j++];
        } else if (j > max) {
            array.array[k] = sub_array[i++];
        } else if (sub_array[j].compareTo(sub_array[i]) < 0) {
            array.array[k] = sub_array[j++];
        } else {
            array.array[k] = sub_array[i++];
        }
    }
}

递归排序:

public void Sort(ArrayToSort<T> array) {
    T sub[] = (T[]) new Comparable[array.Length];
    sort(array, sub, 0, array.Length - 1);
}

private InsertionSort<T> insertionSort = new InsertionSort<>();
private void sort(ArrayToSort<T> array, T[] sub_array, int min, int max) {
    if (max <= min) return;
    if (max <= min + 8 - 1) {
        insertionSort.Sort(array, min, max);
        return;
    }
    var mid = min + (max - min) / 2;
    sort(array, sub_array, min, mid);
    sort(array, sub_array, mid + 1, max);
    merge(array, sub_array, min, mid, max);

}

排序迭代:

private InsertionSort<T> insertionSort = new InsertionSort<>();
public void Sort(ArrayToSort<T> array) {

    int length = array.Length;
    int maxIndex = length - 1;

    T temp[] = (T[]) new Comparable[length];

    for (int i = 0; i < maxIndex; i += 8) {
        insertionSort.Sort(array, i, Integer.min(i + 8 - 1, maxIndex));
    }

    System.arraycopy(array.array, 0, temp, 0, length);

    for (int m = 8; m <= maxIndex; m = 2 * m) {
        for (int i = 0; i < maxIndex; i += 2 * m) {

            merge(array, temp, i, i + m - 1,
                    Integer.min(i + 2 * m - 1, maxIndex));
        }
    }
}

在新图中，我们可以看到现在差异是成比例的 (à un facteur près)。如果有人有更多想法...非常感谢:)
新*新剧情

这是我的(实际上是老师的)绘图方法:

for (int i = 0; i < nbSteps; i++) {
    int N = startingCount + countIncrement * i;
    for (ISortingAlgorithm<Integer> algo : algorithms) {

        long time = 0;
        for (int j = 0; j < folds; j++) {
            ArrayToSort<Integer> toSort = new ArrayToSort<>(
                    ArrayToSort.CreateRandomIntegerArray(N, Integer.MAX_VALUE, (int) System.nanoTime())
            );
            long startTime = System.currentTimeMillis();
            algo.Sort(toSort);
            long endTime = System.currentTimeMillis();
            time += (endTime - startTime);
            assert toSort.isSorted();
        }
        stringBuilder.append(N + ", " + (time / folds) + ", " + algo.Name() + "\n");
        System.out.println(N + ", " + (time / folds) + ", " + algo.Name());
    }

}

Answer 1

我认为我没有答案，因为我没有尝试您的代码。 我会给你想法:

a) CPU 有 L1 缓存和指令预取。当所有的排序都完成后，递归版本可能有更好的引用局部性，并且它在弹出所有帧的同时完成一堆合并(出于其他 cpu 优化原因)

b) 与此同时，JIT 编译器对递归做了疯狂的事情，特别是由于尾递归和内联。我建议您只是为了好玩而尝试不使用 JIT 编译器。也可能想尝试更改 JIT 编译的阈值，以便更快地进行 JIT 编译以最大限度地减少预热时间。

c) system.arraycopy 是一种本地方法，尽管经过了优化，但它应该有开销。

d) 迭代版本似乎在循环中有更多的算法。

e) 这是对微基准测试的尝试。您需要排除 GC 并让测试运行数十次甚至数百次。阅读 JMH。还可以尝试不同的 GC 和 -Xmx。