質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.80%

番兵を用いた線形探索

解決済

回答 2

投稿

  • 評価
  • クリップ 4
  • VIEW 1,505

solzard

score 102

質問文

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

線形探索は「番兵」を用いた実装の工夫で定数倍の高速化が期待できます
(引用元: 渡部有隆 - プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (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
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • tiitoi

    2019/05/16 15:20

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

    キャンセル

回答 2

checkベストアンサー

+3

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

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)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/16 16:20

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

    キャンセル

+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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.80%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る