bisect モジュールは順序付きリストを維持します

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

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

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

挿入

import bisect
import random
   
# Use aconstant seed to ensure that
# the samepseudo-random numbers
# are usedeach time the loop is run.
random.seed(1)
   
print'New  Pos Contents'
print'---  --- --------'
   
# Generaterandom numbers and
# insert theminto a list in sorted
# order.
l = []
for i inrange(1, 15):
#产生1-100的随机数
    r = random.randint(1, 100)
    position = bisect.bisect(l, r)
    bisect.insort(l, r)
print'%3d  %3d' % (r, position), l

実行結果:

#./bisect_example.py

新しい投稿内容

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

14 0[14]

85 1[ 14, 85]

77 1[14, 77, 85]

26 1[14, 26, 77, 85]

50 2[14, 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 はすでに存在するため、右側に挿入します。

関数は 2 つのカテゴリに分類できます。bisect* はインデックスを見つけるために使用されます。実際の挿入には 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']

Bisect は sort のようなキーワード パラメータをサポートしていないため、それを処理することをお勧めします。以下の通り:

>>> data =[('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambdar: 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)