枝長による実行時間の変化。

グラフの枝長を 2^n (n = [-10, 10]) 倍に変化させ、実験を行った。
　2^(-10), 2^(-9), 2^(-8), ... , 2^(0), 2^(1), 2^(2), ... , 2^(10)
の 21 通りについてである。


■実行環境
CPU : Xeon 2.33 GHz
OS : CentOS 4.1 64bit
GCC : gcc 4.1.2

graph : USA-road-d.NY.gr
query : p2p x 256 (random)



用いたデータ構造は以下の４つである。

・ヒープ
実行時間・メモリ要求量ともに安定している。

・１レベルバケット
枝長によって、実行時間・メモリ要求量が影響を受けてしまうが、条件によってはとても高速である。

・２レベルバケット
１レベルバケットをベースに、バケット配列と補助配列の２段階にすることで、枝長の影響を軽減している。

・マルチレベルバケット (by goldberg)
実験的に高速であるといわれているデータ構造。



ヒープの実行時間はグラフからも安定しているのがわかる。また、今回用いたデータ構造の中で最もメモリ要求量が少ない。図からはわかりづらいが、2^4 からは４つの中で最も実行時間が短い。

１レベルバケット法・２レベルバケット法では、ともに枝長に影響を受けていることが良く分かる。２レベルでは小さいながらも１レベルに比べ、その影響が抑えられている。2^5 あたりで、交差している。


マルチバケットではうまく適切なレベルを選択しているのだろうか、枝長が小さいときは実行時間も短くなり、枝長が大きくなっても実行時間が抑えられている。