メニュー  前へ  次へ  関連リンク:マージソート 

手続き脳によるHaskell -- ボトムアップ マージソート(bottom-up merge sort)

 私のホームページを見てくれた人のツイッターで、Haskell では、 マージソートはボトムアップの方が速いという指摘があるのを見つけました。 C++ などはボトムアップなマージソートにすると 普通のマージソート より遅くなるので調べていなかったのですが、せっかくのご指摘なので、 ボトムアップなマージソートも実装してみました。なるほど、 確かに速かったです。

 Haskell によるボトムアップなマージソートの実装は以下のようになります。 なお、この実装によるボトムアップなマージソートは安定ソートです。

MergeSort3.hs

 ボトムアップなマージソートは、 まず最初に与えられた系列を昇順にソートされた区間の列に分割します。 もちろん、任意の系列には降順の部分もあるので、 そのままでは昇順の区間に分割できません。 そこで降順の部分は順序を反転して昇順に修正します。上記コードの groupRun がそれを行う関数です。

 groupRun に系列 [3,1,4,1,5,9,2,6,5,3,5,8,9] を与えると、[[1,3],[1,4],[5,9],[2,6],[3,5],[5,8,9]] のような昇順区間の列を返します。後は、unify で隣接する区間のマージを繰り返し、 最終的に1つの区間にマージしてソート終了です。

 関数 cutLE で、ちょっと面白いテクニックとして、 リストの末尾への要素の追加の計算量を \(O(1)\) に抑えるテクニックが使われています。 リストの先頭への要素の追加は、以下のように計算量 \(O(1)\) ですが、 リストの末尾への要素の追加は、普通、以下のように計算量 \(O(n)\) です。

        先頭への追加  [1] ==> 2:[1] ==> 3:[2,1] ==> 4:[3,2,1]
        末尾への追加  [1] ==> [1] ++ [2] ==> [1,2] ++ [3] ==> [1,2,3] ++ [4] 

 しかし、関数の合成を利用すると、以下のように末尾への要素の追加を、 ならし計算量(amortized complexity)で \(O(1)\) にできます。

        (1:) ==> (1:) . (2:) ==> (1:) . (2:) . (3:) ==> (1:) . (2:) . (3:) . (4:)

 もちろん、関数は最終的にはリストに変換してやる必要があります。 この瞬間、\(O(n)\) の計算量が発生しますが、 \(n\) 個の要素で平均すれば、\(O(1)\) です。 以下のようにします。

        let fs = (1:) . (2:) . (3:) . (4:) in fs [] -- [1,2,3,4] になる

 この実装は、昇順および降順にソート済みの系列に対して非常に高速です。 また、小さいサイズの系列に対しても高速です。しかも安定なソートですから、 ある意味 Haskell におけるソートの決定版と言えるかもしれません。

 ところで、単にマージソートしたいだけなら、 上記のコードはもっと簡単に出来ることにお気づきでしょうか?何も groupRun で昇順区間を切り出してやる必要はなく、 map (\x -> [x]) で1つ1つ切り出してやればマージソート出来ます。 長さが1の系列は常に昇順あるいは降順と見なせるからです。 そのように書き直すと以下のようになります。

MergeSort4.hs

 このコード、速度は MergeSort3.hs に劣りますが、 ボトムアップではない 普通のマージソート (MergeSort1.hs)には勝ります(乱数列で比較)。 何より簡単なので、憶えておきやすいですよね。 筆者はこの簡単バージョンがお気に入りです。


メニュー  前へ  次へ  関連リンク:マージソート