Bucket-Sort のメモリ要求量を減らす工夫を行った。
1. 各データの頻出回数をカウントする。
2. 1 により、区切りを計算する。
3. 区切りにしたがい、データを書き出す。(区切りは移動してしまう)
4. 区切りを格納しているデータをソート前に戻す
区切りは要素が1つずつずれた形になっているため、簡単に元に戻すことができる。
このような流れなら、forward-star + 枝情報配列程度のメモリ領域で抑えることができる。
結果、それぞれ次のような実行時間で forward-star を構成することができた。
工夫を行ったもの(*)と Quick-Sort との比較である。
確かに Quick-Sort の方が省メモリだが、ダイクストラ法実行時のメモリ要求量は更に大きい(1267.2 MB)ので、Bucket-Sort を採用してもよいだろう。
1. 各データの頻出回数をカウントする。
2. 1 により、区切りを計算する。
3. 区切りにしたがい、データを書き出す。(区切りは移動してしまう)
4. 区切りを格納しているデータをソート前に戻す
区切りは要素が1つずつずれた形になっているため、簡単に元に戻すことができる。
このような流れなら、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