牌語備忘録 -pygo

あくまでもメモです。なるべくオフィシャルの情報を参照してください。

牌語備忘録 -pygo

『数学ガール/乱択アルゴリズム』第2章「愚直な一歩の積み重ね」の疑似コードを Python で書いて計測してみるメモ

第4巻『数学ガール/乱択アルゴリズム』

(Python2.7)

hoge.py

なるべく疑似コードに近い感じで

#!/usr/bin/env python
# coding=utf8


def linear_search(A, n, v):
    # k = 1
    k = 0
    while  k <= n:
        if A[k] == v:
            return True
        k += 1
    return False

def sentinel_linear_search(A, n, v):
    # A[n + 1] = v
    A.append(v)
    # k = 1
    k = 0
    while not A[k] == v:
        k = k + 1
    if k <= n:
        return True
    return False


if __name__ == '__main__':
    A = [31, 41, 59, 26, 53]
    n = 5
    v = 26
    print(linear_search(A, n, v))
    print(sentinel_linear_search(A, n, v))
    # print(sentinel_linear_search(A, n, 999))
    # print(sentinel_linear_search(A, n, 31))

iPython で計測してみる

$ ipython

In [9]: run hoge.py
True
True

# linear_search

In [10]: %timeit linear_search(A, n, v)
1000000 loops, best of 3: 1.14 µs per loop

In [11]: %timeit linear_search(A, n, v)
1000000 loops, best of 3: 1.14 µs per loop

# sentinel_linear_search

In [13]: %timeit sentinel_linear_search(A, n, v)
1000000 loops, best of 3: 1.16 µs per loop

In [14]: %timeit sentinel_linear_search(A, n, v)
1000000 loops, best of 3: 1.18 µs per loop

データが少な過ぎて差が小さいっぽいうえに、速くなるはずの sentinel_linear_search が若干遅いので増やしてみる

In [16]: import random

In [29]: A2 = [random.randint(1,100) for _  in range(100)]

In [30]: print(A2)
[41, 93, 38, 74, 18, 54, 39, 39, 98, 77, 9, 7, 94, 81, 46, 48, 96, 41, 79, 79, 78, 41, 26, 79, 94, 25, 55, 33, 92, 35, 39, 38, 14, 44, 22, 50, 36, 49, 10, 84, 68, 8, 84, 87, 43, 11, 99, 52, 12, 10, 82, 66, 25, 9, 41, 40, 19, 44, 63, 84, 97, 30, 50, 23, 82, 55, 15, 59, 47, 67, 84, 14, 21, 3, 63, 38, 23, 43, 98, 24, 68, 41, 55, 89, 46, 37, 93, 65, 25, 65, 81, 24, 50, 63, 76, 14, 94, 62, 53, 96]

# linear_search

In [31]: %timeit linear_search(A2, len(A2), A2[77])
100000 loops, best of 3: 10.1 µs per loop

In [32]: %timeit linear_search(A2, len(A2), A2[77])
100000 loops, best of 3: 10.6 µs per loop

# sentinel_linear_search

In [33]: %timeit sentinel_linear_search(A2, len(A2), A2[77])
100000 loops, best of 3: 7.58 µs per loop

In [34]: %timeit sentinel_linear_search(A2, len(A2), A2[77])
100000 loops, best of 3: 7.02 µs per loop

sentinel_linear_search の方が速くなった。 2章でこんなことしてたら読了までの道のりが長そうな...