メニュー  前へ  次へ  関連リンク: Darkside of the Haskell -- 副作用版クイックソート  Java によるクイックソートキラー

手続き脳によるHaskell -- クイックソート(quick sort)

 ここでは、Haskellでクイックソート(quick sort)を実装してみましょう。 クイックソートを知らない人は このページ を参照してください。 Haskell による典型的なクイックソートの実装は以下のようになるでしょう。

QuickSort1.hs

 この実装は Haskell の入門などでよく紹介されますが、 実は重大な問題があります。 ソート済みの系列をソートすると \(O(n^2)\) の計算量がかかるのです。 ソート済みの系列をソートすることはありがちな局面なので、 これでは全く実用性がありません。 また、lhsrhs は本来一回のリストの走査で計算できるのに、 2回に分けて求めている所も効率が悪いです。

 そこで、pivot の選び方を工夫してソート済みの系列に対しても \(O(n\log n)\) の計算量になるように修正し、 リストの不要な走査もでき得るかぎり減らすと、以下のようになります。 系列の先頭・中間・末尾の3つの中の中央値を pivot として選びます。

QuickSort2.hs

 ただし、このように工夫してもなお、 巧妙に工夫された系列では \(O(n^2)\) の計算量がかかることが知られています。 ところで、クイックソートは一般に不安定なソートとして知られていますが、 QuickSort1.hs, QuickSort2.hs の実装は安定なソートです。 QuickSort2.hs では lhs, rhs だけではなく、 pivot に等しい要素を pivots として系列を3分していますが、 これにより、このソートは安定ソートになります。

【高速化】

 上記の QuickSort2.hs は (++) 演算子を濫用しており、 まだまだ効率が悪いです。また、 山型の系列を処理すると計算量が \(O(n^2)\) になります。 そこで、より実用性を考慮すると以下のようになります。 QuickSort3.hs も安定ソートです。

QuickSort3.hs

 以下のような qcat 関数が何やら素直じゃありませんが、 これは関数型言語で2分木処理をする時の定石なんだそうです。

        qcat  _ ![] ys = ys
        qcat !n !xs ys = qcat nl (lhs []) (pivots !++ qcat nr (rhs []) ys)

 言われてみれば、クイックソートは2分木処理の一種ですね。 こう書くと、 素朴に書いた場合に (++) 演算子の繰り返しの最悪計算量が \(O(n^2)\) になるのが \(O(n)\) に抑えられるそうです。 関数脳って面倒くさいなぁ... ちなみに、ボトムアップマージソートのページ で説明した、リストの末尾への要素の追加の計算量を \(O(1)\) に抑えるテクニックも使っています。

 このコードの高速化のミソはこれ以外に pseudoMedian 関数があります。これは多くの場合に与えられた系列のほぼ中央値を返します。 そのため典型的なケースでは2分木の分割がほぼ半々になり、 再帰の深さが理想値に近づきます。 クイックソートが遅くなるのは、2分木分割のバランスが崩れて、 再帰の深さが深い部分ができてしまうことが原因ですので、 この関数を導入すると性能が改善されます。

 pseudoMedian 関数を使うと、 昇順・降順・山型などの系列を与えても、 計算量が \(O(n^2)\) になったりしません。 一応、クイックソートキラー(quick sort killer)として知られる クイックソートを \(O(n^2)\) の最悪計算量に陥れるテストにかけてみましたが、 マージソートなどと変わらない効率を維持していました。 (クイックソートキラーに関しては こちらのページ へどうぞ)

 この他にも、median of medians という方法があるそうですが、 何やら面倒くさそうだし、サンプルコードも見当たらないのであきらめました。 median of medians の場合、 pivot による分割が最悪でも 30% : 70% で行われるそうで、 より2分木分割が理想に近づくそうですが、 実際にはそこまでやる必要はないようです。

 上記の pseudoMedian 関数は最悪の pivot を選ぶことがあります。 つまり、2分木の分割が \(1 : n - 1\) になることがあります。 しかし、クイックソートが \(O(n^2)\) の計算量に陥るのは、 最悪の選択が \(n\) に比例するくらいある場合です。 最悪の選択が \(\log n\) に比例するくらいに抑えられていれば、 計算量は \(O(n\log n)\) に抑えられます。 pseudoMedian 関数はその条件を満たしています。


メニュー  前へ  次へ  関連リンク: Darkside of the Haskell -- 副作用版クイックソート  Java によるクイックソートキラー