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

Question

我在Haskell中实现了两个版本的Merge Sort,如下所示:

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)

这样做last $ mergeSort2 [1000000,999999..0]在显示后处理的多于一分钟数百万ghci的结果,同时做last $ mergeSort1 [1000000,999999..0]在仅示出5秒后的最后一个元素的结果.

我可以理解为什么mergeSort1比mergeSort2使用更少的内存,因为foldl'的尾递归等等.

我无法理解的是,为什么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更快,因为你给了它最佳输入,它在线性时间内完成.