bisect - Verwaltet Listen in sortierter Reihenfolge

Link zu Doug Hellmanns Original Artikel

Zweck: Verwaltet eine sortierte Liste ohne dass sort für jedes neue Element aufgerufen werden muss.
Python: ab 1.4

Das bisect Modul implementiert einen Algorithmus, der neue Elemente in eine Liste einfügt während er die Sortierung aufrecht erhält. Dies kann wesentlich effizienter sein, als die Liste immmer wieder neu zu sortieren oder eine große Liste nach der Erstellung explizit zu sortieren.

Beispiel

Schauen wir uns ein einfaches Beispiel an, welches bisect.insort() benutzt, um Elemente in sortierter Reihenfolge einzufügen.

import bisect
import random

# Benutze einen konstanten Wert um zu garantieren,
# dass wir bei jedem Lauf immer
# die gleichen Pseudo-Zufallszahlen sehen.
random.seed(1)

# Generiere 20 Zufallszahlen und
# füge sie sortiert in die Liste ein
l = []
for i in range(1, 20):
        r = random.randint(1, 100)
        position = bisect.bisect(l, r)
        bisect.insort(l, r)
        print '%2d %2d' % (r, position), l

Die Ausgabe dieses Skripts ist: 

$ python 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]
45  7 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23  4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]

Die erste Spalte zeigt die neue Zufallszahl. Die zweite Spalte zeigt die Position, in der die Zahl eingefügt wird. Der Rest jeder Zeile ist die aktuelle sortierte Liste.

Dies ist ein einfaches Beispiel und für die Anzahl der Elemente die wir manipulieren mag es schneller sein die Liste einfach zu erstellen und dann einmalig zu sortieren. Aber bei großen Listen können bedeutende Zeit- und Speichereinsparungen durch die Verwendung eines Einfügealgorithmus wie diesen erreicht werden.

Sie haben vermutlich gemerkt, dass die Ergebnisliste oben, einige sich wiederholende Werte enthält (45 und 77). Das bisect Modul stellt zwei Wege zur Verarbeitung von Widerholungen zur Verfügung. Neue Werte können entweder links oder rechts des bereits existierenden eingefügt werden. Die insort() Funktion ist eigentlich ein Alias für insort_right(), welche nach dem existierenden Wert einfügt. Die korrespondierende Funktion insort_left() fügt links von dem bestehenden Wert ein.

Wenn wir die gleichen Daten unter Verwendung von bisect_left() manipulieren, erhalten wir die gleiche sortierte Liste, aber beachten Sie, dass die Einfügepositionen für die Duplikate sich geändert haben.

import bisect
import random

# Zurücksetzen des "seed"
random.seed(1)

# Benutze bisect_left und insort_left.
l = []
for i in range(1, 20):
        r = random.randint(1, 100)
        position = bisect.bisect_left(l, r)
        bisect.insort_left(l, r)
        print '%2d %2d' % (r, position), l


 

$ python bisect_example2.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  8 [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]
45  6 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23  4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]

Zusätzlich zur Python Implementierung existiert eine performatere C Implementierung. Wenn die C Version verfügbar ist dann wird automitisch diese beim Import des bisect Moduls verwendet.

Siehe auch

bisect

Die Dokumenation der Standardbibliothek für dieses Modul.

Wikipedia:Insertion Sort

Eine Beschreibung des Einfüge-Algorithmus