in-place Bucket-Sort を調べているが、あまりにも性能が出ない。どうもデータアクセスに異常なほど時間がとられているのだが、ここまで遅いと他にも原因があるのではないかとも思える。
in-place に限らず、Bucket-Sort は条件さえそろえばとても効率的である。というのも、無駄なスワップはなく各データが書き込むのは1度だけ(事前に1回読み込み、各データの頻出回数を格納しなければならないが、それは誤差の範囲ほどの時間しかかからない)という効率さである。
しかしながら、そうなると当然とびとびのデータアクセスのためのコストが問題になっては来るのだが、次のようにあまりにも時間がかかりすぎている。in-place でなれば、かなり改善と思うため、こちらも作成し検討してみようと思う。しかしながら、数百メガバイト分の補助領域が必要となってくるためにトレードオフだろう。
in-place に限らず、Bucket-Sort は条件さえそろえばとても効率的である。というのも、無駄なスワップはなく各データが書き込むのは1度だけ(事前に1回読み込み、各データの頻出回数を格納しなければならないが、それは誤差の範囲ほどの時間しかかからない)という効率さである。
しかしながら、そうなると当然とびとびのデータアクセスのためのコストが問題になっては来るのだが、次のようにあまりにも時間がかかりすぎている。in-place でなれば、かなり改善と思うため、こちらも作成し検討してみようと思う。しかしながら、数百メガバイト分の補助領域が必要となってくるためにトレードオフだろう。
data: USA-road-d.USA.gr(n=24M, m=58M) Quick-Sort 6.7[sec] in-place Bucket-Sort 17[sec]