# 二分探索と bisect
# 1. 二分探索
二分探索を使うとソートされたリストを高速に探索することができます。 残念ながら Python の標準ライブラリには二分探索そのものの実装はありません。
しかし、二分探索を支援してくれる標準ライブラリ bisect があります。 公式ドキュメントの中に bisect を使った実装があったので、これを少し書き換え引用します。
#
# 対話モード >>> に
# コピペで実行できます。
#
from bisect import bisect_left
# def 二分探索(リスト, 要素)
def index(lst, e):
# Step 1. bisect_left して
i = bisect_left(lst, e)
# Step 2. 変な値を ValueError で弾いて
if i == len(lst):
raise ValueError
if lst[i] != e:
raise ValueError
# Step 3. 値を返す。
return i
lst = [7, 31, 41, 78, 91]
index(lst, 7)
index(lst, 31)
index(lst, 41)
index(lst, 78)
index(lst, 91)
>>> index(lst, 7)
0
>>> index(lst, 31)
1
>>> index(lst, 41)
2
>>> index(lst, 78)
3
>>> index(lst, 91)
4
>>>
パッと見ると index 関数は bisect_left(リスト, 要素) だけしかしていないように見えます。
なぜ ValueError を投げる条件分岐が必要なのでしょうか？
それは bisect_left 関数は、引数に与えられた要素がいる位置を返す関数ではないからです。
bisect_left 関数は、
リストのソートを崩さずに、新しい要素を差し込める位置
を返す関数だからです。
この記事では標準ライブラリ bisect を俯瞰しつつ、
少しずつ掘り下げ、最終的に bisect_left 関数の実装を見ることで二分探索の実装について考えていきます。
# 2. 標準ライブラリ bisect - 概要
# 2.1. insort 関数
ソートを保ったまま、リストに要素を差し込んでくれます。
from bisect import insort
lst = [7, 31, 41, 78, 91]
insort(lst, 6)
insort(lst, 21)
insort(lst, 39)
insort(lst, 68)
insort(lst, 81)
insort(lst, 99)
lst
>>> lst
[6, 7, 21, 31, 39, 41, 68, 78, 81, 91, 99]
>>>
# 2.2. bisect 関数
ソートを保ったまま、リストに要素を差し込む位置を返してくれます。
from bisect import insort
lst = [7, 31, 41, 78, 91]
bisect(lst, 6)
bisect(lst, 21)
bisect(lst, 39)
bisect(lst, 68)
bisect(lst, 81)
bisect(lst, 99)
>>> bisect(lst, 6)
0
>>> bisect(lst, 21)
1
>>> bisect(lst, 39)
2
>>> bisect(lst, 68)
3
>>> bisect(lst, 81)
4
>>> bisect(lst, 99)
5
>>>
# 3. 標準ライブラリ bisect - 詳細
# 3.1. insort 関数
insort と insort_right は同じものです。
重複した値があった場合、insort_right は右側に
insort_left は左側に要素を差し込みます。
# insort
# ソートを保ったまま
# 要素をリストに
# 差し込んでくれます。
from bisect import insort
from bisect import insort_right
from bisect import insort_left
lst = [0, 3, 3, 3, 5]
insort( lst, 3)
insort_right(lst, 3)
insort_left( lst, 3)
lst
# [0, 3, 3, 3, 3, 3, 3, 5]
>>> lst
[0, 3, 3, 3, 3, 3, 3, 5]
>>>
# 3.2. bisect 関数
bisect と bisect_right は同じものです。
重複した値があった場合、bisect_right は右側の位置を
bisect_left は左側の位置を返してくれます。
# bisect
# ソートを保ったまま
# 要素をリストに
# 差し込む位置を返してくれます。
from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left
lst = [0, 3, 3, 3, 5]
bisect( lst, 3)
bisect_right(lst, 3)
bisect_left( lst, 3)
>>> bisect( lst, 3)
4
>>> bisect_right(lst, 3)
4
>>> bisect_left( lst, 3)
1
>>>
# 4. ソースコード
bisect のソースコードは GitHub のリンクからも確認できます。
あるいは特殊属性 __file__ からファイルパスを確認することができます。
import bisect
bisect.__file__
>>> bisect.__file__
'/usr/local/Cellar/python/3.7.2_2/Frameworks/Python.framework/Versions/3.7/lib/python3.7/bisect.py'
>>>
標準ライブラリと仲良くなることも、このカテゴリ「アルゴリズム」の目標でもあります。
# 4.1. insort と insort_right, bisect と bisect_right
insort と insort_right, bisect と bisect_right は同じものです。
単純に代入しているだけです。
# Create aliases
bisect = bisect_right
insort = insort_right
# 4.2. insort_left
insort_left は、コメント、空行を覗ければ実質２行しかありません。
bisect_left を呼び出して位置を検索して、
得られた位置に list.insert を使って差し込んでいるだけです。
def insort_left(a, x, lo=0, hi=None):
...
lo = bisect_left(a, x, lo, hi)
a.insert(lo, x)
# 4.3. bisect_left
少し長いので 5 章に記述します。
# ◯ ちなみに...
ちなみに実際に import したときには C 言語で実装されたものが import されています。
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
except ImportError:
pass
C 言語で書かれたものは、こちらにあります。 中身は、あまりよくわかっていません。
# 5. ソースコード - bisect_left
# 5.1. 全体のコード
少し長いとは言ってもそんなに長くはありません。
def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
# 5.2. 簡略化したコード
オプショナル引数の lo, hi とコメントを削除して、簡略化します。
ひたすら半分にし続けているだけであることがなんとなくわかります。
lo は low, hi は high をそれぞれ略したものだと思われます。
def bisect_left(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
print_progress(a, lo, mid, hi)
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
# 5.3. 実行結果を表示
以下のコードを対話モード >>> にコピペして実行して見てください。
雰囲気がつかめるかなと思います。
def bisect_left(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
print_progress(a, lo, mid, hi)
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def print_progress(lst, lo, mid, hi):
print(' '.join(f'{e:2d}' for e in lst))
print(' '.join(progress(lst, lo, mid, hi)))
print()
def progress(lst, lo, mid, hi):
prog = [' '] * (len(lst) + 1)
# print(lo, mid, hi)
prog[lo], prog[mid], prog[hi]\
= 'lo', 'mi', 'hi'
return prog
def main():
from random import randint
N = 15
lst = [randint(0, 99) for i in range(N)]
lst.sort()
i_ = randint(0, N - 1)
print(f"{str(lst[i_])} を検索します。")
i = bisect_left(lst, lst[i_])
print(f"{str(lst[i_])} は 0 から数えて {i} 番目にあります。")
main()
>>> main()
63 を検索します。
0 9 13 14 22 27 35 51 63 75 77 83 88 99 99
lo mi hi
0 9 13 14 22 27 35 51 63 75 77 83 88 99 99
lo mi hi
0 9 13 14 22 27 35 51 63 75 77 83 88 99 99
lo mi hi
0 9 13 14 22 27 35 51 63 75 77 83 88 99 99
mi hi
63 は 0 から数えて 8 番目にあります。
>>>
>>> main()
32 を検索します。
6 8 9 14 22 29 32 34 41 49 82 95 96 97 97
lo mi hi
6 8 9 14 22 29 32 34 41 49 82 95 96 97 97
lo mi hi
6 8 9 14 22 29 32 34 41 49 82 95 96 97 97
lo mi hi
6 8 9 14 22 29 32 34 41 49 82 95 96 97 97
mi hi
32 は 0 から数えて 6 番目にあります。
>>>
# 6. 計測 - 本当に速いの？
速いです。1001 個の整数をランダムに生成してソートしたリストを検索させました。 検索対象として先頭の値と末尾の値から等間隔に５つ取り出したものを使用しています。
# 6.1. 二分探索 - 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
>>>
# 6.2. 線形探索 - 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
>>>
# ◯ 線形探索
今更ながらですが Python のリストには要素を検索する list.index メソッドがあります。
>>> [1, 4, 5, 7].index(5)
2
>>>
この list.index メソッドは、先頭から順番に、リストにはいっているオブジェクトを調べています。
先頭から順番に調べることを難しい言葉で 線形探索 (opens new window) と言うそうです。
list.index メソッドの場合、線形探索、先頭から順番に調べているので、検索する要素が後ろにあればあるほど遅くなっています。
# おわりに
ここまで次のように見てきました。
二分探索というアルゴリズムと bisect という標準モジュールの２つを見てきました。