バケット系データ構造。

枝長によって簡単に実行時間に影響が受けてしまうバケット系データ構造について、まとめていく。

ある資料によると、Dijkstra 法が生まれたのは 1959 年で、候補枝を格納するためのデータ構造に 1-level bucket を採用したのは 1969 年に Dial によって行われたようだ。

まず、計算量から見ていくが O(m+nU) (n : 点数、m : 枝数、U : 最大枝長）である。これだけみると最大枝長によって、実行時間が決まってしまうようにも思えるが、そうでない。まずは、良く知られているものが挙げていくが、以下のようになる。

・シンプルながら、高速に実行できる
・実行時間は枝長に依存に依存しまい、枝長が大きくなると低速化してしまう
・枝長分だけのバケット配列を要するために、メモリ要求量が大きくなってしまうこともある



実際に実装し、実験を行って得た情報を踏まえると以下のようにいえる。

・道路ネットワークと相性がとても良い（ほぼ理想）
　１．バケット内にある程度分散して格納されている。
　２．最小ポテンシャル点（次探索点）を求める動作が、ハードウェアプリフェッチ (Intel CPU) にのりやすい。

・枝長によって、大きく影響を受ける
　１．最大枝長が０の場合、バケットが働かないため、ある程度大きさの値で置き換える。
　２．枝長が極端に大きい場合、最小ポテンシャル点（次探索点）を求めるコストが大きくなる。

・ポインタを用いての実装では、高速化は難しい。



つまり、まとめると道路ネットワークを解くために出来たようなデータ構造といってもよい（実際そうかもしれないが）ほど、理想的な動きをする。ただし、前処理によって疎化されたグラフなどでは、思ったほどの実行時間を望めないだろうし、実用的な時間内に解けない可能性も出てくる。またメモリ要求量が多めであるため、実行時間・メモリ要求量が安定しているヒープ系に比べ、扱いが難しいともいえる。

また、他のデータ構造と組み合わせる事で、計算量を下げることに成功したデータ構造も存在する。しかしながら、凝った実装（ポインタを用いた実装）になることは避けられず、分岐の増加・データの局所性の低下により、それほどまでに実行時間が短縮されるとも思えない。