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

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


このモジュールは、挿入の度にリストをソートすることなく、リストをソートされた順序に保つことをサポートします。大量の比較操作を伴うような、アイテムがたくさんあるリストでは、より一般的なアプローチに比べて、パフォーマンスが向上します。動作に基本的な二分法アルゴリズムを使っているので、 bisect と呼ばれています。ソースコードはこのアルゴリズムの実例として一番役に立つかもしれません (境界条件はすでに正しいです!)。

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

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

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

The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo : i]) for the left side and all(val >= x for val in a[i : hi]) for the right side.

key specifies a key function of one argument that is used to extract a comparison key from each input element. The default value is None (compare the elements directly).

バージョン 3.10 で変更: Added the key parameter.

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

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

The returned insertion point i partitions the array a into two halves so that all(val <= x for val in a[lo : i]) for the left side and all(val > x for val in a[i : hi]) for the right side.

key specifies a key function of one argument that is used to extract a comparison key from each input element. The default value is None (compare the elements directly).

バージョン 3.10 で変更: Added the key parameter.

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

Insert x in a in sorted order.

key specifies a key function of one argument that is used to extract a comparison key from each input element. The default value is None (compare the elements directly).

This function first runs bisect_left() to locate an insertion point. Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

バージョン 3.10 で変更: Added the key parameter.

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

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

key specifies a key function of one argument that is used to extract a comparison key from each input element. The default value is None (compare the elements directly).

This function first runs bisect_right() to locate an insertion point. Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

バージョン 3.10 で変更: Added the key parameter.

Performance Notes

When writing time sensitive code using bisect() and insort(), keep these thoughts in mind:

  • Bisection is effective for searching ranges of values. For locating specific values, dictionaries are more performant.

  • The insort() functions are O(n) because the logarithmic search step is dominated by the linear time insertion step.

  • 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.cache() to 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 is a high performance module that uses bisect to managed sorted collections of data.

  • The SortedCollection recipe uses bisect to build a full-featured collection class with straight-forward search methods and support for a key-function. The keys are precomputed to save unnecessary calls to the key function during searches.

ソート済みリストの探索

上記の bisect() 関数群は挿入点を探索するのには便利ですが、普通の探索タスクに使うのはトリッキーだったり不器用だったりします。以下の 5 関数は、これらをどのように標準の探索やソート済みリストに変換するかを説明します:

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

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

Examples

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

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

One technique to avoid repeated calls to a key function is to search a list of precomputed keys to find the index of a record:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Precompute a list of keys.
>>> 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)