bisect —配列二分アルゴリズム—Pythonドキュメント

bisect —配列二分アルゴリズム

ソースコード： ：source： `Lib / bisect.py`

---

このモジュールは、挿入のたびにリストをソートしなくても、ソートされた順序でリストを維持するためのサポートを提供します。 コストのかかる比較操作を伴うアイテムの長いリストの場合、これは、より一般的なアプローチよりも改善される可能性があります。 このモジュールは、基本的な二分アルゴリズムを使用して作業を行うため、 bisect と呼ばれます。 ソースコードは、アルゴリズムの実用的な例として最も役立つ場合があります（境界条件はすでに正しいです！）。

以下の機能が提供されています。

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

a で x の挿入ポイントを見つけて、ソートされた順序を維持します。 パラメータ lo および hi を使用して、考慮すべきリストのサブセットを指定できます。 デフォルトでは、リスト全体が使用されます。 x が a にすでに存在する場合、挿入ポイントは既存のエントリの前（左側）になります。 戻り値は、 a がすでにソートされていることを前提として、list.insert()の最初のパラメーターとして使用するのに適しています。

返された挿入ポイント i は、配列 a を2つに分割し、左側がall(val < x for val in a[lo : i])、右側がall(val >= x for val in a[i : hi])になるようにします。

key は、各入力要素から比較キーを抽出するために使用される1つの引数の 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))

bisect_left（）に似ていますが、 a の x の既存のエントリの後ろ（右側）にある挿入ポイントを返します。

返された挿入ポイント i は、配列 a を2つに分割し、左側がall(val <= x for val in a[lo : i])、右側がall(val > x for val in a[i : hi])になるようにします。

key は、各入力要素から比較キーを抽出するために使用される1つの引数の key関数を指定します。 デフォルト値はNoneです（要素を直接比較してください）。

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

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

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

key は、各入力要素から比較キーを抽出するために使用される1つの引数の key関数を指定します。 デフォルト値はNoneです（要素を直接比較してください）。

この関数は、最初に bisect_left（）を実行して、挿入ポイントを見つけます。 次に、 a でinsert()メソッドを実行し、 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))

insort_left（）に似ていますが、 x の既存のエントリの後に a に x を挿入します。

key は、各入力要素から比較キーを抽出するために使用される1つの引数の key関数を指定します。 デフォルト値はNoneです（要素を直接比較してください）。

この関数は、最初に bisect_right（）を実行して、挿入ポイントを見つけます。 次に、 a でinsert()メソッドを実行し、 x を適切な位置に挿入してソート順を維持します。

O(log n)検索は、遅いO（n）挿入ステップによって支配されることに注意してください。

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

パフォーマンスノート

bisect（）および insort（）を使用して時間に敏感なコードを作成するときは、次の点に注意してください。

• 二分法は、値の範囲を検索するのに効果的です。 特定の値を見つけるために、辞書はよりパフォーマンスが高くなります。
• insort（）関数はO(n)です。これは、対数探索ステップが線形時間挿入ステップによって支配されているためです。
• 検索機能はステートレスであり、使用後に主要な機能の結果を破棄します。 したがって、検索関数がループで使用される場合、キー関数は同じ配列要素で何度も呼び出される可能性があります。 キー関数が高速でない場合は、計算の重複を避けるために、 functools.cache（）でラップすることを検討してください。 または、事前に計算されたキーの配列を検索して、挿入ポイントを見つけることを検討してください（以下の例のセクションを参照）。

も参照してください

• 並べ替えられたコレクションは、 bisect を使用して並べ替えられたデータのコレクションを管理する高性能モジュールです。
• SortedCollectionレシピは、bisectを使用して、簡単な検索メソッドとキー関数のサポートを備えたフル機能のコレクションクラスを構築します。 キーは、検索中にキー関数への不要な呼び出しを保存するために事前に計算されています。

ソートされたリストの検索

上記の 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

例

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']

キー関数の繰り返し呼び出しを回避する1つの手法は、事前に計算されたキーのリストを検索して、レコードのインデックスを見つけることです。

>>> 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)