あどけない話

インターネットに関する技術的な話など

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 を使うのがよさそうです。

アドバイスを頂いた田中さんと、チューニングでお世話になった高野さんに感謝します。