Einführung in die geordnete Python-Modulhalbierungsliste

bisect – Pflegen einer geordneten Liste

Zweck: Es ist nicht erforderlich, jedes Mal sort aufzurufen, um eine geordnete Liste zu verwalten.

Das Bisect-Modul implementiert einen Algorithmus zum Einfügen von Elementen in eine geordnete Liste. In manchen Fällen ist dies effizienter als das wiederholte Sortieren der Liste oder das Erstellen einer großen Liste und das anschließende Sortieren. Bisect bedeutet Dichotomie. Hier wird die Bisektionsmethode zum Sortieren verwendet. Der Quellcode von Bisect ist eine Vorlage für die Bisektionssortierung. Dieses Modul umfasst weniger als 100 Codezeilen.

Einfügen

Halbierung importieren

Zufällig importieren

# Verwenden Sie einen konstanten Startwert, um sicherzustellen, dass

# die Dieselben Pseudozufallszahlen

# werden jedes Mal verwendet, wenn die Schleife ausgeführt wird.

random.seed(1)

print'New Pos Contents'

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

# Zufallszahlen generieren und

# sie in eine Liste einfügen sortiert

# order.

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

Ausführungsergebnis:

#./bisect_example.py

Neuer Pos-Inhalt

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

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]

Die vom Bisect-Modul bereitgestellten Funktionen sind:

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

Finden Sie den Index zum Einfügen von x in die Reihenfolge Listen Sie eine auf. lo und hi werden verwendet, um den Bereich der Liste anzugeben. Standardmäßig wird die gesamte Liste verwendet. Wenn x bereits existiert, fügen Sie es links ein. Der Rückgabewert ist index.

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

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

Diese beiden ähneln bisect_left, aber wenn x bereits existiert, fügen Sie es rechts ein.

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

Füge x in die geordnete Liste a ein. Der Effekt ist der gleiche wie bei 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))

Ähnlich wie insort_left, aber wenn x bereits existiert, fügen Sie es rechts ein.

Funktionen können in zwei Kategorien unterteilt werden: bisect*, die zum Suchen des Index verwendet werden. Insort* wird zum eigentlichen Einfügen verwendet. Standardmäßig werden Wiederholungen von rechts eingefügt. Das am häufigsten verwendete ist wahrscheinlich Insort.

Es gibt ein Beispiel für die Berechnung der Bewertung basierend auf der Punktzahl im Standard:

>>> 70, 80, 90], grades='FDCBA'):

... i = halbieren(Haltepunkte, Punktzahl)

... geben Noten[i] zurück

...

>>> , 'A' , 'C','C', 'B', 'A', 'A']

Bisect unterstützt keine Schlüsselwortparameter wie sort. Es wird empfohlen, es wie folgt zu behandeln:

>> ;> data =[('rot', 5), ('blau', 1), ('gelb', 8), ('schwarz', 0)]

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

>>> keys =[r[1] für r in data] #vorberechnete Liste von Schlüsseln

> >> data[bisect_left(keys,0)]

('black', 0)

>>> keys,1)]

('blue', 1)

>>> data[bisect_left(keys,5)]

('red', 5)

>>> data[bisect_left(keys,8)]

('gelb', 8)