Das Bisect-Modul verwaltet eine geordnete Liste

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 die Liste wiederholt zu sortieren oder eine große Liste zu erstellen und diese dann zu 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

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

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, an dem x in die geordnete Liste a eingefügt wird. 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 von Indizes 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 von Noten basierend auf Punktzahlen in den Standards:

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

... i = halbieren(Haltepunkte, Punktzahl)

... Noten zurückgeben[i]

...

> >> [Note(Punktzahl)für Punktzahl in [33, 99, 77, 70, 89, 90, 100]]

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

Bisect unterstützt keine Schlüsselwortparameter wie sort. Es wird empfohlen, wie folgt damit umzugehen:

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