Bucket, Heap, MLB。

Goldberg 氏によるベンチマーク問題について、いろいろ実験を行っている。

Heap と MLB は、異なるアルゴリズムではあるが、どちらも log によって計算量が抑えられているため、同じグラフ特性に対しては同じような性能を示している。枝長の分散が大きいグラフでは、MLB のほうが有効といえるが、それでも 20％ 向上する程である。

また、Heap に比べ MLB は 1.77 倍 もメモリ要求量が多いため、2 threads で実行してもまだ Heap のほうがメモリ要求量が少ない（グラフデータは共有しているため）。現在の計算機では SMP が当たり前になりつつあると思われるので、厳しい条件ではないと思われる。

Bucket は、あまりにも時間がかかりすぎてしまい、正直ソルバーとしては使いづらい。

[Graph] : Long-n.21.0.gr
#nodes    2,097,152
#arcs     8,126,432
length    [0, 2097152]

[Query] : Long-n.21.0.p2p (1000)

Bucket   40652.3001[sec] (126.0 MB)
Heap(1)    448.1252[sec] (134.0 MB)
Heap(2)    228.4283[sec] (198.0 MB)
MLB        408.6989[sec] (236.0 MB)