線形探索と番兵アルゴリズム
- 番兵アルゴリズムはただの書き方の問題だと思ってたけど,高速化のテクニックだった,という話.
- 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;