昨日の続きだが、全米データ(#nodes: 23,947,347 | #arcs: 58,333,344)を選んでも、ヒープ付きのダイクストラ法でも 4 秒強くらい(CPU time)で終了しているようだ（メモリの使用量は 1GB 強)。その他の数百万点ぐらいのでグラフでは 1 秒以内に終了する。現在のダイクストラ法がこのような実性能を持っていることは、最適化の専門家の間でもあまり知られていないと思う（私自身も自分の研究室で実行してみるまで知らなかった）。このサーバ PowerEdge 2900 クラスの CPU, メモリが与えられるのであれば、全米クラスのデータでは前処理も必要ないことがわかる。
しかし、普段はこんな大きなマシンを持ち歩くわけにはいかないので、モバイル系の機器を考慮すると、さらなる高速化、省メモリ化が必要になる。こちらのページに Intel Atom と Celeron, Core 2 のベンチマーク結果が掲載されている。CPU の演算性能では Core 2 の数分の一程度だが、メモリ関係のベンチマークでは半分程度と差が縮まる。現在のダイクストラ法はデータの再利用性が極めて低く、メモリアクセスに関するベンチマークテストのような感じになっているので、実際の性能差は後者の結果の方に近くなるかもしれない。
しかし、普段はこんな大きなマシンを持ち歩くわけにはいかないので、モバイル系の機器を考慮すると、さらなる高速化、省メモリ化が必要になる。こちらのページに Intel Atom と Celeron, Core 2 のベンチマーク結果が掲載されている。CPU の演算性能では Core 2 の数分の一程度だが、メモリ関係のベンチマークでは半分程度と差が縮まる。現在のダイクストラ法はデータの再利用性が極めて低く、メモリアクセスに関するベンチマークテストのような感じになっているので、実際の性能差は後者の結果の方に近くなるかもしれない。
アクセス
トータル
