`bisect` --- 配列二分法アルゴリズム¶

ソースコード: Lib/bisect.py

このモジュールは、挿入のたびにリストをソートすることなく、ソートされた順序でリストを維持するためのサポートを提供します。コストのかかる比較演算を伴う長いリストの場合、これは線形検索や頻繁な並べ替えよりも改善される可能性があります。

基本的な二分法アルゴリズムで処理するため、このモジュールは bisect と呼ばれます。特定の値を探す他の二分探索ツールとは異なり、このモジュールの関数は挿入位置を探すように設計されています。そのため、値が見つかったかを判断するために __eq__() メソッドを呼び出すことはありません。代わりに __lt__() メソッドだけを呼び出し、配列内の値の間にある挿入位置を返します。

注釈

このモジュールの関数はスレッドセーフではありません。複数のスレッドから同じシーケンスに対して bisect の関数を同時に使うと、動作が未定義になる可能性があります。同様に、bisect の関数がシーケンスを操作している間に別のスレッドがそのシーケンスを変更した場合も、結果は未定義です。例えば、複数のスレッドから同じリストに対して insort_left() を使うと、リストのソート順が崩れる可能性があります。

次の関数が用意されています:

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)¶

ソートされた順序を保ったまま x を a に挿入できる点を探し当てます。リストの中から検索する部分集合を指定するには、パラメータの lo と hi を使います。デフォルトでは、リスト全体が使われます。x がすでに a に含まれている場合、挿入点は既存のどのエントリーよりも前(左)になります。戻り値は、list.insert() の第一引数として使うのに適しています。a はすでにソートされているものとします。

返された挿入位置 ip は、配列 a を 2 つのスライスに分割します。左側のスライスでは all(elem < x for elem in a[lo : ip]) が真となり、右側のスライスでは all(elem >= x for elem in a[ip : hi]) が真となります。

key は、配列の各要素から比較用のキーを取り出す、引数を 1 つ受け取るキー関数を指定します。複雑なレコードを検索できるように、キー関数は値 x には適用しません。

key が None の場合は要素を直接比較し、キー関数を呼び出しません。

バージョン 3.10 で変更: key パラメータが追加されました。

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)¶

bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)¶

bisect_left() と似ていますが、 a に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。

返された挿入位置 ip は、配列 a を 2 つのスライスに分割します。左側のスライスでは all(elem <= x for elem in a[lo : ip]) が真となり、右側のスライスでは all(elem > x for elem in a[ip : hi]) が真となります。

バージョン 3.10 で変更: key パラメータが追加されました。

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)¶

x を a にソート順で挿入します。

まず bisect_left() で挿入位置を探します。次に a の insert() メソッドを呼び出し、ソート順を保つ適切な位置に x を挿入します。

テーブルへのレコードの挿入に対応するため、key 関数を指定した場合は、探索の段階で x に適用し、挿入の段階では適用しません。

O(log n) の探索よりも、遅い O(n) の挿入処理が全体の実行時間を支配することに注意してください。

バージョン 3.10 で変更: key パラメータが追加されました。

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)¶

bisect.insort(a, x, lo=0, hi=len(a), *, key=None)¶

insort_left() と似ていますが、 a に含まれる x のうち、どのエントリーよりも後ろに x を挿入します。

まず bisect_right() で挿入位置を探します。次に a の insert() メソッドを呼び出し、ソート順を保つ適切な位置に x を挿入します。

テーブルへのレコードの挿入に対応するため、key 関数を指定した場合は、探索の段階で x に適用し、挿入の段階では適用しません。

O(log n) の探索よりも、遅い O(n) の挿入処理が全体の実行時間を支配することに注意してください。

バージョン 3.10 で変更: key パラメータが追加されました。

パフォーマンスに関するメモ¶

bisect() と insort() を使って時間的制約のあるコードを書くときは、以下のことを念頭に置いてください:

二分法は、値の範囲を検索するのに有効です。特定の値を検索する場合は、辞書の方が効率的です。
insort() 関数の計算量は O(n) です。対数時間の探索よりも、線形時間の挿入処理が全体の実行時間を支配するためです。
探索関数は状態を保持せず、キー関数の結果を使用後に破棄します。そのため、ループ内で探索関数を使うと、配列の同じ要素に対してキー関数を繰り返し呼び出す可能性があります。キー関数が遅い場合は、@functools.cache でラップして重複した計算を避けることを検討してください。または、あらかじめ計算したキーの配列を探索して挿入位置を求める方法もあります (後の使用例を参照してください)。

参考

Sorted Collections は、bisect を使ってソート済みのデータのコレクションを管理する高性能なモジュールです。
bisect を利用して、直接の探索ができ、キー関数をサポートする、完全な機能を持つコレクションクラスを組み立てる SortedCollection recipe。キーは、探索中に不必要な呼び出しをさせないために、予め計算しておきます。

ソート済みリストの探索¶

上記の bisect 関数は挿入点を見つけるには便利ですが、一般的な検索タスクに使うには厄介であったり、使いにくい場合があります。以下の5つの関数は、それらをソートされたリストの標準的な検索に変換する方法を示しています:

def index(a, x):
    'xにちょうど等しい左端の値を見つける'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'xより小さい右端の値を見つける'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'x以下の右端の値を見つける'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'xより大きい左端の値を見つける'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'x以上の左端の要素を見つける'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

使用例¶

bisect() 関数は数値テーブルの探索に役に立ちます。この例では、 bisect() を使って、(たとえば)順序のついた数値の区切り点の集合に基づいて、試験の成績の等級を表す文字を調べます。区切り点は 90 以上は 'A'、 80 から 89 は 'B'、などです:

>>> def grade(score):
...     i = bisect([60, 70, 80, 90], score)
...     return "FDCBA"[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

bisect() と insort() 関数もタプルのリストで動作します。引数 key はテーブルのレコードの順序付けに使用されるフィールドを抽出します:

>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint

>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

>>> movies = [
...     Movie('Jaws', 1975, 'Spielberg'),
...     Movie('Titanic', 1997, 'Cameron'),
...     Movie('The Birds', 1963, 'Hitchcock'),
...     Movie('Aliens', 1986, 'Cameron')
... ]

>>> # 1960 年より後に公開された最初の映画を探す
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')

>>> # ソート順を保ったまま映画を挿入する
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
 Movie(name='Love Story', released=1970, director='Hiller'),
 Movie(name='Jaws', released=1975, director='Spielberg'),
 Movie(name='Aliens', released=1986, director='Cameron'),
 Movie(name='Titanic', released=1997, director='Cameron')]

キー関数がコストがかかる場合は、レコードのインデックスを見つけるために事前に計算されたキーのリストを検索することにより、関数呼び出しの繰り返しを回避することが可能です:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # または operator.itemgetter(1) を使う。
>>> keys = [r[1] for r in data]         # キーのリストを事前に計算する。
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

`bisect` --- 配列二分法アルゴリズム¶

パフォーマンスに関するメモ¶

ソート済みリストの探索¶

使用例¶

目次

前のトピックへ

次のトピックへ

このページ

bisect --- 配列二分法アルゴリズム¶

パフォーマンスに関するメモ¶

ソート済みリストの探索¶

使用例¶

`bisect` --- 配列二分法アルゴリズム¶