对内存操作优化后, 速度更慢

public static <E extends Comparable<E>> void sort4(E[] arr) {
    E[] temp = Arrays.copyOf(arr, arr.length);
    sort4(arr, 0, arr.length - 1, temp);
}
 
private static <E extends Comparable<E>> void sort4(E[] arr, int l, int r, E[] temp) {
    if (l >= r) return;
 
    int mid = l + (r - l) / 2;
    sort4(arr, l, mid, temp);
    sort4(arr, mid + 1, r, temp);
 
    if (arr[mid].compareTo(arr[mid + 1]) > 0)
        merge2(arr, l, mid, r, temp);
}
 
// 合并两个有序区间arr[l..mid]和arr[mid+1...r]
private static <E extends Comparable<E>> void merge2(E[] arr, int l, int mid, int r, E[] temp) {
 
    System.arraycopy(arr, l, temp, l, r - l + 1);
 
    int i = l, j = mid + 1;
    // 每轮循环为arr[k]赋值
    for (int k = l; k <= r; k ++) {
        if (i > mid) {
            break;
            // 或者直接break,因为右侧的数组本身就是有序的
        } else if (j > r) {
            arr[k] = temp[i];
            i ++;
        } else if (temp[i].compareTo(temp[j]) <= 0) {
            arr[k] = temp[i];
            i ++;
        } else {
            arr[k] = temp[j];
            j ++;
        }
    }
}

MergeSort2, n = 5000000: 1.529831 s

MergeSort4, n = 5000000: 1.555577 s

MergeSort2是判断是否需要merge的优化, MergeSort4不仅判断是否需要进行merge操作, 还对内存操作进行了优化, 为什么时间更长呢?

越学越喜欢越学 2022-12-20

源自：归并排序法 2-3 归并排序法的内存操作优化

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2022-12-21 02:01:28

如果我没有理解错的话，你的意思是在你的环境下，课程的这个代码离得 MergeSort 和 MergeSort2 没有性能优化的效果。（MergeSort2 经过了内存优化；MergeSort 没有。）

https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/10-More-about-MergeSort/03-MergeSort-Advanced-Optimization/src/MergeSort.java

虽然这种“常数级”的性能优化会受机器的硬件配置，操作系统，你所使用的编译器版本等等因素的影响，但整体这个在大数据量下没有效果是不应该的。

请尝试在你的环境下运行上面的课程代码，看是否同样如此？如果不是的话，请检查你的代码哪里有问题。（你现在给我的代码只有 sort4 的代码，没有 sort2 的代码。但 sort4 的代码在调用 merge2？道理上是否做这步内存优化，调用的 merge 的逻辑是有不同的，请检查是否有类似的调用错误。）

继续加油！：）

收起回答

越学越喜欢越学提问者 #1

老师, 您理解的没错. 就是sort4是在sort2的基础上, 又优化了内存操作. 我仔细检查了一下, 只有一个地方和您给的代码不同: 左侧数组遍历结束后, i > mid, 我直接break了. 我根据您的代码, 在i > mid时, 令arr[k] = temp[j], j ++. 把两个merge的这一步操作都改过来以后, 确实可以看到0.1s的优化. 请问这是什么原因呢?

2022-12-21 11:16:43
liuyubobobo 回复提问者越学越喜欢越学 #2

该不该 break 不应该对性能优化的结果有影响。你给出的数据表明你的性能优化在你的环境下没有表现出来。(500w 的数据 0.1s 或者 0.03s 的差距近乎等于没差，很难说是算法的影响还是操作系统等运行环境的影响。)我只能猜测你的运行环境比较好（机器配置比较高），导致性能优化结果不明显。

请尝试使用 1000w 的数据测试，如果还是类似不明显的情况，尝试使用 2000w 的数据测试，以此类推。道理上数据规模达到一定程度，一定能看到显著的优化。如果看不到，请下载我的课程代码在你的环境下用更大规模数据测试，看是否看到变化？

2022-12-21 11:33:06
越学越喜欢越学提问者回复 liuyubobobo #3

用2000w的数据测试,能看到1s多的优化了. 谢谢老师答疑!

2022-12-21 13:23:23