algorithm - 为什么 QuackSort 比 Data.List 的随机列表排序快 2 倍？

Question

我正在寻找 MergeSort 的规范实现在 Haskell 上移植到 HOVM ，我找到了this堆栈溢出答案。在移植算法时，我意识到有些事情看起来很愚蠢:该算法有一个“减半”函数，它只会在递归和合并之前使用一半的长度将列表一分为二。所以我想:为什么不更好地利用这个传球，并使用一个枢轴，让每一半分别比那个枢轴更小和更大呢？这将增加递归合并调用应用于已排序列表的几率，这可能会加速算法!
我已经完成了这个更改，产生了以下代码:

import Data.List
import Data.Word

randomList :: Word32 -> Word32 -> [Word32]
randomList seed 0    = []
randomList seed size = seed : randomList (seed * 1664525 + 1013904223) (size - 1)

quacksort :: [Word32] -> [Word32]
quacksort []           = []
quacksort [x]          = [x]
quacksort (p : x : xs) = split p (p : x : xs) [] [] where

  -- Splits the list in two halves of elements smaller/bigger than a pivot
  split p []       as bs = merge (quacksort as) (quacksort bs)
  split p (x : xs) as bs = quack p (p < x) x xs as bs

  -- Helper function for `split`
  quack p False x xs as bs = split p xs (x : as) bs
  quack p True  x xs as bs = split p xs as (x : bs)

  -- Merges two lists as a sorted one
  merge []       ys       = ys
  merge xs       []       = xs
  merge (x : xs) (y : ys) = place (x < y) x xs y ys

  -- Helper function for `merge`
  place False x xs y ys = y : merge (x : xs) ys
  place True  x xs y ys = x : merge xs (y : ys)

main :: IO ()
main = do
  let l = randomList 0 2000000
  let b = quacksort l
  print $ sum b

然后我对它进行了基准测试，令我惊讶的是，它确实比 Haskell 的官方 Data.List 快 2 倍。种类。所以我想知道为什么在实践中不使用它，突然间，我意识到很明显: 合并排序在已经排序的列表上表现不佳 .哦。因此，quacksort 背后的整个假设都失败了。不仅如此，它对于反向排序的列表会表现得非常糟糕，因为它无法生成大小相似的两半(除非我们能猜到一个非常好的枢轴)。所以，quacksort 在所有情况下都是古怪的，不应该在实践中使用。但是之后...
为什么它的执行速度比 Data.List 的随机列表排序快 2 倍？
我想不出一个很好的理由应该是这种情况。使每一半小于/大于枢轴不会改变必须调用合并调用的次数，因此它不应该产生任何积极影响。但是将其恢复为传统的合并排序确实会使其慢 2 倍，因此，出于某种原因，有序拆分会有所帮助。

Answer 1

您的 split将列表分成两个有序的部分，所以 merge首先消耗它的第一个参数，然后只产生完整的后半部分。换句话说，它等价于 ++ , 在前半部分进行冗余比较，结果总是 True .
在真正的合并排序中，合并实际上对随机数据做了两倍的工作，因为这两个部分没有排序。split尽管在分区上花费了一些工作，而在线自下而上的归并排序根本不会在那里花费任何工作。但是内置排序试图检测输入中的有序运行，显然额外的工作是不可忽略的。