Mergesort - 自上而下快于自上而下吗？

Question

我一直在阅读Sedgewick和Wayne的"Algorithms,4th Ed",并且我一直在实现JavaScript中讨论的算法.

我最近采用了书中提供的mergesort示例来比较自上而下和自下而上的方法......但我发现自下而上的运行速度更快(我认为).在我的博客上查看我的分析.- http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/

我还没有找到任何讨论说一个mergesort方法应该比另一个快.我的实施(或分析)是否存在缺陷？

注意:我的分析测量算法的迭代循环,而不是严格的数组比较/移动.也许这有缺陷或无关紧要？

编辑:我的分析实际上没有时间速度,所以我关于它运行"更快"的声明有点误导.我通过递归方法(自上而下)和for循环(自下而上)跟踪"迭代" - 并且自下而上似乎使用更少的迭代.

Answer 1

我还没有找到任何讨论说一个mergesort方法应该比另一个快.

自上而下和自上而下的合并类别以及其他变体在90年代进行了很好的研究.简而言之,如果您将成本测量为单个密钥的比较次数,则最佳成本相同(〜(n lg n)/ 2),自上而下的最差成本低于或等于最差成本自下而上的情况(但两者都是n n n)和自上而下的平均成本低于或等于自下而上的平均情况(但都是〜n lg n),其中"lg n"是二进制对数.差异源于线性项.当然,如果n = 2 ^ p,则这两个变体实际上完全相同.这意味着,从比较的角度来看,自上而下总是好于自下而上.此外,已经证明自上而下合并排序的"半"分裂策略是最优的.研究论文来自Flajolet,Golin,Panny,Prodinger,Chen,Hwang和Sedgewick.

以下是我在Erlang中出版的"纯功能程序设计与分析(英国大学出版物)" 一书中提到的内容:

tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T)           -> T.

cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S,    T,      U) -> mrg(tms(S),tms(T)).

mrg(     [],    T)            -> T;
mrg(      S,   [])            -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg(  [X|S],    T)            -> [X|mrg(S,T)].

请注意,这不是一个稳定的排序.此外,在Erlang(和OCaml)中,如果要节省内存,则需要在模式中使用别名(ALIAS = ...).这里的技巧是在不知道其长度的情况下找到列表的中间部分.这是由cutr/3完成的,它处理两个指向输入列表的指针:一个递增一个而另一个递增两个,所以当第二个到达结尾时,第一个指向中间.(我是从Olivier Danvy的一篇论文中学到的.)这样,你不需要跟踪长度,也不需要复制列表后半部分的单元格,所以你只需要(1/2) )n lg n额外空间,相对于n lg n.这不是众所周知的.

人们常说自下而上的变体更适合函数式语言或链表(Knuth,Panny,Prodinger),但我不认为这是真的.

由于缺乏关于合并类型的讨论,我对你感到困惑,所以我做了自己的研究并写了一篇关于它的大篇章.我目前正在准备一个新版本,其中有更多关于合并类型的材料.

顺便说一下,还有其他变种:队列合并排序和在线合并排序(我在书中讨论后者).

[编辑:由于成本的衡量标准是比较次数,因此选择数组与链表之间没有区别.当然,如果您使用链接列表实现自上而下的变体,您必须聪明,因为您不一定知道键的数量,但每次都需要遍历至少一半的键,并且重新分配,总共(1/2)n lg n个细胞(如果你聪明的话).与链接列表的自下而上合并排序实际上需要更多额外的内存,n lg n + n个单元格.因此,即使使用链接列表,自上而下的变体也是最佳选择.就程序的长度而言,您的里程可能会有所不同,但在功能语言中,如果不需要稳定性,自上而下的合并排序可以比自下而上更短.有些论文讨论了合并排序的实现问题,例如就地(您需要数组)或稳定性等.例如,Katajainen和Larsson Traff(1997)对Mergesort 程序的细致分析.

Answer 2

我在2012年8月版本课程的课程论坛上提出了同样的问题.普林斯顿教授Kevin Wayne回答说,在很多情况下,递归比迭代更快,因为缓存提高了性能.

所以我当时得到的简短答案是,由于缓存原因,自顶向下合并排序将比自下而上合并排序更快.

请注意,该课程是用Java编程语言(而不是Javascript)教授的.

Answer 3

如果更快意味着更少的“迭代”，那么是的。如果您想知道执行时间。

原因是这 21,513 次迭代中有一些比 22,527 次迭代做得更多。

从源头来看，图中的一些叶节点似乎被排序在一起，而不是单独排序，从而导致更少的合并和排序，但它们花费的时间更长。