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 しているように見えてるだけとかいえないだろう。
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 しているように見えてるだけとかいえないだろう。
![](https://blogimg.goo.ne.jp/user_image/07/c3/efd7859272d55d8b205421ec01979293.png)