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

Question

我正在寻找 MergeSort on Haskell to port to HOVM, and I found this Whosebug 答案的规范实现。移植该算法时，我意识到有些东西看起来很傻：该算法有一个“减半”函数，它除了在递归和合并之前使用一半的长度将列表一分为二之外什么都不做。所以我想：为什么不更好地利用这个传球，并使用一个中枢，让每一半分别比那个中枢小和大？这将增加递归合并调用应用于已排序列表的可能性，这可能会加快算法速度！

我已完成此更改，生成以下代码：

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 倍。所以我想知道为什么这没有在实践中使用，突然间，我意识到了一个显而易见的事实：mergesort 在已经排序的列表 上的表现并不好。哦。所以 quacksort 背后的整个假设都失败了。不仅如此，对于反向排序的列表，它的表现会很糟糕，因为它无法生成大小相似的两半（除非我们能猜出一个非常好的主元）。所以，quacksort 在所有情况下都是古怪的，不应该在实践中使用。但是，那么...

为什么它的执行速度比 Data.List 的随机列表排序快 2 倍？

我想不出这种情况的充分理由。将每一半 smaller/bigger 设置为枢轴不会改变必须调用合并调用的次数，因此它不应该有任何积极影响。但是将其恢复为传统的合并排序确实会使速度慢 2 倍，因此，出于某种原因，有序拆分会有所帮助。

Answer 1

您的 split 将列表分成有序两半，因此 merge 首先使用它的第一个参数，然后只生成完整的后半部分。换句话说，它相当于 ++，在前半部分进行冗余比较，结果总是 True.

在真正的合并排序中，合并实际上对随机数据做了两倍的工作，因为这两部分没有排序。

虽然 split 在分区上花费了一些工作，而在线 bottom-up 合并排序根本不会在那里花费任何工作。但是 built-in 排序试图检测输入中的有序运行，显然额外的工作是不可忽略的。

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

Why is QuackSort 2x faster than Data.List's sort for random lists?

sorting

algorithm

mergesort

haskell

quicksort