haskell - 为什么使用 foldl' 实现 Haskell 中的 MergeSort 更快？

Question

我在 Haskell 中实现了两个版本的合并排序，如下所示:

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

其中 'merge' 和 'splitList' 的实现方式如下:

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] ys = ys
merge all_x@(x:xs) all_y@(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 秒后显示最后一个元素。

我可以理解为什么由于 foldl' 的尾递归性等原因，mergeSort1 使用的内存比 mergeSort2 少得多。

我不明白为什么 mergeSort1 比 mergeSort2 快这么大的差异？

会不会splitList是mergeSort2的瓶颈，每次调用都会生成两个新列表？

Answer 1

照原样，

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更快，因为你给了它最佳输入，它在线性时间内完成。