Haskellの配列でクイックソート
Haskell の クイックソート としては、以下のようなコードがよく例に出てきます。
quickSortList :: [a] -> [a] quickSortList [] = [] quickSortList (x:xs) = quickSortList lt ++ [x] ++ quickSortList gt where lt = filter (<x) xs gt = filter (>=x) xs
これは、小さなリストを何度も連結するので、効率が悪そうです。
そこで、一旦配列に直し、固定領域を使ってソートして、またリストに戻す方がいいのではないかと思い、実装して速度を比べてみました。配列を使うクイックソートのコードは、「珠玉のプログラミング」から拝借しました。ベンチマークも含むコードは、gist に上げています。
結果はこんな感じ(単位はms)：
| 入力のサイズ | 10^4 | 10^5 |
| Data.List.sort | 15.09825 | 256.7437 |
| quickSortList | 12.97226 | 193.1537 |
| quickSortST | 7.502490 | 92.16319 |
| quickSortVec | 6.115590 | 71.58241 |
| introSort | 3.233967 | 35.04761 |
- Data.List.sort は、マージソートの改良版
- quickSortList は、上記に示したおなじみの実装
- quickSortST は、ST という破壊的代入ができる型の可変配列を直に使った実装
- quickSortVec は、Vector を使った実装。内部は ST だと思われる
- introSort は、vector-algorithms で提供されている Vector を使ったイントロソート
これを見ると、配列に変換するオーバーヘッドを払っても、Vector を使うのがよさそうです。
アドバイスを頂いた田中さんと、チューニングでお世話になった高野さんに感謝します。
