为什么Haskell使用mergesort而不是quicksort？

Question

在Wikibooks的Haskell中,有以下声明:

Data.List提供用于排序列表的排序功能.它不使用quicksort; 相反,它使用称为mergesort的算法的有效实现.

Haskell使用mergesort而不是quicksort的根本原因是什么？Quicksort通常具有更好的实际性能,但在这种情况下可能不是.我认为快速排序的现场好处很难(不可能？)与Haskell列表有关.

关于so​​ftwareengineering.SE有一个相关的问题,但实际上并不是为什么使用 mergesort.

我自己实现了两种类型的分析.Mergesort是优越的(大约是2 ^ 20个元素列表的两倍),但我不确定我的quicksort实现是否最佳.

编辑:这是我的mergesort和quicksort的实现:

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
    where size = div (length l) 2
          (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge first@(l:ls) second@(v:vs)
    | l < v = l : merge ls second
    | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
    where pivotIndex = div (length l) 2
          pivot = l !! pivotIndex
          [less, greater] = foldl addElem [[], []] $ enumerate l
          addElem [less, greater] (index, elem)
            | index == pivotIndex = [less, greater]
            | elem < pivot = [elem:less, greater]
            | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

编辑2 3:我被要求为我的实施提供时间安排Data.List.按照@Will Ness的建议,我用标志编译了这个要点,每次-O2更改提供的排序main,然后执行它+RTS -s.排序列表是一个廉价创建的伪随机[Int]列表,包含2 ^ 20个元素.结果如下:

• Data.List.sort:0.171s
• mergesort:1.092s(比慢6倍Data.List.sort)
• quicksort:1.152s(比慢7倍Data.List.sort)

Answer 1

在命令式语言中,Quicksort通过改变数组来就地执行.正如您在代码示例中演示的那样,您可以通过构建单链接列表来使Quicksort适应纯函数语言(如Haskell),但这并不是那么快.

另一方面,Mergesort不是就地算法:简单的命令式实现将合并的数据复制到不同的分配.这更适合Haskell,无论如何它必须复制数据.

让我们退后一步:Quicksort的性能优势是"绝杀" - 几十年前在与我们今天使用的机器大不相同的机器上建立的声誉.即使你使用相同的语言,这种传说也需要不时地重新检查,因为实地的事实可能会改变.我读到的关于这个主题的最后一篇基准测试论文让Quicksort仍处于领先地位,但它在Mergesort上的领先优势很小,即使在C/C++中也是如此.

Mergesort还有其他优点:它不需要调整以避免Quicksort的O(n ^ 2)最坏情况,并且它自然是稳定的.因此,如果由于其他因素而导致性能差异缩小,Mergesort是一个明显的选择.

Answer 2

我认为@greestorm的答案几乎就在鼻子上,但这里有关于GHC排序功能历史的更多信息.

在源代码中Data.OldList,你可以找到实现的sort,并为自己验证它是一个合并排序.在该文件中的定义下面是以下注释:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it's performance...

因此,最初使用了一个功能性快速排序(功能qsort仍在那里,但已被注释掉).Ian的基准测试显示,他的mergesort在"随机列表"案例中与quicksort竞争,并且在已经排序的数据的情况下大大超过了它.之后,根据该文件中的其他评论,Ian的版本被另一个实现速度提高了两倍的实现所取代.

原始的主要问题qsort是它没有使用随机数据.相反,它转向列表中的第一个值.这显然是非常糟糕的,因为它意味着对于排序(或接近排序)的输入,性能将是最坏情况(或接近).不幸的是,从"第一个枢轴"转换到替代方案(随机,或者 - 在实施中 - 在"中间"的某个地方),存在一些挑战.在没有副作用的函数式语言中,管理伪随机输入有点问题,但是假设你解决了这个问题(可能是通过在你的sort函数中构建一个随机数生成器).您仍然遇到的问题是,在对不可变链接列表进行排序时,查找任意数据透视表然后根据它进行分区将涉及多个列表遍历和子列表副本.

我认为实现快速排序所谓好处的唯一方法是将列表写入向量,对其进行排序(并牺牲排序稳定性),然后将其写回列表.我不认为这可能是一场全面的胜利.另一方面,如果您已经在向量中有数据,那么就地快速排序肯定是一个合理的选择.

Answer 3

在单链表上,mergesort可以在适当的位置完成.更重要的是,天真的实现扫描超过列表的一半以获得第二个子列表的开始,但第二个子列表的开始作为排序第一个子列表的副作用而不需要额外的扫描.快速排序已经超越mergesort的一件事是缓存一致性.Quicksort使用内存中彼此接近的元素.一旦间接元素进入它,就像你在排序指针数组而不是数据本身时那样,这种优势就会减少.

Mergesort对最坏情况的行为有很好的保证,并且很容易用它进行稳定的排序.