バケット法において、循環リスト内で要素の入っているバケットを探すためにインクリメントする方法について。
[1]
循環リストなので、容易に考えられる実装。
一番端までインクリメントされたら、余算により先頭要素へ。
i = (i + 1) % bucket_size;
[2]
1度しか必要でない余算を毎回するのはもったいない。
余算コストに比べ、比較コストは小さいので、効果あり。
ダイクストラ法では1割ほど高速化。
i++;
if (i >= bucket_size) i = 0;
[3]
先頭ノードに向かうのは1度だけであるので、ループをわけてしまう。
for (i = crt_bucket; i <bucket_size; i++){ }
実行時間は [1] >> [2] > [3] と、なっている。
[1]
循環リストなので、容易に考えられる実装。
一番端までインクリメントされたら、余算により先頭要素へ。
i = (i + 1) % bucket_size;
[2]
1度しか必要でない余算を毎回するのはもったいない。
余算コストに比べ、比較コストは小さいので、効果あり。
ダイクストラ法では1割ほど高速化。
i++;
if (i >= bucket_size) i = 0;
[3]
先頭ノードに向かうのは1度だけであるので、ループをわけてしまう。
for (i = crt_bucket; i <bucket_size; i++){ }
実行時間は [1] >> [2] > [3] と、なっている。