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

(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章でこんなことしてたら読了までの道のりが長そうな...