bisect — Algorithmus zum Bisektion von Arrays

Quellcode: Lib/bisect.py

Dieses Modul bietet Unterstützung für die Aufrechterhaltung einer sortierten Liste, ohne die Liste nach jeder Einfügung neu sortieren zu müssen. Bei langen Listen von Elementen mit kostspieligen Vergleichsoperationen kann dies eine Verbesserung gegenüber linearen Suchen oder häufigem Neusortieren darstellen.

Das Modul heißt bisect, da es einen grundlegenden Bisektionsalgorithmus verwendet, um seine Arbeit zu erledigen. Im Gegensatz zu anderen Bisektionswerkzeugen, die nach einem bestimmten Wert suchen, sind die Funktionen in diesem Modul darauf ausgelegt, einen Einfügepunkt zu finden. Dementsprechend rufen die Funktionen niemals eine __eq__()-Methode auf, um zu bestimmen, ob ein Wert gefunden wurde. Stattdessen rufen die Funktionen nur die __lt__()-Methode auf und geben einen Einfügepunkt zwischen den Werten in einem Array zurück.

Hinweis

Die Funktionen in diesem Modul sind nicht threadsicher. Wenn mehrere Threads gleichzeitig bisect-Funktionen auf derselben Sequenz verwenden, kann dies zu undefiniertem Verhalten führen. Ebenso ist das Ergebnis undefiniert, wenn die bereitgestellte Sequenz von einem anderen Thread mutiert wird, während eine bisect-Funktion darauf arbeitet. Zum Beispiel kann die Verwendung von insort_left() auf derselben Liste aus mehreren Threads dazu führen, dass die Liste unsortiert wird.

Die folgenden Funktionen sind verfügbar

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

Findet den Einfügepunkt für x in a, um die sortierte Reihenfolge beizubehalten. Die Parameter lo und hi können verwendet werden, um einen Teil der Liste anzugeben, der berücksichtigt werden soll; standardmäßig wird die gesamte Liste verwendet. Wenn x bereits in a vorhanden ist, liegt der Einfügepunkt vor (links von) allen vorhandenen Einträgen. Der Rückgabewert ist für die Verwendung als erster Parameter von list.insert() geeignet, vorausgesetzt, a ist bereits sortiert.

Der zurückgegebene Einfügepunkt ip teilt das Array a in zwei Slices auf, sodass all(elem < x for elem in a[lo : ip]) für die linke Slice wahr ist und all(elem >= x for elem in a[ip : hi]) für die rechte Slice wahr ist.

key gibt eine Schlüsselfunktion mit einem Argument an, die verwendet wird, um einen Vergleichsschlüssel aus jedem Element im Array zu extrahieren. Zur Unterstützung der Suche nach komplexen Datensätzen wird die Schlüsselfunktion nicht auf den Wert x angewendet.

Wenn key None ist, werden die Elemente direkt verglichen und es wird keine Schlüsselfunktion aufgerufen.

Geändert in Version 3.10: Der Parameter key wurde hinzugefügt.

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

Ähnlich wie bisect_left(), gibt aber einen Einfügepunkt zurück, der nach (rechts von) allen vorhandenen Einträgen von x in a kommt.

Der zurückgegebene Einfügepunkt ip teilt das Array a in zwei Slices auf, sodass all(elem <= x for elem in a[lo : ip]) für die linke Slice wahr ist und all(elem > x for elem in a[ip : hi]) für die rechte Slice wahr ist.

Geändert in Version 3.10: Der Parameter key wurde hinzugefügt.

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

Fügt x in sortierter Reihenfolge in a ein.

Diese Funktion führt zuerst bisect_left() aus, um einen Einfügepunkt zu finden. Als Nächstes führt sie die insert()-Methode auf a aus, um x an der entsprechenden Stelle einzufügen, um die Sortierreihenfolge beizubehalten.

Um das Einfügen von Datensätzen in eine Tabelle zu unterstützen, wird die key-Funktion (falls vorhanden) für den Suchschritt auf x angewendet, aber nicht für den Einfügeschritt.

Beachten Sie, dass die O(log n)-Suche von dem langsamen O(n)-Einfügeschritt dominiert wird.

Geändert in Version 3.10: Der Parameter key wurde hinzugefügt.

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)

Ähnlich wie insort_left(), aber x wird in a nach allen vorhandenen Einträgen von x eingefügt.

Diese Funktion führt zuerst bisect_right() aus, um einen Einfügepunkt zu finden. Als Nächstes führt sie die insert()-Methode auf a aus, um x an der entsprechenden Stelle einzufügen, um die Sortierreihenfolge beizubehalten.

Um das Einfügen von Datensätzen in eine Tabelle zu unterstützen, wird die key-Funktion (falls vorhanden) für den Suchschritt auf x angewendet, aber nicht für den Einfügeschritt.

Beachten Sie, dass die O(log n)-Suche von dem langsamen O(n)-Einfügeschritt dominiert wird.

Geändert in Version 3.10: Der Parameter key wurde hinzugefügt.

Leistungshinweise

Wenn Sie zeitkritischen Code mit bisect() und insort() schreiben, beachten Sie Folgendes:

  • Bisektion ist für die Suche in Wertebereichen effektiv. Für das Auffinden bestimmter Werte sind Dictionaries performanter.

  • Die insort()-Funktionen sind O(n), da der logarithmische Suchschritt vom linearen Einfügeschritt dominiert wird.

  • Die Suchfunktionen sind zustandslos und verwerfen die Ergebnisse der Schlüsselfunktion, nachdem sie verwendet wurden. Folglich kann die Schlüsselfunktion immer wieder für dieselben Array-Elemente aufgerufen werden, wenn die Suchfunktionen in einer Schleife verwendet werden. Wenn die Schlüsselfunktion nicht schnell ist, sollten Sie erwägen, sie mit functools.cache() zu umschließen, um doppelte Berechnungen zu vermeiden. Alternativ sollten Sie erwägen, ein Array von vorab berechneten Schlüsseln zu durchsuchen, um den Einfügepunkt zu finden (wie im nachstehenden Beispielbereich gezeigt).

Siehe auch

  • Sorted Collections ist ein Hochleistungsmodul, das bisect zur Verwaltung sortierter Datensammlungen verwendet.

  • Das SortedCollection recipe verwendet bisect, um eine voll funktionsfähige Collection-Klasse mit geradlinigen Suchmethoden und Unterstützung für Schlüsselfunktionen zu erstellen. Die Schlüssel werden vorab berechnet, um unnötige Aufrufe der Schlüsselfunktion während der Suche zu vermeiden.

Suche in sortierten Listen

Die oben genannten bisect-Funktionen sind nützlich, um Einfügepunkte zu finden, können aber bei gängigen Suchaufgaben schwierig oder umständlich zu verwenden sein. Die folgenden fünf Funktionen zeigen, wie sie in die Standard-Lookups für sortierte Listen umgewandelt werden können.

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

Beispiele

Die Funktion bisect() kann für numerische Tabellensuchen nützlich sein. Dieses Beispiel verwendet bisect(), um eine Notenstufe für eine Prüfungspunktzahl nachzuschlagen (z. B. 90 und höher ist ein 'A', 80 bis 89 ist ein 'B' und so weiter).

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

Die Funktionen bisect() und insort() funktionieren auch mit Listen von Tupeln. Das Argument key kann verwendet werden, um das Feld zu extrahieren, das für die Ordnung von Datensätzen in einer Tabelle verwendet wird.

>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint

>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

>>> movies = [
...     Movie('Jaws', 1975, 'Spielberg'),
...     Movie('Titanic', 1997, 'Cameron'),
...     Movie('The Birds', 1963, 'Hitchcock'),
...     Movie('Aliens', 1986, 'Cameron')
... ]

>>> # Find the first movie released after 1960
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')

>>> # Insert a movie while maintaining sort order
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
 Movie(name='Love Story', released=1970, director='Hiller'),
 Movie(name='Jaws', released=1975, director='Spielberg'),
 Movie(name='Aliens', released=1986, director='Cameron'),
 Movie(name='Titanic', released=1997, director='Cameron')]

Wenn die Schlüsselfunktion kostspielig ist, ist es möglich, wiederholte Funktionsaufrufe zu vermeiden, indem eine Liste vorab berechneter Schlüssel durchsucht wird, um den Index eines Datensatzes zu finden.

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Precompute a 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)