Python でソートされたリストを高速に検索する

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

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

もしリストがソートされているなら、より高速に検索する方法があります。 Python の公式マニュアルにソートされたリストを高速に検索する関数のサンプルコードが書かれていたので、ご紹介いたします。

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 標準ライブラリ

bisect モジュールを使うとソートされたリストを高速に検索できる index 関数を、簡単に書くことができます。

index 関数を利用して [1, 3, 5, 9, 11, 20, 31] というリストについて 11 がある位置を求めると処理を書いています。

bisect とは何者でしょうか？それは追ってご紹介いたします。
8.6. bisect 配列二分法アルゴリズム - Python 標準ライブラリ

◯ 本当に速いの？

速いです。

>>> end1 - start1
0.0005290508270263672
>>> 
...
>>> end2 - start2
0.0020699501037597656
>>> 

from bisect import bisect_left
import random
import time

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 = [random.randint(0, 99999) for _ in range(100000)]
lst.sort()
value = lst[50000]

start1 = time.time()
index(lst, value)
end1 = time.time()
end1 - start1


start2 = time.time()
lst.index(value)
end2 = time.time()
end2 - start2

◯ なんで速いの？

二分探索 を利用しているから。 bisect はこの二分探索を提供してくれるモジュールになります。 感動的にわかりやすいワクワクアカデミーの動画をご紹介します。

◯ bisect_left

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

from bisect import bisect_left

lst = [1, 3, 7, 9, 11]
lst.insert(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 のソースコード

簡略化したものを貼り付けます。ひたすら半分にし続けているだけであることがなんとなくわかります。

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

https://github.com/python/cpython/blob/3.6/Lib/bisect.py

◯ 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 という標準モジュールの２つを紹介しました。

二分探索木のご紹介

二分探索は、アルゴリズムです。また、二分探索木というデータ構造があります。 二分探索木は、もっとも基本的なデータ構造の１つになります。

二分探索を使えば同じことができてしまうので、 みなさんが直接、二分探索木を作って嬉しいことはないかなと思います。

しかし、二分探索木は、木というデータ構造の基礎になるものです。 例えば、二分探索木を応用した B 木 B-tree などはデータベースの世界で活用されています。

この対数化を実現しているのが、実は SQL のインデックスで使われている B-tree というアルゴリズムで、 このインデックスがあるがゆえに、 テーブルの行数が 10 倍、1 万倍、1 億倍になっても性能は 1 億分の 1 ではなく 8 分の 1 ぐらいのおだやかな性能劣化で収まるのです。 こういう圧倒的なパワーこそがサイエンスと呼ぶにふさわしいものです。
MongoDB の様な NoSQL に勢いがあるのは何故ですか？SQLと比べてどんな利点や欠点がありますか？

せっかくの機会なので、ご紹介させていただきたいと思います。