番兵の有無による線形探索法の速度の変化

はじめに

学部時代は、情報科学系を専攻していなかったので、ここ最近アルゴリズムの勉強しています。ある教材に、線形探索を行う時、番兵を入れることで探索時間の削減に繋がると書いてあったので、その実験を行いました。

前提

使用する PC は、以下に示します。

PC

機種：MacBook Air
チップ：M1
メモリ：8 GB

概要

二つの画像は配列 $A$ の画像で、長さは $5$ です。
上の画像が通常の線形探索法の画像です。線形探索法では、$A[1]$ から順に $A[5]$ まで探索対象かどうかを比較して、「探索対象が見つかった」あるいは「繰り返し処理の回数が配列の長さより多くなった」時に、探索は終了します。
下の画像は、番兵を追加した線形探索法です。この方法は、配列の末尾に探索対象を追加する方法です。今回の場合、$A[6]$ に探索対象を追加します。探索対象が見つかったら、終了です。

実験のルール

配列はランダムに生成（最小値：$-1000000$、最大値：$1000000$）
探索対象はランダムに選定（$10$ 個）
$10$ 個の探索にかかった時間の平均を算出

ソースコード

使用する言語は Python で実験しています。
実験に使用したソースコードは、以下の通りです。（シード値の固定などは行っていないので、再現性はないです。）

import random
import time
import pandas as pd
import matplotlib.pyplot as plt

def linear_search(A, target, sentinel=False):
    i = 0
    n = len(A)  # リストの長さを取得
    while True:
        if i == n and not sentinel:
            return -1  # 見つからなかった場合
        if target == A[i]:
            return i
        i += 1

k = 10
n_list = [10, 100, 1000, 10000, 100000, 1000000]
minimum = -1000000
maximum = 1000000

# 記録用データフレーム
df_without_sentinel = pd.DataFrame(columns=["n", "trial", "time"])
df_with_sentinel = pd.DataFrame(columns=["n", "trial", "time"])

# 記録用リスト
records_without_sentinel = []
records_with_sentinel = []

for n in n_list:
    for i in range(k):
        A = random.sample(range(minimum, maximum + 1), n)
        target = random.randint(minimum, maximum) # 探索対象
        # 番兵なし
        start = time.perf_counter()
        linear_search(A, target, sentinel=False)
        end = time.perf_counter()
        records_without_sentinel.append({"n": n, "trial": i+1, "time": end - start})
        # 番兵あり
        A.append(target)
        start = time.perf_counter()
        linear_search(A, target, sentinel=True)
        end = time.perf_counter()
        records_with_sentinel.append({"n": n, "trial": i+1, "time": end - start})

# データフレームに変換
df_without_sentinel = pd.DataFrame(records_without_sentinel)
df_with_sentinel = pd.DataFrame(records_with_sentinel)

mean_without_sentinel = df_without_sentinel.groupby("n")["time"].mean()
mean_with_sentinel = df_with_sentinel.groupby("n")["time"].mean()

plt.plot(mean_without_sentinel.index, mean_without_sentinel.values, marker='o', linestyle='-', label="Without Sentinel")
plt.plot(mean_with_sentinel.index, mean_with_sentinel.values, marker='s', linestyle='--', label="With Sentinel")

# plt.xscale("log")
# plt.yscale("log")
plt.xlabel("n")
plt.ylabel("time")
plt.legend()
plt.show()

番兵ありの方が探索時間は短いという結果が得られました。今回は、$k=10$、すなわち $10$ 回の実験の平均を使っています。一つ一つのデータに着目すると、バラツキがあるはずなので、誤差バーも合わせて表示します。

std_without_sentinel = df_without_sentinel.groupby("n")["time"].std()
std_with_sentinel = df_with_sentinel.groupby("n")["time"].std()

plt.errorbar(mean_without_sentinel.index, mean_without_sentinel.values, yerr=std_without_sentinel.values, marker='o', linestyle='-', label="Without Sentinel", capsize=5)
plt.errorbar(mean_with_sentinel.index, mean_with_sentinel.values, yerr=std_with_sentinel.values, marker='s', linestyle='--', label="With Sentinel", capsize=5)
# plt.xscale("log")
# plt.yscale("log")
plt.xlabel("n")
plt.ylabel("time")
plt.legend()
plt.show()

今回の実験だと、探索対象となる値の幅が広く、$n=10$ などの時、ほぼ発見できないと思われるから、少しだけコードを改良して再度実験します。変更内容は、最小値を $-n$、最大値を $n$ に変更しました。つまり、$n=10$の時は、生成されるリスト $A$ は $-10$ から $10$ の間です。

k = 10
n_list = [10, 100, 1000, 10000, 100000, 1000000]

# 記録用データフレーム
df_without_sentinel = pd.DataFrame(columns=["n", "trial", "time"])
df_with_sentinel = pd.DataFrame(columns=["n", "trial", "time"])

# 記録用リスト
records_without_sentinel = []
records_with_sentinel = []

for n in n_list:
    for i in range(k):
        A = random.sample(range(-n, n+1), n)
        target = random.randint(n, n) # 探索対象
        # 番兵なし
        start = time.perf_counter()
        linear_search(A, target, sentinel=False)
        end = time.perf_counter()
        records_without_sentinel.append({"n": n, "trial": i+1, "time": end - start})
        # 番兵あり
        A.append(target)
        start = time.perf_counter()
        linear_search(A, target, sentinel=True)
        end = time.perf_counter()
        records_with_sentinel.append({"n": n, "trial": i+1, "time": end - start})

# データフレームに変換
df_without_sentinel = pd.DataFrame(records_without_sentinel)
df_with_sentinel = pd.DataFrame(records_with_sentinel)

この実験でも誤差バーを追加して表示します。

二つの実験の誤差バー付きの両軸対数グラフから番兵ありが安定して誤差バーの長さが抑えられている。（もちろん、対数グラフなので、縦軸の正の方向に行くほど、誤差バーの範囲自体は大きくなっている。）
番兵がない場合、誤差バーの長さが番兵がある場合と同じ程度の場合もあるが、ところどころ目に見て、誤差の範囲が広いところがあることが分かる。
※ 本来は、検定などの統計学に基づいてこの結果が有意かどうかを検証するべきですが、今回は割愛します。ごめんなさい。

特別な事情がない限り、番兵は使った方が良いと言える。

おわりに

今後もこんな感じで実験しながら勉強していきます。私と同じように勉強している人、一緒に頑張りましょう。