番兵の有用性がイマイチわかりません。

Question

こちらの、与えられたキーが、配列に含まれるか否かを判別する関数を番兵を用いるverと用いないverの実装の比較に関して質問があります。
普通の線形探索では

bool linear_search(int A[], int n, int key) {
  // A[]: 配列, n:配列の要素の数
  for (int i = 0; i < n; i++) {
    if (A[i] == key) return true;
  }
  return false;
}

と書くのですが

bool linear_search(int A[], int n, int key) {
  // A[]: 配列, n:配列の要素の数
  int i = 0;
  A[n] = key;  // 番兵の設置
  while (A[i] != key) i++;
  return i != n;
}

このように番兵を用いることで定数倍の高速化が可能になっているそうなのですが自分には理解できません。
上のパターンでは0から順番に見ていってi番目になったらkeyを返し、下のパターンでは0から順番に見ていってkeyが見つからなかったらiを1ずつインクリメントしていくということをしてると思うのですがどう高速になっているのでしょうか？記事の方はif文がない分早くなっているとおっしゃているのですが結局両者ともn回見てない...?となってしまいます。どう高速になっているか詳しく教えていただけますと幸いです。よろしくお願い致します。

Answer 1

bool linear_search(int A[], int n, int key) {
  // A[]: 配列, n:配列の要素の数
  for (int i = 0; i < n; i++) {
    if (A[i] == key) return true;
  }
  return false;
}

これだとi < nの条件チェックとif (A[i] == key)の条件チェック

bool linear_search(int A[], int n, int key) {
  // A[]: 配列, n:配列の要素の数
  int i = 0;
  A[n] = key;  // 番兵の設置
  while (A[i] != key) i++;
  return i != n;
}

これだとA[i] != keyの条件チェック

よって条件チェック数が半分になる…ってことだと思う

Comments

[stdio]

補足ですが、メモリの壁の破壊が可能なC,C++等で可能なバグ技なので、他の言語ではご利用になれません。ご注意下さいませ...

[otn]

> 他の言語ではご利用になれません。
何かの勘違いでしょう。
配列への要素追加が出来るすべての言語で使えます。

[Zuishin]

番兵は他の言語でも使えますし、C/C++ でも引数として渡された配列の範囲外にアクセスしてはいけません。

[dodox86]

質問文中で提示された記事の中でも
> 計算量は変わらずNのオーダーですが、ループの中にif文がない分、早くなっており定数倍の高速化が見込まれます。
と説明がありますが、記事では双方のベンチマークが示されていないので分かりませんね。数百～数千万回のループであれば差が出てくるかもしれませんが、実質、どれだけ効果あるのか。
過去、同じような処理で「本当に有意な差があるか？」と試したteratailの質問回答があった気がしますが、見付けられずじまいでした。

[dodox86]

番兵はC言語でもバグ技ではありませんね。明示的に配列に＋１個増やして、値として無効な値(NULLとか-1とか)を入れて扱うことは良くあります。

[maisumakun]

というか、C言語のヌル終端文字列自体、番兵そのものですし。

[dodox86]

確かに。

[fana]

主題と関係ないですが，引数に関する注意書きが色々と必要そうだし，使う側にとっては扱いづらい関数に見える……この形だと引数をconstにもできないし．

[rururu3]

参考サイトのやつだとO(n)だからif数あまり気にしないでもいいかな…
問題がat-corderとかのやつだとifよりはO(n)なのかO(logn)なのかO(n^2)なのかを気にしないといけない

[Zuishin]

そういえばつい最近 C# で番兵を使った回答したのを思い出しました。

https://teratail.com/questions/263952#reply-378364
> foreach (var c in source.Append(','))

カンマ区切りの文字列を分割するコードですが、一番最後にカンマを置くことでロジックをシンプルにしています。この番兵の目的は高速化ではありません。番兵を置かないと、ループが終わった時点で未処理のデータが残るので、それを掃き出すために置いています。

[stdio]

> 配列への要素追加が出来るすべての言語で使えます。

Javaの場合、リストか配列の結合使わないと出来なかった気がします。
今回の質問のプログラムを行い場合はstd::vectorでstd::findを使った方が、早いと思います。

[Zuishin]

使えばできるということです。

[rururu3]

Javaあまり使ってないけど
int foo[] = new int[3];
foo[2] = 1;
とかできるんだからJavaでもできますよね。
(配列数一つ増やしておくは当然として)

[dodox86]

私の2020/05/26 13:20のコメント自体への補足です。

> 数百～数千万回のループであれば差が出てくるかもしれませんが、実質、どれだけ効果あるのか。

これは実用上の効果の話で、もとのコードに厳然として if (i < N)のチェックがある以上、そのコード＊N回のCPU時間はかかるわけで、それをもって「定数倍」かかるのは理論的に正しいと言えると思います。オリジナルの記事に反論している訳ではありません。番兵を使うことでメリットがあるのは、rururu3さんの本回答で既にご指摘済みのように、番兵をつかうことでコード量の削減が図れる場合がある、と言うことだと思います。実際にどれほど効果があるかはまたちょっと別の話ではないかな、と。

[cunwe]

皆様ありがとうございました。今回の番兵の役割は単にコード量の削減のためという理解で終えたいと思います。特に本回答して下さったrururu3さん、ありがとうございました。