bisect --- 配列二分法アルゴリズム¶
ソースコード: Lib/bisect.py
このモジュールは、挿入のたびにリストをソートすることなく、ソートされた順序でリストを維持するためのサポートを提供します。 コストのかかる比較演算を伴う長いリストの場合、これは線形検索や頻繁な並べ替えよりも改善される可能性があります。
このモジュールは、基本的な二分法アルゴリズムを使用しているため bisect と呼ばれます。 特定の値を検索する他の二分法ツールとは異なり、このモジュールの関数は挿入点を特定するように設計されています。 したがって、関数は値が見つかったかどうかを判断するために __eq__() メソッドを呼び出すことはありません。 その代わりに、関数は __lt__() メソッドのみを呼び出し、配列内の値間の挿入点を返します。
注釈
The functions in this module are not thread-safe. If multiple threads
concurrently use bisect functions on the same sequence, this
may result in undefined behaviour. Likewise, if the provided sequence
is mutated by a different thread while a bisect function
is operating on it, the result is undefined. For example, using
insort_left() on the same list from multiple threads
may result in the list becoming unsorted.
次の関数が用意されています:
- 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 にソート順で挿入します。
This function first runs
bisect_left()to locate an insertion point. Next, it runs theinsert()method on a to insert x at the appropriate position to maintain sort order.テーブルへのレコードの挿入に対応するため、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 を挿入します。This function first runs
bisect_right()to locate an insertion point. Next, it runs theinsert()method on a to insert x at the appropriate position to maintain sort order.テーブルへのレコードの挿入に対応するため、key 関数を指定した場合は、探索の段階で x に適用し、挿入の段階では適用しません。
O(log n) の探索よりも、遅い O(n) の挿入処理が全体の実行時間を支配することに注意してください。
バージョン 3.10 で変更: key パラメータが追加されました。
パフォーマンスに関するメモ¶
bisect() と insort() を使って時間的制約のあるコードを書くときは、以下のことを念頭に置いてください:
二分法は、値の範囲を検索するのに有効です。 特定の値を検索する場合は、辞書の方が効率的です。
insort() 関数の計算量は O(n) です。 対数時間の探索よりも、線形時間の挿入処理が全体の実行時間を支配するためです。
The search functions are stateless and discard key function results after they are used. Consequently, if the search functions are used in a loop, the key function may be called again and again on the same array elements. If the key function isn't fast, consider wrapping it with
@functools.cacheto avoid duplicate computations. Alternatively, consider searching an array of precomputed keys to locate the insertion point (as shown in the examples section below).
参考
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)