線形探索と番兵アルゴリズム

  • 番兵アルゴリズムはただの書き方の問題だと思ってたけど,高速化のテクニックだった,という話.
  • forでvectorの要素を回す時に,毎回比較演算が行われるけど,それが勿体無いという場合に,絶対に止まるよに番兵を置いておいて無限ループで回すというのが番兵テクニックみたいだ.
  • アルゴリズム本体が軽い時,かなり性能がシビアに要求される時には必要なのかな?

forで書く場合(比較は2回)

for (int i=0; i<n; ++i) {         // ここで1回
  if (vec[j] == key) return true; // ここで1回(計2回)
}
return false;

番兵で書く場合(比較は1回)

vector<int> vec(n+1);       // +1個分確保
vec[n] = key;               // 末尾に番兵を置く
int j = 0;
while (1) {                 // 無限ループが絶対に止まることが保証される
  if (vec[j] == key) break; // ここの比較だけで良い
  ++j;
}
if (j==n) return false;// 末尾まで行っていたら失敗
else return true;