番兵について

番兵について

線形探索の際に、探索する配列の末尾にキー値を含めることで、比較回数を減らすテクニック。

結果

番兵なし

番兵なし

========================================
cost=1: if i == N ... False
cost=2: if xs[i] == key ... False
cost=3: if i == N ... False
cost=4: if xs[i] == key ... False
cost=5: if i == N ... False
cost=6: if xs[i] == key ... False
cost=7: if i == N ... False
cost=8: if xs[i] == key ... False
cost=9: if i == N ... False
cost=10: if xs[i] == key ... False
cost=11: if i == N ... False
cost=12: if xs[i] == key ... False
cost=13: if i == N ... False
cost=14: if xs[i] == key ... False
cost=15: if i == N ... False
cost=16: if xs[i] == key ... False
cost=17: if i == N ... False
cost=18: if xs[i] == key ... False
cost=19: if i == N ... False
cost=20: if xs[i] == key ... False
cost=21: if i == N ... True

not found.
========================================

xs=[7, 8, 1, 5, 3, 4, 2, 0, 9, 6], len=10
key=-99
cost=21

コスト: 21

• 20
• 1

番兵あり

番兵あり

========================================
cost=1: if xs[i] == key ... False
cost=2: if xs[i] == key ... False
cost=3: if xs[i] == key ... False
cost=4: if xs[i] == key ... False
cost=5: if xs[i] == key ... False
cost=6: if xs[i] == key ... False
cost=7: if xs[i] == key ... False
cost=8: if xs[i] == key ... False
cost=9: if xs[i] == key ... False
cost=10: if xs[i] == key ... False
cost=11: if xs[i] == key ... True
cost=12: if i == N ... True
cost=13: xs.append(key)
cost=14: xs.pop()

not found.
========================================

xs=[7, 8, 1, 5, 3, 4, 2, 0, 9, 6], len=10
key=-99
cost=12 (cost=14)

コスト 12 (14)

• 10
• 2
• 2 (番兵の設定、解除分)

コード

番兵なし

#!/usr/bin/env python3

import random
random.seed(0)

xs = list(range(10))
random.shuffle(xs)

i = 0
N = len(xs)
# key = 2
key = -99
result = "\nnot found."

cost = 0

print("番兵なし")
print()

print("=" * 40)

while True:
    cost += 1
    print(f"{cost=}: if i == N ... {i == N}")
    if i == N:
        break

    cost += 1
    print(f"{cost=}: if xs[i] == key ... {xs[i] == key}")
    if xs[i] == key:
        result = f"\nfound! index is {i=}"
        break

    i += 1

print(result)
print("=" * 40)
print()

print(f"{xs=}, len={N}")
print(f"{key=}")
print(f"{cost=}")

番兵あり

#!/usr/bin/env python3

import random
random.seed(0)

xs = list(range(10))
random.shuffle(xs)

i = 0
N = len(xs)
# key = 2
key = -99
result = "\nnot found."

cost = 0

print("番兵あり")
print()

print("=" * 40)

# 番兵を設定
xs.append(key)

while True:
    cost += 1
    print(f"{cost=}: if xs[i] == key ... {xs[i] == key}")
    if xs[i] == key:
        break

    i += 1

cost += 1
print(f"{cost=}: if i == N ... {i == N}")
if i == N:
    pass
else:
    result = f"\nfound! index is {i=}"

# 番兵を除外
xs.pop()

cost += 1
print(f"{cost=}: xs.append(key)")
cost += 1
print(f"{cost=}: xs.pop()")

print(result)
print("=" * 40)
print()

print(f"{xs=}, len={N}")
print(f"{key=}")
print(f"cost={cost - 2} ({cost=})")