１レベルバケット or ヒープ。

今まで、dimacs graph data をそのまま用いて実験を行っていたが、枝長についてはあまり考慮しなかった。しかし、バケット法での枝長はかなりクリティカルなものであるため、枝長に影響を受けないヒープも見直していこうと思う。

まずは、pthread で書き直したヒープの実行時間である。やはり通常の道路ネットワークではバケット法に勝ち目はないようだ。ただ goldberg 氏の２レベルバケットと比べてもあまり大差はなく、最適化次第では逆転も十分考えられそうである。

[ヒープ]
１スレッド　38.54 [sec]
２スレッド　21.05 [sec]
４スレッド　12.53 [sec]
８スレッド　 9.58 [sec]

[１レベルバケット]
１スレッド　24.19 [sec]
２スレッド　13.80 [sec]
４スレッド　 8.36 [sec]
８スレッド　 6.92 [sec]

[２レベルバケット]
１スレッド　36.08 [sec]



次にグラフの枝長を10倍、100倍にしたものに対して、上記の「１レベルバケット法」、「ヒープ」について、実験を行った。

[ヒープ]
　　１倍　38.54 [sec]
　１０倍　40.23 [sec]
１００倍　42.37 [sec]


[１レベルバケット]
　　１倍　24.19 [sec]
　１０倍　50.85 [sec]
１００倍 222.84 [sec]

予想よりもヒープは枝長に影響を受ける結果となったが、それでもほとんど実行時間は変わらず、安定していた。バケット法は距離分だけ、バケット配列をインクリメントするため、グラフの枝長の範囲が大きいとき、無駄な処理が大きくなってしまう。できれば、グラフの特性を選んでデータ構造を自動的に、データ構造を選ぶのが望ましいだろう。