3

私は次のようにHaskellに2つのバージョンのマージソートを実装しました：

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)

ghcilast $ mergeSort2 [1000000,999999..0]で実行すると、1分以上の処理後に数値1000000が表示されますが、実行すると、last $ mergeSort1 [1000000,999999..0]5秒後にのみ最後の要素が表示されます。

foldl'などのテール再帰性のために、mergeSort1がmergeSort2よりもはるかに少ないメモリを使用する理由を理解できます。

私が理解できないのは、mergeSort1がmergeSort2よりも大きな違いで速い理由です。

splitListがmergeSort2のボトルネックであり、呼び出しごとに2つの新しいリストが生成される可能性がありますか？

4

1 に答える 1

9

そのまま、

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

基本ケースを指定していないため、は無限再帰です（長さのリストの結果を指定する必要があります< 2）。それが修正された後は、各ステップで完全なトラバーサルが必要であり、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

これは、逆ソートされた入力で特にうまく機能しますが、ソートされた入力またはランダムな入力を与えると、2乗でスケーリングします。

mergeSort1線形時間で終了する最適な入力を与えたので、より高速でした。

于 2012-08-10T19:29:28.717 に答える