センチネル・サーチは、順次格納されるアイテムのリストに対する検索アルゴリズムです。
この記事では、このアルゴリズムがどのように動作するかを学び、線形探索と比較し、このアルゴリズムを使って動作するかどうかを確認することにします。
Pre-Requisite: 線形探索
センチネル・サーチに進む前に、なぜセンチネル・サーチが存在するのかを理解する必要があります。
そのためには、まず線形サーチを理解する必要があります。
線形探索では、リストの各項目を線形に調べ、ターゲットと比較し、最終的に必要な項目が見つかるか、見つからないかのどちらかです。
このプロセスでは、繰り返しごとに2つの比較を行います。
最初の比較はリストが終わっているかどうか、2つ目の比較は現在の項目がターゲットと一致するかどうかです。
しかし、これらの比較を減らして、検索を高速化する方法があるとしたらどうでしょう。
それがセンチネル・サーチの意図するところです。
Sentinel Searchとは？
センチネル・サーチは、線形探索と同様に、逐次探索アルゴリズムです。
つまり、リストの各項目を1つずつ比較するのです。
しかし、このアルゴリズムは比較の回数を減らすことができるため、線形探索よりも高速に実行できます。
センチネル・サーチでは、まずターゲットをリストの末尾に挿入し、次に必要なアイテムが見つかるまでリストの各アイテムを比較します。
必要な項目がリストの中にあるか、その場合はリストの末尾に到達する前に見つかります。
あるいは、リストには目的の項目がないので、アルゴリズムはリストの末尾に到達し、挿入した目的の項目を見つけます。
ここでは、項目がターゲットに一致するかどうかだけをチェックすればよく、リストが空かどうかをチェックする必要はありません。
なぜなら、いずれにせよターゲットを見つけてループから抜け出すつもりだからです。
最後に、見つかった項目がすでにあったのか、それとも私たちが追加したものなのかをチェックすることができます。
このチェックは一度だけ行われ、ループの繰り返しで行う比較が一つ減るので、アルゴリズム全体の実行時間は大幅に短縮されます。
Pythonによるセンチネル・サーチの実装
Pythonで書かれたセンチネル・サーチを見てみましょう。
def sentinel(lst, target):
size = len(lst)
lst.append(target)
i = 0
while(lst[i] != target):
i += 1
if(i == size):
return None
else:
return i
|
上記のコードでは、まずリストのサイズを取得し、リストの末尾にターゲットを追加しています。
その後、現在のアイテムがターゲットと同じかどうかをチェックするwhileループを開始します。
ターゲットを最後に置いたので、ループは確実に終了します。
最後に、最後の要素で終わったかどうかをチェックします。
もしそうなら、ターゲットはリストに存在しないことになり、そうでなければ、存在することになる。
そして、それに応じて適切な値を返す。
この記事もチェック：Pythonによるバイナリサーチ(二分探索)をwhile文を使って実装する
出力
このコードを実行して、どのように動作するかを見てみましょう。
まとめ
この記事では、センチネル探索とは何か、なぜそれを使うのか、線形探索との違い、pythonでの実装、そして最後にその出力について見てきました。
次のチュートリアルでお会いしましょう。
この記事もチェック：Pythonによる線形探索の実装をコードを交えて分かりやすく解説する