問題
n個の整数を含む数列 Sと、q個の異なる整数を含む数列 Tを読み込み、Tに含まれる整数の中で Sに含まれるものの個数 C出力するプログラムを作成してください。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_A
解法
1.forループを用いる方法
def linear_search(x, n_list):
for n in n_list:
if x == n:
return True
return False
S = [random.randint(1, 10000) for i in range(1000000)]
T = set([random.randint(1, 10000) for i in range(100)])
# 普通の線形探索
count = 0
start = time.time()
for t in T:
if linear_search(t, S):
count += 1
print("elapsed_time:{0}".format(time.time() - start))
print(count)
ただfor文を回して1要素ずつ比較を行う方法。
上記コードの実行時間は約0.03秒であった。
2. while文と番兵を用いる方法
def linear_search_banpei(x, n_list):
n_list.append(x)
i = 0
while x != n_list[i]:
i += 1
if i + 1 == len(n_list):
n_list.pop(-1)
return False
n_list.pop(-1)
return True
S = [random.randint(1, 10000) for i in range(1000000)]
T = set([random.randint(1, 10000) for i in range(100)])
# 番兵を用いた線形探索
count = 0
start = time.time()
for t in T:
if linear_search_banpei(t, S):
count += 1
print("elapsed_time:{0}".format(time.time() - start))
print(count)
「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」に載っていた、「番兵」となる要素をリストの最後に追加することで必ずwhile文が終わるようにし、ループ中で行う要素比較の回数を少なくすることで効率化を図る実装方法。
1のforループを用いる方法だとループの継続判定と要素の数値が同じかの2つの判定をしなければならないが、2の番兵を使う方法だとループ中で行うのがループの継続判定のみでいいため、効率的になると書いてあった。
だが実際に上記コードを動かすと、2の番兵を使った方法は0.08秒の実行時間がかかり、1の単純なforループを使った方法よりも実行に時間がかかってしまった。Pythonのリストは参照渡しであるため、2の番兵を使った方法ではいちいちリストに要素を追加したり削除したりしているのだが、恐らくここで処理に時間がかかっており、理論とは逆の結果となっているのだろう。
