理論的計算量と実験的性能 Heap と mbp

heap と mbp が同様の性能になるという話。

heap : Binary Heap, SSSP O((m+n)log(n))
mbp : Multi-Level Buckets, SSSP O(m+nlog(U))


まず heap の計算量から考えてみよう。
insert(), decreasekey(), extractmin() の計算量は1回あたり log(n) となっている。この log(n) の n はヒープサイズの最大値となっており、最悪時には n となるが、点数 2400万 の USA でもこの値は 10000 程度と随分小さい。

2400 万と 1 万では随分差があるように見えるのだが、あるグラフを与えられたとき、優先キュー内に格納される点数の最大値を簡単に求める方法はない。点数や枝数や次数には緩く依存しているが、ほとんど定数として考えても良さそうである。経験的に道路ネットワークのように近い点同士が枝を張るようなPlanar graph では優先キュー内の要素数が大きくなりがちである。また次数が非常に大きくなる場合も同様である。


次に mbp の計算機上での実行について詳しく見ていく。
mbp 内に格納されるデータアクセスパターンを見ていくと 2^n により分類されている。このアクセスがある意味 heap のような木構造のアクセスパターンと良く似ており、この不連続のアクセスに性能が依存していると考えられる。また mbp のメモリバンド幅要求は非常に大きいが、最適化した heap ではある程度抑えられている。


これらから、アルゴリズムの限界と考えても良いのだが、現状としては多くの要因によってたまたま fitting しているように見えてるだけとかいえないだろう。