bisect_or_linear.py

#
# 対話モード >>> に
# コピペで実行できます。
#
import bisect
import random
import timeit

#
# 1. 関数を定義
#
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

#
# 2. N + 1 個のランダムな数をソートしたリスト
#
N = 10**3
lst = sorted(
    random.randint(0, N) for _ in range(N + 1))

#
# 3. 検索対象の値を選定
#
Q = N // 4           # Quoter の Q
value0 = lst[0 * Q]  # 先頭
value1 = lst[1 * Q]
value2 = lst[2 * Q]  # 真ん中
value3 = lst[3 * Q]
value4 = lst[4 * Q]  # 末尾

# N + '1' 個にしてるのは
# こんな感じに分割できるから
#   0, 1, 2, 3, 4, 5, 6, 7, 8
#   x     x     x     x     x 



#
# 4. 計測
#
timeit.timeit('lst.index(value0)', globals=globals())
timeit.timeit('lst.index(value1)', globals=globals())
timeit.timeit('lst.index(value2)', globals=globals())
timeit.timeit('lst.index(value3)', globals=globals())
timeit.timeit('lst.index(value4)', globals=globals())

timeit.timeit('index(lst, value0)', globals=globals())
timeit.timeit('index(lst, value1)', globals=globals())
timeit.timeit('index(lst, value2)', globals=globals())
timeit.timeit('index(lst, value3)', globals=globals())
timeit.timeit('index(lst, value4)', globals=globals())