番兵を用いた線形探索

Question

質問文

アルゴリズムの勉強をしているのですが、読んでいる書籍に

線形探索は「番兵」を用いた実装の工夫で定数倍の高速化が期待できます
(引用元: 渡部有隆 - プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (2015))

という記述があり実際に試してみることにしました。

1000個の異なる正の整数からなるリストの中に、無作為に選ばれたある整数が含まれるかどうか、また含まれる場合は何番目かを返す関数を2つ用意します。
1つは純粋な線形探索、もう一方は番兵付きです。
timeitを用いて100万回試したときのそれぞれの処理時間の平均を計測したのですが、予想に反して番兵アルゴリズムの方が遅いという結果になりました。

linear search: 5.852486592900002e-05
sentinel search: 7.166582232300002e-05

これがどうしてなのかが良く分かりません。
私のコードに問題があるのか、あるいはPythonではif判定を1000回行うよりもlist.append(),list.pop()を1度ずつ行う方が重いのでしょうか?

コード

from random import randint, sample
from timeit import timeit

# list of random unique integers
lst = sample(range(1, 1001), 1000)

# Linear search
def lin_search(tgt: int, lst: list):
    for i in range(len(lst)):
        if lst[i] == tgt:
            return i + 1
    else:
        return -1


# Linear search with sentinel
def lin_sentinel(tgt: int, lst: list):
    lst.append(tgt)
    i = 0
    while lst[i] != tgt:
        i += 1
    lst.pop()
    if i < len(lst):
        return i + 1
    else:
        return -1


loop = 1000000
res_1 = timeit("lin_search(randint(1, 2001), lst)", globals=globals(), number=loop)
res_2 = timeit("lin_sentinel(randint(1, 2001), lst)", globals=globals(), number=loop)
print(f"linear search: {res_1 / loop}")
print(f"sentinel search: {res_2 / loop}")

> linear search: 5.852486592900002e-05
> sentinel search: 7.166582232300002e-05

Comments

[tiitoi]

このような小手先のテクニックは Python のようなスクリプト言語でやってもあまり意味がないと思います。

Answer 1

番兵の効果を実感したいなら

from random import randint, sample

target_lst = sample(range(1, 1001), 1000)

def lin_search(tgt: int, lst: list):
    i = 0
    while i < len(lst) and lst[i] != tgt:
        i += 1
    return i


def lin_sentinel(tgt: int, lst: list):
    lst.append(tgt)
    i = 0
    while lst[i] != tgt:
        i += 1
    del lst[-1]
    return i

こう。

In : %timeit lin_search(1001, target_lst)
184 µs ± 33.2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In : %timeit lin_sentinel(1001, target_lst)
73.9 µs ± 3.69 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In : %timeit lin_search(500, target_lst)
125 µs ± 1.39 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In : %timeit lin_sentinel(500, target_lst)
50.4 µs ± 793 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

---

Pythonではfor i in iterable:がwhile cond: i+=1より速いので比較になってないのです。

def sum_for(n):
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

def sum_while(n):
    s = 0
    i = 1
    while i <= n:
        s += i
        i += 1
    return s

In : %timeit sum_for(10000)
523 µs ± 4.84 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In : %timeit sum_while(10000)
1.02 ms ± 4.92 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Comments

[退会済みユーザー]

quiquiさん、hayataka2049さん、お二人ともありがとうございます。
まさか、for文がwhileよりも速いとは思いませんでした。

Answer 2

pythonの比較と足し算は遅いので、ループカウンタをインクリメントしていくよりはrangeで生成した方が高速になります。主な敗因はそれです。

import timeit

def f1():
    for i in range(1000):
        pass

def f2():
    i = 0
    while i < 1000:
        i += 1

print(timeit.timeit(f1, number=100)/100) # 1.6771509981481357e-05
print(timeit.timeit(f2, number=100)/100) # 7.219993000035174e-05