3

我在 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 的瓶颈，每次调用都会生成两个新列表？

4

1 回答 1

9

照原样，

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-10T19:29:28.717 回答