Haskell 快速排序实现（如何获得最佳性能？）

Question

我目前正在阅读有关功能数据结构和算法的内容，并尝试了不同的快速排序实现。然而，我注意到他们的表演有很多变化。

下面是我要讨论的一些精选的（所有程序都已经编译（ghc program.hs）进行测试（括号中的时间是优化-O标志获得的时间），要排序的列表是（最坏的情况已经排序了（这意味着所花费的时间在O (n^2))) [1 .. 20000] 列表中）：

qs1 []             = []
qs1 (pivot : rest) = qs1 lower ++ [pivot] ++ qs1 upper  where
  lower = [ x | x <- rest, x <= pivot ]
  upper = [ x | x <- rest, x >  pivot ]

这是我们学习语言时看到的经典类型。在这里，rest列表被遍历两次以首先过滤小于或等于枢轴的元素，然后是大于枢轴的元素。所用时间为 6.45 (4.42) 秒。

qs2 []             = []
qs2 (pivot : rest) = qs2 lower ++ [pivot] ++ qs2 upper  where
  (lower, upper) = foldr
    (\x (l, u) -> if x <= pivot then (x : l, u) else (l, x : u))
    ([], [])
    rest

我对这个感到惊讶。它与上面相同，只是它只遍历rest列表一次。它的表现比第一个差，总共为 8.11 (2.95) 秒。我尝试了partitionData.List 库中的函数，但它只会更糟（更糟），灾难性的 10.99 (9.99) 秒。我检查了实现，但它与我的 lambda 函数几乎相同，尽管它依赖于一个实用函数：

partition               :: (a -> Bool) -> [a] -> ([a],[a])
partition p xs = foldr (select p) ([],[]) xs

select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select p x ~(ts,fs) | p x       = (x:ts,fs)
                    | otherwise = (ts, x:fs)

（取自https://hackage.haskell.org/package/base-4.14.0.0/docs/src/Data.OldList.html#partition）。

qs3 []             s = s
qs3 (pivot : rest) s = qs3 lower (pivot : (qs3 upper s))  where
    lower = [ x | x <- rest, x <= pivot ]
    upper = [ x | x <- rest, x >  pivot ]

在这一方面，有 2 个新奇事物。拳头，删除 append++以支持 cons :。其次，它是一个尾递归函数，所以它（原则上）应该更快。然而，它仅仅比第一个好，时间为 6.42 (4.44) 秒。事实上，由于从一个执行到另一个执行的变化，它可能是相同的。

qs4 []             s = s
qs4 (pivot : rest) s = qs4 lower (pivot : (qs4 upper s))  where
  (lower, upper) = foldr
    (\x (l, u) -> if x <= pivot then (x : l, u) else (l, x : u))
    ([], [])
    rest

同样，这与上面的相同，除了我用 a 替换了 2 列表遍历foldr，并且再次增加了所花费的时间：8.02 (2.95) 秒。

split pivot [] lower upper s = qs5 lower (pivot : qs5 upper s)
split pivot (h : t) lower upper s
     | h <= pivot = split pivot t (h : lower) upper s
     | otherwise  = split pivot t lower (h : upper) s

qs5 []             s = s
qs5 (pivot : rest) s = split pivot rest [] [] s

这是最快的。我记录了 2.82 (1.92) 秒的惊人时间，几乎比“最慢”快 4 倍。它在 2 个相互调用的函数之间跳动。split是一个递归函数，用于分隔rest由qs5函数发送的列表元素，完成分区后返回。

---

结论：这到底是怎么回事？我对编译过程中所有隐藏的微妙之处感到困惑，这些细节使我对程序性能的期望出错了。我虚心感谢任何可以通过指出引擎盖下发生的事情来帮助我解开这个拼图碎片的人。