ソートあれこれ - その４。

in-place Bucket-Sort を調べているが、あまりにも性能が出ない。どうもデータアクセスに異常なほど時間がとられているのだが、ここまで遅いと他にも原因があるのではないかとも思える。

in-place に限らず、Bucket-Sort は条件さえそろえばとても効率的である。というのも、無駄なスワップはなく各データが書き込むのは１度だけ（事前に１回読み込み、各データの頻出回数を格納しなければならないが、それは誤差の範囲ほどの時間しかかからない）という効率さである。

しかしながら、そうなると当然とびとびのデータアクセスのためのコストが問題になっては来るのだが、次のようにあまりにも時間がかかりすぎている。in-place でなれば、かなり改善と思うため、こちらも作成し検討してみようと思う。しかしながら、数百メガバイト分の補助領域が必要となってくるためにトレードオフだろう。

data: USA-road-d.USA.gr(n=24M, m=58M)
Quick-Sort            6.7[sec]
in-place Bucket-Sort 17[sec]