performance - linked - quick sort




為什麼Haskell使用mergesort而不是quicksort? (4)

Wikibooks的 Haskell中 ,有 以下聲明

Data.List提供用於排序列表的排序功能。 它不使用quicksort; 相反,它使用稱為mergesort的算法的有效實現。

Haskell使用mergesort而不是quicksort的根本原因是什麼? Quicksort通常具有更好的實際性能,但在這種情況下可能不是。 我認為快速排序的現場好處很難(不可能?)與Haskell列表有關。

關於softwareengineering.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(比 Data.List.sort 慢約6倍)
  • quicksort :1.152s(比 Data.List.sort 慢約7倍)

在命令式語言中,Quicksort通過改變數組來就地執行。 正如您在代碼示例中演示的那樣,您可以通過構建單鏈接列表來使Quicksort適應純函數語言(如Haskell),但這並不是那麼快。

另一方面,Mergesort不是就地算法:簡單的命令式實現將合併的數據複製到不同的分配。 這更適合Haskell,無論如何它必須複製數據。

讓我們退後一步:Quicksort的性能優勢是“絕殺” - 幾十年前在與我們今天使用的機器大不相同的機器上建立的聲譽。 即使你使用相同的語言,這種傳說也需要不時地重新檢查,因為實地的事實可能會改變。 我讀到的關於這個主題的最後一篇基準測試論文讓Quicksort仍處於領先地位,但它在Mergesort上的領先優勢很小,即使在C / C ++中也是如此。

Mergesort還有其他優點:它不需要調整以避免Quicksort的O(n ^ 2)最壞情況,並且它自然是穩定的。 因此,如果由於其他因素而導致性能差異縮小,Mergesort是一個明顯的選擇。


在單鍊錶上,mergesort可以在適當的位置完成。 更重要的是,天真的實現掃描超過列表的一半以獲得第二個子列表的開始,但第二個子列表的開始作為排序第一個子列表的副作用而不需要額外的掃描。 快速排序已經超越mergesort的一件事是緩存一致性。 Quicksort使用內存中彼此接近的元素。 一旦間接元素進入它,就像你在排序指針數組而不是數據本身時那樣,這種優勢變得更少了。

Mergesort對最壞情況的行為有很好的保證,並且很容易用它進行穩定的排序。


我認為@greestorm的答案幾乎就在鼻子上,但這裡有關於GHC排序功能歷史的更多信息。

Data.OldList 的源代碼中,您可以找到 sortimplementation 並驗證它是合併排序。 在該文件中的定義下面是以下註釋:

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函數中構建一個隨機數生成器)。 您仍然遇到的問題是,在對不可變鏈接列表進行排序時,查找任意數據透視表然後根據它進行分區將涉及多個列表遍歷和子列表副本。

我認為實現快速排序所假設的好處的唯一方法是將列表寫入向量,對其進行排序(並犧牲排序穩定性),然後將其寫回列表。 我不認為這可能是一場全面的勝利。 另一方面,如果您已經在向量中有數據,那麼就地快速排序肯定是一個合理的選擇。


關於為什麼Quicksort沒有在Haskell中使用的許多爭論似乎都是合理的。 但是,對於隨機情況,至少Quicksort並不比Mergesort慢。 基於Richard Bird的書“ Haskell中的思考功能”中 給出的實現,我製作了一個三向Quicksort:

tqsort [] = []
tqsort (x:xs) = sortp xs [] [x] [] 
  where
    sortp [] us ws vs     = tqsort us ++ ws ++ tqsort vs
    sortp (y:ys) us ws vs =
      case compare y x of 
        LT -> sortp ys (y:us) ws vs 
        GT -> sortp ys us ws (y:vs)
        _  -> sortp ys us (y:ws) vs

我對一些情況進行了基準測試,例如,包含0到10 ^ 10或10 ^ 4之間的Int的大小為10 ^ 4的列表,依此類推。 結果是3-way Quicksort甚至Bird的版本都比GHC的Mergesort更好,比ghc的Mergesort快1.x~3.x,這取決於數據的類型(很多重複?非常稀疏?)。 以下統計信息由 criterion 生成:

benchmarking Data.List.sort/Diverse/10^5
time                 223.0 ms   (217.0 ms .. 228.8 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 226.4 ms   (224.5 ms .. 228.3 ms)
std dev              2.591 ms   (1.824 ms .. 3.354 ms)
variance introduced by outliers: 14% (moderately inflated)

benchmarking 3-way Quicksort/Diverse/10^5
time                 91.45 ms   (86.13 ms .. 98.14 ms)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 96.65 ms   (94.48 ms .. 98.91 ms)
std dev              3.665 ms   (2.775 ms .. 4.554 ms)

但是,在Haskell 98/2010中還有另一個 sort 要求:它需要 穩定 。 使用 Data.List.partition 的典型Quicksort實現是 穩定的 ,但上面的不是。

後來補充 :評論中提到的一個穩定的3向Quicksort似乎和 tqsort 一樣快。







haskell