【アルゴリズムの基本】線形探索と番兵法
今回は繰り返し系の処理をおこなうときにつかえるアルゴリズムである、線形探索と番兵法について説明します
線形探索とは？
配列を順番に走査していき、目標がみつかったら停止するアルゴリズムのことです
プログラムは必ず停止しなければならないという決まりがあります
線形探索の場合、停止する条件は、
または（or, (| |)）
探したい値がみつかる
ということになります
それでは、上記の条件の否定をとってみましょう
つまり、
かつ (and,(&&))
探したい値が見つからない
となります
（そうです、高校数学Aでならったド・モルガン則を思い出してください）
このように否定をとった場合には、停止しない、つまり、
配列のなかをがんばって探してくださいってことになります
これがループの式（forやwhile）の反復条件になります
一般的に、よいプログラマは面倒なことをただしく面倒だと感じ、それを改善することで、ラクしようとするものだといわれています
きっとあなたは
- 配列の途中
かつ - 探したい値が見つからない
っていう条件式をたとえば
i=1
while(i＜N and A[i]!=x){
i++
}
と書いたかもしれません。これが線形探索とよばれるアルゴリズムですね
このアルゴリズムの場合、配列のループカウンタが配列の要素数を越えないかを逐一判定する必要があります
そこで、もっと処理が高速なものがいまから紹介する番兵法というアルゴリズムです
番兵法
ポイント
- 配列の最後に探したい値を追加
探したい値を配列の最後に追加？？それならいつかは絶対見つかるじゃねえか、うわチートじゃねえかとおもったひとはナイスです。この番兵法のポイントはまさにそこで、自分自身でいつかは必ず見つかるように配列を操作しているところがミソなのです。探したい値と全く同じ値を、配列の一番後ろにも置くことで、途中でみつからなかった場合にもプログラムが停止することが約束されます。
こうすることで、さきほどのwhile文で書いた反復条件式は、
こう書けます
A[N+1]=x
i=1
while(A[i]!=x){
i++
}
i＜N（Nは配列の要素数）の条件が消えて、条件式のコードが短くなりました。
なぜ消えたのかというと、番兵としてA[N+1]に探したい値を追加したからです。
そもそもi＜Nの条件がなぜ必要なのかを考えてみましょう
i＜Nがない場合には、配列のなかに探している値がなかった場合にどうなるでしょうか？そうです。反復処理が停止しませんね。無限ループになります。
しかし、番兵法をつかったアルゴリズムの場合には、A[N+1]に値を追加したので、N+1番目に来たときにはかならず反復処理が停止することが約束されています
じゃあ、具体的に番兵法は何がいいんだい？ってことですが、こちらのアルゴリズムのほうが高速に処理が行えます。その理由ですが、i＜Nの比較処理が消えたことで、単純に反復処理一回あたりにCPUが計算しなければならない量が減るからです。
つまり番兵法についてまとめると、
- 反復一回あたりの命令数が減るので、処理が高速になる
ということです
番兵さんを配列の端においたおかげです。
なぜ番兵というのかというと、配列の端っこでループカウンタが配列の要素数よりも大きくならないこと見張り番する兵隊から言われているらしいです
アルゴリズムを学びたい人へ
私はUdemyの「Data Structures & Algorithms !」でアルゴリズムとデータ構造の基礎を学びました。書籍参考書ではデータの各ステップでの状態をイメージしずらいですが、こちらは動画レクチャーなので、その点を非常にわかりやすく補足説明されていてデータの各状態のイメージが非常にしやすかったです。データ構造とアルゴリズムは難解だと言われますが、それを理解しているかどうかがエンジニアの優劣を決める要素の一つだとも思います。本格派エンジニアを目指したいなら、非常におすすめです。
今回はここまでです
ではでは！