# 二分探索

# 標準ライブラリ bisect

二分探索を使うとソートされたリストを高速に探索することができます。 二分探索を支援してくれるライブラリ bisect があります。

from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left
from bisect import insort
from bisect import insort_right
from bisect import insort_left


lst = [0, 3, 3, 3, 5]

# bisect
#   値をリストに
#   差し込む位置を返してくれます。
bisect(         lst, 3)  # 4
bisect_right(   lst, 3)  # 4
bisect_left(    lst, 3)  # 1


# insort
#   値をリストに
#   差し込んでくれます。
insort(         lst, 3)
insort_right(   lst, 3)
insort_left(    lst, 3)

重複した値があった場合、bisect_right は右側の位置を bisect_left は左側の位置を返してくれます。 bisect_rightbisect は同じものです。

insort は基本的に bisect で位置を探して list.insert メソッドで値を差し込むということをしています。

from bisect import bisect
lst = [0, 3, 3, 3, 5]
lst.insert(bisect(lst, 3), 3)
assert lst == [0, 3, 3, 3, 3, 5]

# bisect で二分探索

もしリストがソートされているなら、より高速に検索する方法があります。 それが上の動画で紹介されている二分探索です。

標準ライブラリ bisect を使うとソートされたリストを高速に検索できる二分探索 index 関数を、簡単に書くことができます。

from bisect import bisect_left


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


lst = [1, 3, 5, 9, 11, 20, 31]
index(lst, 11)  # 4
8.6.1. ソート済みリストの探索 - Python 標準ライブラリ

上記のコードでは index 関数を利用して [1, 3, 5, 9, 11, 20, 31] という リストについて 11 がある位置を求めると処理を書いています。 ここからは標準ライブラリ bisect にはいっている関数を ご紹介致します。

# bisect_left 関数

bisect_left 関数は、ソートを崩さないように、新しい要素を挿入する位置を検索する関数です。 上で紹介した index 関数は、既存の要素を検索するように書き直した関数です。

import bisect

lst = [1, 3, 7, 9, 11]
lst.insert(bisect.bisect_left(lst, 8), 8)
lst  # [1, 3, 7, 8, 9, 11]

bisect.bisect_left(a, x, lo=0, hi=len(a))
ソートされた順序を保ったまま x を a に挿入できる点を探し当て

# ◯ bisect_left のソースコード

簡略化したものを貼り付けます。 ひたすら半分にし続けているだけであることがなんとなくわかります。 lo は low, hi は high をそれぞれ略したものだと思われます。

def bisect_left(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo
python/cpython/Lib/bisect.py - GitHub

ちなみに実際に import したときには C 言語で実装されたものが import されています。

# Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass
python/cpython/Lib/bisect.py - GitHub

標準ライブラリ bisect のソースコードは、 標準ライブラリの中でも特に短く簡単なコードなので、 ぜひ直接読んで見てもいいかなと感じたりもします。

GitHub のリンクからも確認できますし、 あるいは特殊属性 __file__ からファイルパスを確認することができます。

>>> import bisect
>>> bisect.__file__
'/usr/local/Cellar/python/3.7.2_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/bisect.py'
>>> 

標準ライブラリと仲良くなることも、このカテゴリ「アルゴリズム」の目標でもあります。

# insrot_left 関数

ソートされたリストに新しく値を挿入したい場合は insort_left を使った方が便利です。

import bisect
lst = [1, 3, 7, 9, 11]
# lst.insert(bisect.bisect_left(lst, 8), 8)
bisect.insort_left(lst, 8)
lst  # [1, 3, 7, 8, 9, 11]

# bisect_right 関数

bisect_left があるなら bisect_right もあるの? あります。同じ値が複数あるリストで意味があります。 bisect_left は左端の bisect_right は右端の位置を返します。

from bisect import bisect_left
from bisect import bisect_right

lst = [0, 1, 3, 3, 3, 5, 6]
bisect_left(lst, 3)   # 2
bisect_right(lst, 3)  # 5

ちなみに bisect_rightbisect でも呼び出せます。

from bisect import bisect, bisect_right
bisect is bisect_right  # True

# insrot_right 関数

同じく insort_right 関数もあります。 insort_right 関数は insort でも呼び出せます。

# 本当に速いの?

速いです。

# 1. list.index 関数

>>> timeit.timeit('lst.index(value0)', globals=globals())
0.17925353700002233
>>> timeit.timeit('lst.index(value1)', globals=globals())
4.7704678539998895
>>> timeit.timeit('lst.index(value2)', globals=globals())
9.357747213000039
>>> timeit.timeit('lst.index(value3)', globals=globals())
14.830968766000069
>>> timeit.timeit('lst.index(value4)', globals=globals())
18.41838743800008
>>> 

# 2. index 関数

>>> timeit.timeit('index(lst, value0)', globals=globals())
0.8878458670001237
>>> timeit.timeit('index(lst, value1)', globals=globals())
0.8281808429999273
>>> timeit.timeit('index(lst, value2)', globals=globals())
0.9421129969998674
>>> timeit.timeit('index(lst, value3)', globals=globals())
0.9537168950000705
>>> timeit.timeit('index(lst, value4)', globals=globals())
0.9572374409999611
>>> 

# 3. お前は、なにを計測したんだ?

1001 個の整数をランダムに生成してソートしたリストを検索しました。 検索対象として先頭の値と末尾の値から等間隔に5つ取り出したものを使用しています。

#
# 対話モード >>> に
# コピペで実行できます。
#
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())

Python のリストには要素を検索する list.index メソッドがあります。

>>> [1, 4, 5, 7].index(5)
2
>>> 

この list.index メソッドは、先頭から順番に リストにはいっているオブジェクトを調べています。

先頭から順番に調べることを難しい言葉で 線形探索 と言います。 list.index メソッドの場合、線形探索なので後ろに行けば行くほど遅くなっています。

# まとめ

二分探索というアルゴリズムと bisect という標準モジュールの2つを紹介しました。