bisect —配列二分アルゴリズム
ソースコード: :source: `Lib / bisect.py`
このモジュールは、挿入のたびにリストをソートしなくても、ソートされた順序でリストを維持するためのサポートを提供します。 コストのかかる比較操作を伴うアイテムの長いリストの場合、これは、より一般的なアプローチよりも改善される可能性があります。 このモジュールは、基本的な二分アルゴリズムを使用して作業を行うため、 bisect と呼ばれます。 ソースコードは、アルゴリズムの実用的な例として最も役立つ場合があります(境界条件はすでに正しいです!)。
以下の機能が提供されています。
- bisect.bisect_left(a, x, lo=0, hi=len(a))
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])
になるようにします。
- bisect.bisect_right(a, x, lo=0, hi=len(a))
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])
になるようにします。
- bisect.insort_left(a, x, lo=0, hi=len(a))
- x を a にソート順に挿入します。 これは、 a がすでにソートされていると仮定すると、
a.insert(bisect.bisect_left(a, x, lo, hi), x)
と同等です。 O(log n)検索は、遅いO(n)挿入ステップによって支配されることに注意してください。
- bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))
- insort_left()に似ていますが、 x の既存のエントリの後に a に x を挿入します。
も参照してください
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']
sorted()関数とは異なり、 bisect()関数が key または reversed 引数を持つことは意味がありません。非効率的な設計につながります(バイセクト関数を連続して呼び出すと、以前のすべてのキールックアップが「記憶」されません)。
代わりに、事前に計算されたキーのリストを検索して、問題のレコードのインデックスを見つけることをお勧めします。
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data] # precomputed 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)