爲什麼在使用foldl'實現Haskell時MergeSort更快？

我已經實現歸併排序的兩個版本在Haskell就像如下：爲什麼在使用foldl'實現Haskell時MergeSort更快？

mergeSort1 :: (Ord a) => [a] -> [a] 
mergeSort1 xs = foldl' (\acc x -> merge [x] acc) [] xs

和

mergeSort2 :: (Ord a) => [a] -> [a] 
mergeSort2 [] = [] 
mergeSort2 (x:[]) = [x] 
mergeSort2 xs = (mergeSort2 $ fst halves) `merge` (mergeSort2 $ snd halves) 
     where halves = splitList xs

其中 '合併' 和 'splitList' 是這樣實現的：

merge :: (Ord a) => [a] -> [a] -> [a] 
merge [] [] = [] 
merge xs [] = xs 
merge [] ys = ys 
merge [email protected](x:xs) [email protected](y:ys) 
    | x < y = x:merge xs all_y 
    | otherwise = y:merge all_x ys 

splitList :: [a] -> ([a], [a]) 
splitList zs = go zs [] [] where 
    go [] xs ys = (xs, ys) 
    go [x] xs ys = (x:xs, ys) 
    go (x:y:zs) xs ys = go zs (x:xs) (y:ys)

在ghci中使用last $ mergeSort2 [1000000,999999..0]會導致在超過一分鐘的處理後顯示數字1000000，同時做last $ mergeSort1 [1000000,999999..0]結果顯示只有5秒後才能顯示最後一個元素。

我可以理解爲什麼mergeSort1使用比mergeSort2少得多的內存，因爲foldl'的尾遞歸性等等。

我不明白爲什麼mergeSort1比mergeSort2快這麼大的區別？

難道是splitList是mergeSort2中的瓶頸，每次調用都會生成兩個新列表？

來源

2012-08-10 tonlika

不要使用ghci測試這些東西;它完全不代表編譯的程序的性能。用優化編譯測試程序（'-O'）;你可以使用['criterion']（http://hackage.haskell.org/package/criterion/）來對它進行基準測試，或者如果你想快速和骯髒，只需編寫兩個單獨的測試程序並使用Unix時間用於計時的實用程序。 – 2012-08-10 19:27:24

@sacundim是的，我已經測試了它們都是以可執行格式進行測試，用-O2進行編譯，但差別仍然很大。 mergeSort1在4秒內完成，而mergeSort2在58秒內完成。 – tonlika 2012-08-10 19:35:14

~~AS是，~~

mergeSort2 :: (Ord a) => [a] -> [a] 
mergeSort2 xs = (mergeSort2 $ fst halves) `merge` (mergeSort2 $ snd halves) 
     where halves = splitList xs

~~是一個無限的遞歸，因爲你沒有給一個基本情況（需要指定爲長度< 2的列表中的結果）~~。在修復之後，mergeSort2由於splitList仍然相對較慢，因此需要在每個步驟中完成遍歷並構建兩個新列表，而不允許在完成之前處理任何內容。一個簡單的

splitList zs = splitAt h zs where h = length zs `quot` 2

做得更好。

但是，您的mergeSort1根本不是合併排序，而是插入排序。

mergeSort1 :: (Ord a) => [a] -> [a] 
mergeSort1 xs = foldl' (\acc x -> merge [x] acc) [] xs

這對反向排序的輸入特別有效，但如果您給它排序或隨機輸入，它將按比例進行縮放。

因此，mergeSort1速度更快，因爲它給了它最佳輸入，並在線性時間內完成輸入。

來源

2012-08-10 19:29:28

對不起，忘了將mergeSort2的兩行基本大小寫粘貼起來。現在他們在那裏編輯。 – tonlika 2012-08-10 19:33:04

好的，答案的其餘部分不受影響，「mergeSort1」不是合併排序，並且您的輸入對於該插入排序而言是最佳的。 – 2012-08-10 19:34:14

嘗試了splitList和實現的排序輸入，並且mergeSort1在每次測試中的執行速度都比mergeSort2快5倍，性能差距隨着N的每增加10倍而擴大。 – tonlika 2012-08-10 19:55:43

爲什麼在使用foldl'實現Haskell時MergeSort更快？

回答

相關問題