【Python】番兵法【アルゴリズム】

Pythonでアルゴリズムの番兵法の解説をします。

番兵法

線形探索では繰り返しのたびに2つの終了条件をチェックします。

配列の要素が少なければ問題ないですが1万とかになるとかなりのコストになります。

このコストを約半分に削減するのが番兵法(ばんぺいほう)(sentinel method)です。

番兵法を使って配列aである4、1、5、3、6、3、7から3を探索します。

番兵法では最初に探索する値を配列の末尾に追加します。

それから線形探索で目的の値であるキーを探します。

この場合は末尾であるa[7]にキー3を追加しています。

a[3]でキー3が見つかります。

次に番兵法を使って同じ配列aから2を探索します。

この場合は末尾であるa[7]にキー2を追加しています。

a[7]でキー2が見つかります。

配列内のa[0]からa[6]の要素は本来のデータで、末尾のa[7]は探索の準備で追加した番兵です。

したがって本来の配列にはキーが存在しないことがわかります。

2つの例では番兵法の準備として以下のことをしています。

2つ目の例のように配列に探索する値が存在しなくてもa[7]の番兵で探索する値が見つかります。

これにより線形探索の終了条件の1つである「探索する値と等しい値を見つけた(a[i] == key)」が必ず成立します。

よってもう一つの終了条件の「探索する値が見つからず終端を通り越しそうになった(i == len(a))」の判定が不要になります。

これにより線形探索よりも判定のコストが抑えられます。

番兵法を用いて線形探索を修正したプログラムは以下の通りです。

線形探索(番兵法)のソースコード

コード例

# 線形探索(番兵法)

from typing import Any, Sequence
import copy

def linear_search(seq: Sequence, key: Any) -> int:
    """シーケンスseqからkeyと等価な要素の線形探索(番兵法)"""
    a = copy.deepcopy(seq) # seqをディープコピー
    a.append(key)          # 番兵を追加

    i = 0

    while True:
        if a[i] == key:
            break  # 探索成功
        i += 1
    return -1 if i == len(seq) else i

if __name__ == '__main__':
    num = int(input('要素数 : '))
    x = [None] * num  # 要素数numの配列を生成

    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))

    search_key = int(input('探す値 : ')) # キーsearch_keyの読み込み

    idx = linear_search(x, search_key) # xからsearch_keyと等価な要素を探索

    if idx == -1:
        print('その値の要素は存在しません。')
    else:
        print(f'{search_key}はx[{idx}]にあります。')

実行結果(探索成功)

要素数 : 7
x[0] : 4
x[1] : 1
x[2] : 5
x[3] : 3
x[4] : 6
x[5] : 3
x[6] : 7
探す値 : 3
3はx[3]にあります。

実行結果(探索失敗)

要素数 : 7
x[0] : 4
x[1] : 1
x[2] : 5
x[3] : 3
x[4] : 6
x[5] : 3
x[6] : 7
探す値 : 2
その値の要素は存在しません。

関数linear_searchは配列seqのディープコピーをaに格納します。

そのaに番兵としてkeyを追加して本来の配列の後ろに番兵を追加した探索用の配列が完成します。

iを0で初期化しwhile文ではa[i]を先頭から順番に探索していきます。

その過程でキーと同じ値が見つかったらbreak文によりwhile文を抜けます。

番兵が追加されているためここではif i == len(a):の判定はなくなります。

次の要素を探索するためにiの値を1だけインクリメントします。

while文の繰り返しが終わった後は見つけたのが配列の本来の値なのか、番兵なのかの判別が必要になります。

そこで変数iの値を調べてlen(seq)と同じになれば見つけたのが番兵なので探索失敗を表す-1を返します。

len(a)だと番兵を追加した配列の要素の長さになるので本来の配列の長さであるlen(seq)で調べます。

配列の最後の要素のインデックス値は要素数-1であることに注意してください。

実行例だと番兵が追加されているのが添え字7の要素なのでiがlen(seq)つまり7なら探索失敗です。

番兵でない場合はどの要素で見つけたのかを表すiの値を返します。

while文内での判定は半分に減りましたが最後に番兵かどうかを判定する1回が追加されています。