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