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

Bucket-Sort のメモリ要求量を減らす工夫を行った。

1. 各データの頻出回数をカウントする。
2. 1 により、区切りを計算する。
3. 区切りにしたがい、データを書き出す。（区切りは移動してしまう）
4. 区切りを格納しているデータをソート前に戻す

区切りは要素が１つずつずれた形になっているため、簡単に元に戻すことができる。
このような流れなら、forward-star + 枝情報配列程度のメモリ領域で抑えることができる。

結果、それぞれ次のような実行時間で forward-star を構成することができた。
工夫を行ったもの(*)と Quick-Sort との比較である。
確かに Quick-Sort の方が省メモリだが、ダイクストラ法実行時のメモリ要求量は更に大きい（1267.2 MB）ので、Bucket-Sort を採用してもよいだろう。

data: USA-road-d.USA.gr (n=24M, m=58M)
Quick-Sort   6.7 [sec]   758.9 MB
Bucket-Sort* 1.3 [sec]  1204.0 MB