今回は線形探索における、番兵法という方法を用いて処理を軽くするテクニックを紹介したいと思います。
線形探索とは？
まず線形探索とは何かについて。
ある配列の中に、特定の値が存在するかどうかを調べる場合を考えましょう。
その時に配列に格納されている値を先頭から末尾まで一つ一つ調べていき、
特定のデータと一致するものがあるのかを調べることを線形探索と言います。
まあ普通にパッと思いつく探索って感じですね。
この線形探索のコードを書いてみました。
#define N 5
void search_linear(int data, int x[N]){
int i=0;
while((x[i]!=data) && (i<N))
i++;
if(i<N)
printf("%d番目の要素で探索成功\n",i);
else
printf("探索失敗\n");
}マクロ定義のNは配列の長さです。
関数search_linearが線形探索の関数で
引数のint dateは特定の値。
int x[N]は探索する配列です。
そしてwhile文です。
int i=0;
while((x[i]!=data) && (i<N))
i++;継続条件の一つ目、
x[i]!=dateは、x[i]が探している値でない時は継続。
言い換えれればx[i]が探している値ならば終了という意味です。
継続条件の二つ目、
i<Nはループが配列の中だけで行われるようにするための制約です。
まあ二つとも特に難しいことはないと思います。
本文ではiをインクリメントします。
継続ならあたらしいiで条件式に当てはめる。終了ならそのiを保持して下のif文に行くって感じです。
if(i<N)
printf("%d番目の要素で探索成功\n",i);
else
printf("探索失敗\n");iがNより小さい時はx[i]!=dateを守れなくてループを終了した、つまり配列の中に求める値があったってことですね。なので探索成功。
iがNより大きいとき、これはつまりi=Nの時ですね。ループがi<Nを守れなくて終了したということで、s配列の中に求める要素がなかったことになります。なので探索失敗。
以上が簡単な線形探索のコードの例です。
まあとくに難しくはないと思います。
番兵法のアルゴリズム
番兵法では上の探索を改良します。
どこを改良するかというと、whileの条件です。
ん？改良するところなんてある？
実はあるんですね。
上の探索ではwhileの条件にx[i]!=dateとi<Nの二つの条件がありました。
これは毎度whileのループが回るたびにコンピュータに二つの式を処理させているってことなんですね。
番兵法ではこの条件式を
x[i]!=dateのみにして、毎度の式の処理を一つのみにします。
そしたらもし配列の中に求めている値がなかった時、whileループはどうやって終わるの？
そうですね。
このままだともし配列の中に求めている値がなければ無限ループすることになります。
なのでここから工夫をしていきます。
この無限ループを防ぐために、配列の最後に求める値を追加します。
配列の最後に追加・・？
イメージ図です。
これが元の配列
ここに配列の最後に求める値を追加するとは以下のようなことです。
つまり配列の長さがN+1になるってことですね。
こうすることで元の配列自体に求める値がなかったとしても、追加した値がx[i]!=dateに引っかかってくれるのでループから抜け出すことができます。
なるほどねぇ
もちろん元の配列自体に求める値がある場合は
最後に追加した値にたどり着く前にループを終了します。
ちなみに番兵っていうのはWikipediaによると基地や夜戦値の出入りを警備する兵士のことらしくて、
プログラミングの場合では配列の最後にいて、無限ループから守ってくれる奴てきな意味だと思います。
コードの実装
まずはコード
#define N 5
void search_guard(int data, int x[N]){
int y[N+1];
for(int j=0; j<N; j++)
y[j] = x[j];
y[N] = data;
int i=0;
while((x[i]!=data))
i++;
if(i<N)
printf("%d番目の要素で探索成功\n",i);
else
printf("探索失敗\n");
}引数とかマクロNとかは上の線形探索のコードと一緒です。
番兵法用の配列を定義
まずは最初の部分。
int y[N+1];
for(int j=0; j<N; j++)
y[j] = x[j];
y[N] = data;番兵法用に長さN+1の配列yを定義。
そのあとはfor文を用いて配列xのN-1番目の要素までコピーします。
最後のN番目の要素は番兵としてdateを代入して完成です。
while文
int i=0;
while((x[i]!=data))
i++;先ほど説明した通り、条件式をx[i]!=dataのみにしています。
判定文
if(i<N)
printf("%d番目の要素で探索成功\n",i);
else
printf("探索失敗\n");ここは上で説明した線形探索と全く一緒ですね。
これで完成です！！
まとめ
これで番兵法の解説を終わります。
まあ発想はなかなか思いつかないですが、やっていることは超簡単ですよね。
今回は説明のためN=5としましたが、
番兵法のパワーが発揮されるのはもっとNが大きい時ですね。
課題などでも扱われやすいと思うので是非この記事のコードを参考にしてください。
ではまた！
コメント