Goldberg 氏によるベンチマーク問題について、いろいろ実験を行っている。
Heap と MLB は、異なるアルゴリズムではあるが、どちらも log によって計算量が抑えられているため、同じグラフ特性に対しては同じような性能を示している。枝長の分散が大きいグラフでは、MLB のほうが有効といえるが、それでも 20% 向上する程である。
また、Heap に比べ MLB は 1.77 倍 もメモリ要求量が多いため、2 threads で実行してもまだ Heap のほうがメモリ要求量が少ない(グラフデータは共有しているため)。現在の計算機では SMP が当たり前になりつつあると思われるので、厳しい条件ではないと思われる。
Bucket は、あまりにも時間がかかりすぎてしまい、正直ソルバーとしては使いづらい。
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)
※コメント投稿者のブログIDはブログ作成者のみに通知されます