可以不可以在mergeSort函数中一次性申请aux数组 然后避免在调用_merge的时候不断申请小段内存

Question

我在一些算法书上看到的 merge 算法都是一次性申请aux[n] 复制原来arr数组 然后再后面调用函数的时候避免多次申请内存

这样做是否能够提高效率 牺牲空间成本 为了时间成本。

Answer 1

liuyubobobo 2016-11-08 03:19:31

赞。当然可以啦。在这个问题下：http://coding.imooc.com/learn/questiondetail/3044.html 我的第三点就是这个思路。

其实我们也可以很容易的做一次实验。以下代码是我针对100万的数据，在我的计算机上的实验结果。其中Merge Sort 1使用在merge时申请栈空间；Merge Sort2使用在merge外面开辟aux数组，再将aux数组传递给merge。两个MergeSort均未使用其他优化。

Merge Sort 1 : 0.451496 s
Merge Sort 2 : 0.444103 s

可以看到，Merge Sort 2确实快了。但是快的非常不明显。

为了避免是一次数据产生的偏差，我们可以使用多次测试取平均值的方式，来获得更加精准的具有统计意义的结果。下面的结果是针对两种方式，100万的数据量，各运行100次后，取平均值的时间。（这种方式其实在看算法的效果的时候非常常用！）

Merge Sort 1 Average Run Time: 0.394418 s
Merge Sort 2 Average Run Time: 0.361739 s

不要问我为什么一次实验运行结果是0.4+；而另一次实验是0.3+，我也不知道。现代计算机运行的过程中，有太多的干扰因素是我们无法排除的。但大体上，我们的算法是稳定在一个时间范围里的。（对100万的数据进行排序，在我的计算机上，在0.5s的范围内），同时，更重要的是，我们可以观察到趋势，将aux放在外面传给merge的归并排序确实会更快一些。

但是，你也发现了，其实快的并不多。我们可以简单分析一下。

1）将aux数组的空间开辟放在外面，虽然减少了在merge中反复开空间的消耗，但同时增加了传参的消耗。（不过堆内存的操作比传参耗费要更大）

2）现代编译器针对一些代码，会进行一些优化。解释器也是如此。代码运行时，对内存的使用也可能有内部优化。

所以，这步优化效果并不明显。不过我们还是可以清楚地看到，这样做确实是有效的：）

在课程中，由于aux只在merge的过程中使用，所以我就把aux的声明放在merge里了，便于理解。这样，每一个模块儿的任务很清晰，所有的变量，在哪里使用，就在哪里声明。但是，如果透彻理解了MergeSort的话，完全可以这样做。尤其是将MergeSort包装成类的时候，aux就可以大摇大摆的变成一个私有的成员变量啦。这样，就不需要在方法间传递这个参数了：）

我为了回答这个问题，实验的代码，可以参见：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/MergeSortImplementationComparision

• 提问者 hamphis #1

  非常感谢！

Answer 2

LeeDada 2016-11-07 15:07:20

我试验了两种方法，一种是一次性分配，一种是在merge的栈中临时分配。

最后的效果差不多了多少，但是整体来说一次性分配效率会高那么一点点。并且我个人认为在栈中临时分配的方法在大量数据的场合应用会有危险，很有可能会导致栈溢出。同时，代码的可能性也不是太好，需要做索引偏移。

上述就是我的意见，你可以自己实验一下嘛。

• liuyubobobo #1

  赞！有道理。不过索引的偏移其实可以通过修改代码避免。有兴趣可以思考一下：）

• 提问者 hamphis #2

  我当时说先提问了之后 再去实验的 结果和你差不多，因为传参的时候浪费了一些性能。如果包装成类的话，aux作为私有变量的时候，不需要传参的情况，效果还会有所提升。

Answer 3

22不小了 2017-03-20 21:39:57

这种精华回答让我觉得看别人的提问，也是一种提高