Pythonモジュールの紹介-bisect順序付きリスト

bisect – 順序付きリストを維持する

目的: 順序付きリストを維持するために毎回 sort を呼び出す必要はありません。

bisect モジュールは、順序付きリストに要素を挿入するためのアルゴリズムを実装します。場合によっては、リストを繰り返し並べ替えたり、大きなリストを作成して並べ替えたりするよりも効率的です。 bisect は二分法を意味します。ここでは二分法を使用してソートします。bisect のソース コードは二分法ソートのテンプレートです。このモジュールのコードは 100 行未満です。

insert

import bisect

import random

# ループが実行されるたびに

# 同じ擬似乱数

# が使用されるようにするために、定数シードを使用します。

random.seed(1)

print'新しいposコンテンツ'

print'--- -----------'

# 乱数を生成し、

# 並べ替えられた順序でリストに挿入します

#。

l = []

for i inrange(1, 15):

r =random.randint(1, 100)

position = bisect.bisect(l, r)

bisect.insort(l, r )

print'%3d %3d' % (r,position), l

実行結果:

#./bisect_example.py

新しいPos内容

--- --- ------ --

14 0[14]

85 1[14, 85]

77 1[14, 77, 85]

26 1[14, 26, 77, 85]

50 2[1 4, 26 , 50, 77, 85]

45 2[14, 26, 45, 50, 77, 85]

66 4[14, 26, 45, 50, 66, 77, 85]

79 6[14 、26、45、50、66、77、79、85]

10 0[10、14、26、45、50、66、77、79、85]

3 0[3、10、14、26 、45、50、66、77、79、85]

84 9[3、10、14、26、45、50、66、77、79、84、85]

44 4[3、10、14 、26、44、45、50、66、77、79、84、85]

77 9[3、10、14、26、44、45、50、66、77、77、79、84、85]

1 0[1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

Bisect モジュールによって提供される関数は次のとおりです:

bisect。 bisect_left(a ,x, lo=0, hi=len(a)):

順序付きリスト a に x を挿入するインデックスを見つけます。 lo と hi はリストの範囲を指定するために使用され、デフォルトではリスト全体が使用されます。 x がすでに存在する場合は、それを左側に挿入します。戻り値はインデックスです。

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

bisect.bisect(a, x,lo=0, hi=len(a))

これら 2 つは bisect_left に似ていますただし、x がすでに存在する場合は、右側に挿入します。

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

順序付きリスト a に x を挿入します。効果は a.insert(bisect.bisect_left(a,x, lo, hi), x) と同じです。

bisect.insort_right(a,x, lo=0, hi=len(a))

bisect.insort(a, x,lo=0, hi=len(a))

insort_left と似ていますが、 x はすでに存在するため、右側に挿入します。

関数は、インデックスを見つけるために使用される bisect* の 2 つのカテゴリに分類できます。実際の挿入には Insort* が使用されます。デフォルトでは、リピートは右から挿入されます。最も一般的に使用されるのはおそらく insort です。

標準のスコアに基づいて評価を計算する例があります:

>>> def Grade(score,breakpoints=[60, 70, 80, 90], Grade='FDCBA' ):

... i = bisect(ブレークポイント, スコア)

... 成績[i]を返します

...

>>> [33, 99のスコアの成績(スコア)] , 77, 70 , 89, 90, 100]]

['F', 'A', 'C', 'C', 'B', 'A', 'A']

二分法はキーワードをサポートしていませんsort のようなパラメータを使用する場合は、次のように処理することをお勧めします:

>>> data =[('red', 5), ('blue', 1), (' yellow', 8), (' black', 0)]

>>> data.sort(key=lambdar: r[1])

>>> キー =[r[1] for r in data] #precomputed listキーの数

>> data[bisect_left(keys,0)]

('black', 0)

>>> data[bisect_left(keys,1)] ', 1)

> >> データ[bisect_left(keys,5)]

('red', 5)

>>> データ[bisect_left(keys,8)] 「黄色」、8)