Python標準ライブラリbisectで二分探索の動作を見る・簡易速度計測

まとめ:
純粋に二分探索の動作、O(logN)回で取得、1万件データ時で0.30us/1回のアクセス速度。

bisectの二分探索の動作を見る

(はじめに : bisectを用いる簡易的なテストコード)

試行コード.py

import bisect, time

# bisectの試行
def run__main1():
    
    a = list(range(10))

    print(a)
    # 出力: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    i = bisect.bisect(a, 3.5)

    print(i)
    # 出力: 4

listへのアクセスを見る

試行コード.py

# bisectの試行 listへのアクセスを見る
def run__main2():
    # log2(10) = 3.32... < 4回以下のアクセス回数で要素位置を見つけられる
    
    a = list(range(10))

    print(a)
    # 出力: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    a_vis = VisibleList(a)

    i = bisect.bisect(a_vis, 3.5)
    # 出力: 
    # access: a[5] -> 5
    # access: a[2] -> 2
    # access: a[4] -> 4
    # access: a[3] -> 3

    print(i)
    # 出力: 4

    i = bisect.bisect(a_vis, 8.5)
    # 出力: 
    # access: a[5] -> 5
    # access: a[8] -> 8
    # access: a[9] -> 9

    print(i)
    # 出力: 9

# listへのアクセスをprintする
class VisibleList:
    
    def __init__(self, a):
        self.a = a
    
    def __len__(self):
        return len(self.a)

    def __getitem__(self, i):
        print(f"access: a[{i}] -> {self.a[i]}")
        return self.a[i]

listへのアクセスを見る : 1万件の場合

試行コード.py

# bisectの試行 listへのアクセスを見る 1万件の場合
def run__main3():
    # log2(10000) = 13.28... < 14回以下のアクセス回数で要素位置を見つけられる

    a = list(range(10000))

    a_vis = VisibleList(a)

    i = bisect.bisect(a_vis, 3.5)
    # 出力: 
    # access: a[5000] -> 5000
    # access: a[2500] -> 2500
    # access: a[1250] -> 1250
    # access: a[625] -> 625
    # access: a[312] -> 312
    # access: a[156] -> 156
    # access: a[78] -> 78
    # access: a[39] -> 39
    # access: a[19] -> 19
    # access: a[9] -> 9
    # access: a[4] -> 4
    # access: a[2] -> 2
    # access: a[3] -> 3

    print(i)
    # 出力: 4

    i = bisect.bisect(a_vis, 8.5)
    # 出力: 
    # access: a[5000] -> 5000
    # access: a[2500] -> 2500
    # access: a[1250] -> 1250
    # access: a[625] -> 625
    # access: a[312] -> 312
    # access: a[156] -> 156
    # access: a[78] -> 78
    # access: a[39] -> 39
    # access: a[19] -> 19
    # access: a[9] -> 9
    # access: a[4] -> 4
    # access: a[7] -> 7
    # access: a[8] -> 8

    print(i)
    # 出力: 9

    i = bisect.bisect(a_vis, 4999)
    # 出力: 
    # access: a[5000] -> 5000
    # access: a[2500] -> 2500
    # access: a[3750] -> 3750
    # access: a[4375] -> 4375
    # access: a[4688] -> 4688
    # access: a[4844] -> 4844
    # access: a[4922] -> 4922
    # access: a[4961] -> 4961
    # access: a[4981] -> 4981
    # access: a[4991] -> 4991
    # access: a[4996] -> 4996
    # access: a[4998] -> 4998
    # access: a[4999] -> 4999

    print(i)
    # 出力: 5000

    i = bisect.bisect(a_vis, 5000)
    # 出力: 
    # access: a[5000] -> 5000
    # access: a[7500] -> 7500
    # access: a[6250] -> 6250
    # access: a[5625] -> 5625
    # access: a[5313] -> 5313
    # access: a[5157] -> 5157
    # access: a[5079] -> 5079
    # access: a[5040] -> 5040
    # access: a[5020] -> 5020
    # access: a[5010] -> 5010
    # access: a[5005] -> 5005
    # access: a[5003] -> 5003
    # access: a[5002] -> 5002
    # access: a[5001] -> 5001

    print(i)
    # 出力: 5001

簡易的な速度計測 (1万件データ時)

試行コード.py

# bisectの処理時間を測定
def run__main4():
    # bisect.bisect: 1万回で約0.0030s、0.30us/1回(1万件データ時)
    # (参考比較用 for文, +, %: 1万回で約0.00047s、0.047us/1回)
    
    # sec: 同じ位置へアクセス
    
    a = list(range(10000))
    
    t_0 = time.perf_counter()
    
    for j in range(10000):
        i = bisect.bisect(a, 3.5) # 同じ位置へアクセス

    t_1 = time.perf_counter()
    
    print(i)
    # 出力: 4
    print(t_1 - t_0)
    # 出力: 0.003071

    # sec: 順番にアクセス
    
    t_0 = time.perf_counter()
    
    for j in range(10000):
        i = bisect.bisect(a, j) # 順番にアクセス

    t_1 = time.perf_counter()
    
    print(i)
    # 出力: 10000
    print(t_1 - t_0)
    # 出力: 0.002024

    # sec: 疑似的にランダムなアクセス
    
    t_0 = time.perf_counter()
    
    i = 0
    for j in range(10000):
        i = bisect.bisect(a, (j + i) % 10000) # 疑似的にランダムなアクセス

    t_1 = time.perf_counter()
    
    print(i)
    # 出力: 5000
    print(t_1 - t_0)
    # 出力: 0.003031

    # sec: 参考比較用
    
    t_0 = time.perf_counter()
    
    i = 0
    for j in range(10000):
        i = (j + i) % 10000 # 参考比較用

    t_1 = time.perf_counter()
    
    print(i)
    # 出力: 5000
    print(t_1 - t_0)
    # 出力: 0.000474

参照

Python標準ライブラリ：順序維持のbisect
https://qiita.com/ta7uw/items/d6d8f0ddb215c3677cd3

Pythonで二分探索を行うライブラリ「bisect」
https://qiita.com/T_Wakasugi/items/c979e977f56531942de4

[Python]二分探索(bisect)　ABC143D
https://qiita.com/tefuxu/items/51c25d91bec7680697f5