Dijkstra 法にもブロッキング。

最短路問題に使用するグラフの格納方法として Forward Star (名前が合っているか分らないが)を採用している。node 数分の配列１つと、arc 数分の配列２つによりグラフデータを格納することにしている。

ex)
tail / head / lentgh
1 2 1
1 3 2
2 1 4
2 4 2
3 2 2
3 4 3
4 2 2
4 3 3

ID / incident / head /length
0 - 2 1
1 0 3 2
2 2 1 4
3 4 4 2
4 6 2 2
5 - 4 3
6 - 2 2
7 - 3 3

この格納ならば枝のスキャンの部分は一般的な for 文となりデータの整理がし易い。明示的にループの回数は特定できるし、ループ内で使用するデータとそうでないものとを分けておけば、高速化できているのではないかと思い、実験してみた。効果がないのであれば、変数の置き直しによるオーバーヘッドにより低速化してしまうだろう。また、うまくいったら、SIMD 等でさらに高速化が期待できる。


今回実験に用いたデータは、DIMACS の NY とランダムに作成した 1000 個のクエリである。ひとつひとつは数十ミリ秒で実行してしまうので、差が出にくいかと思ったが、次のように若干であるが改善されている。誤差が積もっての結果かもしれないので、１回の処理が大きい、USA 等の大きなグラフでも実行みることにした。しかし、USA-road-d.USA.gr では期待を裏切られ、あまり効果が表れていない。

CPU : Xeon3.0GHz / Mem : 8GB

[USA-road-d.NY.gr]
通常　　　　　：52秒
ブロッキング後：49秒

[USA-road-d.USA.gr]
通常　　　　　：33秒
ブロッキング後：34.5秒



以下、違うマシンでの結果を改善されたと勘違いしました。
/*--------------------------------------------------
ただ、以前の 46 秒ほどに比べ、10 秒以上も改善されており、
なんというか今回の改善が直接効いているのではないのではないかと思う。

この前の BLOG のときと異なる点は、確認のためにスキャンしている枝数をカウントしているだけである。確信はないがこれが効いている可能性が高いため、データ・処理の流れが安定的ではないことで、実行がうまくいっていないのかもしれない。もう少し流れを追えば分かるかもしれない。
--------------------------------------------------*/