最短路についていろいろ書いてはいるが、ごちゃごちゃして自分にしか分からないようになってしまっていると感じていたので、ここら辺でまとめを書いておこうと思う。現時点で効果のあった改善点としては当り前なのだが、以下のようになる。
１、ソースを整理し、必要なものと不必要なものにわける。
２、アクセスのされかたを考慮して、データを持つ。
以下は現在までの実行時間である。Goldberg 氏の２レベルバケット法よりも実行時間が短縮されている。ただ、このクエリでしか試していないので、これからいろいろ試したいと思う。ちなみにプログラムは こちら より手に入れられるものを用いた。
[Graph data]
USA-road-d.USA.gr
23947347 nodes and 58333344 arcs
[Query data]
p aux sp p2p 10
q 957498 10453327
q 19200797 7727679
q 13006257 40639
q 4314559 22779984
q 17261435 8424294
q 8077810 13186938
q 3048748 1475829
q 21869636 3531883
q 13446936 4981527
q 18549540 3230879
実行結果は次のように記してある。
用いたデータ構造 消費メモリ 実行時間（ファイル読み込み除く）
Xeon 2.33GHz / Mem 16GB / gcc(4.1.2)
２分木 725MB ～ 945MB 42.97[s]
１レベルバケット 910MB ～ 945MB 23.59[s]
２レベルバケット 2808MB 36.08[s]
Xeon 3.00GHz / Mem 8GB / gcc(4.1.2)
２分木 725MB ～ 945MB 29.60[s]
１レベルバケット 910MB ～ 945MB 18.11[s]
１、ソースを整理し、必要なものと不必要なものにわける。
２、アクセスのされかたを考慮して、データを持つ。
以下は現在までの実行時間である。Goldberg 氏の２レベルバケット法よりも実行時間が短縮されている。ただ、このクエリでしか試していないので、これからいろいろ試したいと思う。ちなみにプログラムは こちら より手に入れられるものを用いた。
[Graph data]
USA-road-d.USA.gr
23947347 nodes and 58333344 arcs
[Query data]
p aux sp p2p 10
q 957498 10453327
q 19200797 7727679
q 13006257 40639
q 4314559 22779984
q 17261435 8424294
q 8077810 13186938
q 3048748 1475829
q 21869636 3531883
q 13446936 4981527
q 18549540 3230879
実行結果は次のように記してある。
用いたデータ構造 消費メモリ 実行時間（ファイル読み込み除く）
Xeon 2.33GHz / Mem 16GB / gcc(4.1.2)
２分木 725MB ～ 945MB 42.97[s]
１レベルバケット 910MB ～ 945MB 23.59[s]
２レベルバケット 2808MB 36.08[s]
Xeon 3.00GHz / Mem 8GB / gcc(4.1.2)
２分木 725MB ～ 945MB 29.60[s]
１レベルバケット 910MB ～ 945MB 18.11[s]