High Performance Python, 2. Auflage

Kapitel 4. Wörterbücher und Mengen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Fragen, die du nach diesem Kapitel beantworten kannst

• Wozu sind Wörterbücher und Sets gut?

• Inwiefern sind Wörterbücher und Sets dasselbe?

• Wie hoch ist der Aufwand bei der Verwendung eines Wörterbuchs?

• Wie kann ich die Leistung eines Wörterbuchs optimieren?

• Wie verwendet Python Wörterbücher, um den Überblick über Namensräume zu behalten?

Mengen und Wörterbücher sind die idealen Datenstrukturen, wenn deine Daten keine eigene Reihenfolge haben (außer der Einfügereihenfolge), aber ein eindeutiges Objekt, auf das du verweisen kannst(das Referenzobjekt ist normalerweise eine Zeichenkette, kann aber auch ein beliebiger hashfähiger Typ sein). Dieses Referenzobjekt wird Schlüssel genannt, während die Daten der Wert sind. Wörterbücher und Mengen sind fast identisch, außer dass Mengen keine Werte enthalten: Eine Menge ist einfach eine Sammlung von eindeutigen Schlüsseln. Wie der Name schon sagt, sind Sets sehr nützlich, um Mengenoperationen durchzuführen.

Hinweis

Ein Hash-Typ ist ein Typ, der sowohl die magische Funktion __hash__ als auch entweder __eq__ oder __cmp__ implementiert. Alle nativen Typen in Python implementieren diese bereits, und alle Benutzerklassen haben Standardwerte. Siehe"Hash-Funktionen und Entropie" für weitere Details.

Während wir im vorigen Kapitel gesehen haben, dass wir bei Listen/Tupeln ohne eigene Ordnung bestenfalls O(log n) Suchzeit haben (durch eine Suchoperation), können wir mit Wörterbüchern und Mengen O(1) auf der Grundlage eines beliebigen Index nachschlagen. Darüber hinaus haben Wörterbücher und Mengen wie Listen/Tupel eine O(1)Einfügezeit.¹ Wie wir in "Wie funktionieren Wörterbücher und Mengen?" sehen werden , wird diese Geschwindigkeit durch die Verwendung einer Hash-Tabelle mit offenen Adressen als zugrunde liegende Datenstruktur erreicht.

Die Verwendung von Wörterbüchern und Sets hat jedoch einen Preis. Erstens benötigen sie in der Regel einen größeren Speicherplatz. Auch wenn die Komplexität beim Einfügen und Nachschlagen O(1) ist, hängt die tatsächliche Geschwindigkeit stark von der verwendeten Hash-Funktion ab. Wenn die Hash-Funktion nur langsam ausgewertet werden kann, werden alle Operationen mit Wörterbüchern oder Mengen ähnlich langsam sein.

Schauen wir uns ein Beispiel an. Nehmen wir an, wir möchten die Kontaktdaten aller Personen aus dem Telefonbuch speichern. Wir möchten diese Daten in einer Form speichern, die es uns erleichtert, die Frage "Wie lautet die Telefonnummer von John Doe?" zu beantworten. In Listen würden wir die Telefonnummern und Namen der Reihe nach speichern und die gesamte Liste durchsuchen, um die gewünschte Telefonnummer zu finden, wie inBeispiel 4-1 gezeigt.

Beispiel 4-1. Nachschlagen im Telefonbuch mit einer Liste

def find_phonenumber(phonebook, name):
    for n, p in phonebook:
        if n == name:
            return p
    return None

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
]
print(f"John Doe's phone number is {find_phonenumber(phonebook, 'John Doe')}")

Hinweis

Wir könnten dies auch tun, indem wir die Liste sortieren und das Modul bisect (ausBeispiel 3-4) verwenden, um die Leistung von O(log n) zu erhalten.

Bei einem Wörterbuch hingegen kann der "Index" einfach die Namen und die "Werte" die Telefonnummern sein, wie in Beispiel 4-2 gezeigt. So können wir den gewünschten Wert einfach nachschlagen und erhalten einen direkten Verweis darauf, anstatt jeden Wert in unserem Datensatz lesen zu müssen.

Beispiel 4-2. Nachschlagen im Telefonbuch mit einem Wörterbuch

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print(f"John Doe's phone number is {phonebook['John Doe']}")

Bei großen Telefonbüchern ist der Unterschied zwischen der O(1) Zeit für das Nachschlagen im Wörterbuch und der O(n) Zeit für die lineare Suche über die Liste (oder bestenfalls der O(log n) Komplexität mit dem Bisect-Modul) ganz erheblich.

Tipp

Erstelle ein Skript, das die Leistung der Methode list-bisect gegenüber einem Wörterbuch für die Suche nach einer Nummer in einem Telefonbuch vergleicht. Wie verändert sich die Zeit, wenn die Größe des Telefonbuchs wächst?

Wenn wir hingegen die Frage "Wie viele eindeutige Vornamen gibt es in meinem Telefonbuch?" beantworten wollten, könnten wir die Macht der Mengen nutzen. Eine Menge ist einfach eine Sammlung von eindeutigen Schlüsseln - das ist genau die Eigenschaft, die wir in unseren Daten erzwingen wollen. Dies steht im krassen Gegensatz zu einem listenbasierten Ansatz, bei dem diese Eigenschaft unabhängig von der Datenstruktur durch den Vergleich aller Namen mit allen anderen Namen erzwungen werden muss. Beispiel 4-3 veranschaulicht dies.

Beispiel 4-3. Finden von eindeutigen Namen mit Listen und Sets

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook: 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names: 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook: 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name) 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Guido van Rossum", "301-555-5555"),
]

print("Number of unique names from set method:", set_unique_names(phonebook))
print("Number of unique names from list method:", list_unique_names(phonebook))

,

Wir müssen alle Einträge in unserem Telefonbuch durchgehen, und so kostet diese Schleife O(n).

Hier müssen wir den aktuellen Namen mit allen eindeutigen Namen vergleichen, die wir bereits gesehen haben. Wenn es sich um einen neuen eindeutigen Namen handelt, fügen wir ihn zu unserer Liste der eindeutigen Namen hinzu. Dann gehen wir die Liste weiter durch und führen diesen Schritt für jeden Eintrag im Telefonbuch durch.

Bei der Set-Methode müssen wir nicht alle eindeutigen Namen durchgehen, die wir bereits gesehen haben, sondern können den aktuellen Namen einfach zu unserer Menge eindeutiger Namen hinzufügen. Da Mengen die Einzigartigkeit der darin enthaltenen Schlüssel garantieren, wird ein Element, das sich bereits in der Menge befindet, nicht hinzugefügt, wenn du es versuchst. Außerdem kostet dieser Vorgang O(1).

Die innere Schleife des Listenalgorithmus iteriert über unique_names, die zunächst leer ist und dann im schlimmsten Fall, wenn alle Namen eindeutig sind, auf die Größe von phonebook anwächst. Dies kann alslineare Suchenach jedem Namen im Telefonbuch über eine ständig wachsende Liste angesehen werden. Der gesamte Algorithmus funktioniert also wie O(n^2).

Auf der anderen Seite hat der Mengenalgorithmus keine innere Schleife; die Operation set.add ist ein O(1) Prozess, der in einer festen Anzahl von Operationen abgeschlossen wird, unabhängig davon, wie groß das Telefonbuch ist (es gibt einige kleinere Einschränkungen, die wir bei der Diskussion der Implementierung von Wörterbüchern und Mengen behandeln werden). Der einzige nicht konstante Beitrag zur Komplexität dieses Algorithmus ist also die Schleife über das Telefonbuch, so dass dieser Algorithmus in O(n) ausgeführt wird.

Wenn wir diese beiden Algorithmen anhand einer phonebook mit 10.000 Einträgen und 7.412 eindeutigen Vornamen messen, sehen wir, wie drastisch der Unterschied zwischen O(n) undO(n^2) sein kann:

>>> %timeit list_unique_names(large_phonebook)
1.13 s ± 26.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit set_unique_names(large_phonebook)
4.48 ms ± 177 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Mit anderen Worten: Der Set-Algorithmus hat uns einen 252-fachen Geschwindigkeitsgewinn beschert! Außerdem steigen die Geschwindigkeitsgewinne, je größer die phonebook ist (bei einer phonebook mit 100.000 Einträgen und 15.574 eindeutigen Vornamen erhalten wir einen 557-fachen Geschwindigkeitszuwachs).

Wie funktionieren Wörterbücher und Sets?

Wörterbücher und Mengen verwenden Hash-Tabellen, um ihreO(1) Suchvorgänge und Einfügungen zu realisieren. Diese Effizienz ist das Ergebnis einer sehr cleveren Verwendung einer Hash-Funktion, die einen beliebigen Schlüssel (d.h. eine Zeichenkette oder ein Objekt) in einen Index für eine Liste verwandelt. Die Hash-Funktion und die Liste können später verwendet werden, um zu ermitteln, wo sich ein bestimmtes Datenelement befindet, ohne dass eine Suche erforderlich ist. Indem wir den Schlüssel der Daten in etwas verwandeln, das wie ein Listenindex verwendet werden kann, erreichen wir die gleiche Leistung wie bei einer Liste. Außerdem müssen wir nicht mehr mit einem numerischen Index auf die Daten verweisen, was wiederum eine gewisse Ordnung der Daten voraussetzt, sondern können sie mit diesem beliebigen Schlüssel ansprechen.

Einfügen und Abrufen

Um eine Hashtabelle von Grund auf neu zu erstellen, beginnen wir mit zugewiesenem Speicher, ähnlich wie bei Arrays. Wenn wir bei einem Array Daten einfügen wollen, suchen wir einfach den kleinsten ungenutzten Bereich und fügen unsere Daten dort ein (und ändern gegebenenfalls die Größe). Bei Hash-Tabellen müssen wir zuerst herausfinden, wo die Daten in diesem zusammenhängenden Speicherbereich platziert werden sollen.

Die Platzierung der neuen Daten hängt von zwei Eigenschaften der einzufügenden Daten ab: dem Hash-Wert des Schlüssels und dem Vergleich des Wertes mit anderen Objekten. Wenn wir Daten einfügen, wird der Schlüssel zunächst gehasht und mit einer Maskeversehen, damit er zu einem effektiven Index in einem Array wird.² Die Maske stellt sicher, dass der Hash-Wert, der den Wert einer beliebigen ganzen Zahl annehmen kann, in die zugewiesene Anzahl von Buckets passt. Wenn wir also 8 Speicherblöcke zugewiesen haben und unser Hash-Wert28975 ist, betrachten wir den Bucket mit dem Index 28975 & 0b111 = 7. Wenn unser Wörterbuch jedoch auf 512 Blöcke angewachsen ist, wird die Maske zu0b111111111 (und in diesem Fall würden wir den Bucket mit dem Index 28975 & 0b11111111 berücksichtigen).

Jetzt müssen wir prüfen, ob dieser Bucket bereits in Gebrauch ist. Wenn er leer ist, können wir den Schlüssel und den Wert in diesen Speicherblock einfügen. Wir speichern den Schlüssel, damit wir sicher sein können, dass wir den richtigen Wert abrufen. Wenn er in Gebrauch ist und der Wert des Buckets mit dem Wert übereinstimmt, den wir einfügen wollen (ein Vergleich, der mit dem eingebauten cmp durchgeführt wird), dann ist das Schlüssel/Wert-Paar bereits in der Hashtabelle und wir können zurückkehren. Wenn die Werte jedoch nicht übereinstimmen, müssen wir einen neuen Platz für die Daten finden.

Als zusätzliche Optimierung fügt Python die Schlüssel/Wert-Daten zunächst an ein Standard-Array an und speichert dann nur den Index in diesem Array in der Hashtabelle. Dadurch können wir den Speicherbedarf um 30-95% reduzieren.³ Außerdem haben wir dadurch die interessante Eigenschaft, dass wir die Reihenfolge, in der neue Elemente in das Wörterbuch eingefügt wurden, festhalten können (was seit Python 3.7 für alle Wörterbücher garantiert ist).

Um den neuen Index zu finden, berechnen wir ihn mithilfe einer einfachen linearen Funktion, einer Methode namens probing. Pythons Sondierungsmechanismus fügt einen Beitrag aus den höherwertigen Bits des ursprünglichen Hashes hinzu (du erinnerst dich, dass wir bei einer Tabelle der Länge 8 nur die letzten drei Bits des Hashes für den Anfangsindex berücksichtigt haben, indem wir einen Maskenwert von mask = 0b111 = bin(8 - 1) verwendet haben). Durch die Verwendung dieser höherwertigen Bits erhält jeder Hash eine andere Abfolge der nächstmöglichen Hashes, was dazu beiträgt, zukünftige Kollisionen zu vermeiden.

Bei der Wahl des Algorithmus für die Erstellung eines neuen Index gibt es viele Freiheiten; es ist jedoch sehr wichtig, dass das Schema jeden möglichen Index besucht, um die Daten gleichmäßig in der Tabelle zu verteilen. Wie gut die Daten in der Hash-Tabelle verteilt sind, nennt man den Auslastungsfaktor und hängt mit derEntropie der Hash-Funktion zusammen. Der Pseudocode in Beispiel 4-4 veranschaulicht die Berechnung von Hash-Indizes, die in CPython 3.7 verwendet werden. Dies zeigt auch eine interessante Tatsache über Hash-Tabellen: Der meiste Speicherplatz, den sie haben, ist leer!

Beispiel 4-4. Sequenz zum Nachschlagen im Wörterbuch

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) 
    i = perturb & mask
    yield i
    while True:
        perturb >>= PERTURB_SHIFT
        i = (i * 5 + perturb + 1) & mask
        yield i

hash gibt eine Ganzzahl zurück, während der eigentliche C-Code in CPython eine Ganzzahl ohne Vorzeichen verwendet. Aus diesem Grund gibt dieser Pseudocode das Verhalten in CPython nicht genau wieder, ist aber eine gute Annäherung.

Dieses Sondieren ist eine Abwandlung der naiven Methode deslinearen Sondierens. Beim linearen Sondieren liefern wir einfach die Wertei = (i * 5 + perturb + 1) & mask, wobei i mit dem Hash-Wert des Schlüssels initialisiert wird.⁴ Wichtig ist, dass beim linearen Sondieren nur die letzten Bits des Hashwerts berücksichtigt werden und der Rest unberücksichtigt bleibt (d. h. bei einem Wörterbuch mit acht Elementen werden nur die letzten drei Bits betrachtet, da die Maske zu diesem Zeitpunkt0x111 lautet). Das bedeutet, dass wir nicht nur eine Kollision haben, wenn der Hash zweier Elemente die gleichen letzten drei Binärziffern ergibt, sondern auch, dass die Reihenfolge der abgefragten Indizes gleich ist. Das gestörte Verfahren, das Python verwendet, berücksichtigt mehr Bits aus den Hashes der Elemente, um dieses Problem zu lösen.

Ähnlich wird verfahren, wenn wir nach einem bestimmten Schlüssel suchen: Der angegebene Schlüssel wird in einen Index umgewandelt, und dieser Index wird untersucht. Wenn der Schlüssel in diesem Index übereinstimmt (denk daran, dass wir bei Einfügeoperationen auch den ursprünglichen Schlüssel speichern), können wir diesen Wert zurückgeben. Wenn nicht, erstellen wir nach demselben Schema immer wieder neue Indizes, bis wir entweder die Daten finden oder auf einen leeren Bucket stoßen. Wenn wir auf einen leeren Bucket stoßen, können wir daraus schließen, dass die Daten nicht in der Tabelle vorhanden sind.

Abbildung 4-1 veranschaulicht den Prozess des Hinzufügens von Daten in eine Hashtabelle. Hier haben wir uns entschieden, eine Hash-Funktion zu erstellen, die einfach den ersten Buchstaben der Eingabe verwendet. Dazu verwenden wir die Python-Funktion ord für den ersten Buchstaben der Eingabe, um die ganzzahlige Repräsentation dieses Buchstabens zu erhalten (du weißt ja, dass Hash-Funktionen ganze Zahlen zurückgeben müssen). Wie wir in"Hash-Funktionen und Entropie" sehen werden, bietet Python Hash-Funktionen für die meisten seiner Typen an, so dass du in der Regel keine eigene Funktion erstellen musst, außer in extremenSituationen.

Abbildung 4-1. Die resultierende Hashtabelle beim Einfügen mit Kollisionen

Das Einfügen des Schlüssels Barcelona führt zu einer Kollision, und ein neuer Index wird nach dem Schema inBeispiel 4-4 berechnet. Dieses Wörterbuch kann auch in Python mit dem Code in Beispiel 4-5 erstellt werden.

Beispiel 4-5. Benutzerdefinierte Hashing-Funktion

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 'Italy',
    City("San Francisco"): 'USA',
    City("New York"): 'USA',
    City("Barcelona"): 'Spain',
}

In diesem Fall verursachen Barcelona und Rome die Hash-Kollision(Abbildung 4-1 zeigt das Ergebnis dieser Einfügung). Das sehen wir daran, dass wir für ein Wörterbuch mit vier Elementen einen Maskenwert von 0b111 haben. Infolgedessen werden Barcelona und Rome versuchen, denselben Index zu verwenden:

hash("Barcelona") = ord("B") & 0b111
                  = 66 & 0b111
                  = 0b1000010 & 0b111
                  = 0b010 = 2

hash("Rome") = ord("R") & 0b111
             = 82 & 0b111
             = 0b1010010 & 0b111
             = 0b010 = 2

Übung

Bearbeite die folgenden Aufgaben. Es folgt eine Diskussion über Hash-Kollisionen:

1. Ein Element finden -Wie würde eine Suche nach dem Schlüssel Johannesburg indemin Beispiel 4-5 erstellten Wörterbuch aussehen? Welche Indizes würden überprüft werden?

2. Löschen eines Elements -Wie würdest duindem in Beispiel 4-5 erstellten Wörterbuch das Löschen des Schlüssels Rome behandeln? Wie würden die nachfolgenden Suchvorgänge nach den SchlüsselnRome und Barcelona gehandhabt werden?

3. Hash-Kollisionen -Wie viele Hash-Kollisionen könntest du erwarten, wenn du 500 Städte, deren Namen alle mit einem Großbuchstaben beginnen, in eine Hash-Tabelle einträgst,ausgehend vondem in Beispiel 4-5 erstellten Wörterbuch? Wie wäre es mit 1.000 Städten? Fällt dir eine Möglichkeit ein, wie du die Anzahl der Kollisionen verringern kannst?

Bei 500 Städten gäbe es ungefähr 474 Wörterbuchelemente, die mit einem früheren Wert kollidieren (500 - 26), wobei jeder Hash 500 / 26 = 19,2 Städte zugeordnet ist. Bei 1.000 Städten würden 974 Elemente kollidieren, und jeder Hash würde 1.000 / 26 = 38,4 Städte enthalten. Das liegt daran, dass der Hash einfach auf dem numerischen Wert des ersten Buchstabens basiert, der nur einen Wert von A-Z annehmen kann, wodurch nur 26 unabhängige Hash-Werte möglich sind. Das bedeutet, dass eine Abfrage in dieser Tabelle bis zu 38 weitere Abfragen erfordern kann, um den richtigen Wert zu finden. Um dieses Problem zu lösen, müssen wir die Anzahl der möglichen Hash-Werte erhöhen, indem wir andere Aspekte der Stadt im Hash-Wert berücksichtigen. Die Standard-Hash-Funktion für eine Zeichenkette berücksichtigt jedes Zeichen, um die Anzahl der möglichen Werte zu maximieren. Unter "Hash-Funktionen und Entropie" findest du weitere Erklärungen.

Löschung

Wenn ein Wert aus einer Hash-Tabelle gelöscht wird, können wir nicht einfach NULL in den entsprechenden Bereich des Speichers schreiben. Das liegt daran, dass wir NULLs als Sentinel-Wert verwendet haben, während wir nach Hash-Kollisionen gesucht haben. Daher müssen wir einen speziellen Wert schreiben, der besagt, dass der Bucket leer ist, es aber noch Werte geben kann, die bei der Auflösung einer Hash-Kollision berücksichtigt werden müssen. Wenn also "Rom" aus dem Wörterbuch gelöscht wurde, sehen nachfolgende Suchvorgänge nach "Barcelona" zuerst diesen Sentinel-Wert, an dem "Rom" stand, und anstatt anzuhalten, fahren sie fort, die nächsten Indizes zu prüfen, die von index_sequence angegeben werden. Diese leeren Slots können in Zukunft beschrieben werden und werden entfernt, wenn die Größe der Hashtabelle geändert wird.

Größenänderung

Wenn mehr Elemente in die Hashtabelle eingefügt werden, muss die Tabelle selbst angepasst werden, um sie aufzunehmen. Es lässt sich zeigen, dass eine Tabelle, die nicht mehr als zwei Drittel voll ist, optimal Platz spart und gleichzeitig die Anzahl der zu erwartenden Kollisionen in Grenzen hält. Wenn eine Tabelle also diesen kritischen Punkt erreicht, wird sie vergrößert. Dazu wird eine größere Tabelle zugewiesen (d.h. es werden mehr Buckets im Speicher reserviert), die Maske wird an die neue Tabelle angepasst und alle Elemente der alten Tabelle werden wieder in die neue Tabelle eingefügt. Dies erfordert eine Neuberechnung der Indizes, da die geänderte Maske den resultierenden Index verändert. Daher kann die Größenänderung großer Hash-Tabellen ziemlich teuer sein! Da wir diese Größenänderung jedoch nur vornehmen, wenn die Tabelle zu klein ist, und nicht bei jeder Einfügung, sind die amortisierten Kosten einer Einfügung immer nochO(1).⁵

Standardmäßig ist die kleinste Größe eines Wörterbuchs oder einer Menge 8 (d.h., wenn du nur drei Werte speicherst, weist Python immer noch acht Elemente zu) und ändert die Größe um 3×, wenn das Wörterbuch zu mehr als zwei Dritteln gefüllt ist. Sobald also das sechste Element in das ursprünglich leere Wörterbuch eingefügt wird, wird es auf 18 Elemente vergrößert. Sobald das 13. Element in das Objekt eingefügt wird, wird es auf 39, dann auf 81 und so weiter verkleinert, wobei die Größe immer um 3× erhöht wird (wie man die Größe eines Wörterbuchs berechnet, erklären wir in "Hash-Funktionen und Entropie"). Daraus ergibt sich die folgende Anzahl von Werten, die eine Größenänderung des Wörterbuchs auslösen:

6; 18; 39; 81; 165; 333; 669; 1,341; 2,685; 5,373; 10,749; 21,501; 43,005; ...

Es ist wichtig zu wissen, dass eine Hash-Tabelle durch Größenänderung größer oderkleiner werden kann. Das heißt, wenn ausreichend viele Elemente einer Hashtabelle gelöscht werden, kann die Tabelle verkleinert werden. Die Größenänderung erfolgt jedoch nur beim Einfügen.

Hash-Funktionen und Entropie

Objekte in Python sind in der Regel hashfähig, da sie bereits über eingebaute__hash__ und __cmp__ Funktionen verfügen, die mit ihnen verbunden sind. Bei numerischen Typen(int und float) basiert der Hash einfach auf dem Bitwert der Zahl, die sie repräsentieren. Tupel und Strings haben einen Hash-Wert, der auf ihrem Inhalt basiert, d.h. ein Tupel ist unhashbar, wenn es unhashbare Elemente enthält. Listen hingegen können nicht gehasht werden, weil sich ihre Werte ändern können. Da sich die Werte einer Liste ändern können, kann sich auch der Hash-Wert ändern, der die Liste repräsentiert, wodurch sich die relative Position des Schlüssels in der Hash-Tabelle ändern würde.⁶

Benutzerdefinierte Klassen haben auch Standard-Hash- und Vergleichsfunktionen. Die Standardfunktion __hash__ gibt einfach die Platzierung des Objekts im Speicher zurück, wie sie von der eingebauten Funktion id angegeben wird. Ebenso vergleicht der __cmp__Operator den numerischen Wert der Platzierung des Objekts im Speicher.

Das ist im Allgemeinen akzeptabel, denn zwei Instanzen einer Klasse sind in der Regel unterschiedlich und sollten in einer Hashtabelle nicht kollidieren. In manchen Fällen möchten wir jedoch set oder dict Objekte verwenden, um die Elemente eindeutig zu unterscheiden. Nehmen wir die folgende Klassendefinition:

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

Wenn wir mehrere Point Objekte mit denselben Werten für xund y instanziieren würden, wären sie alle unabhängige Objekte im Speicher und hätten somit unterschiedliche Platzierungen im Speicher, wodurch sie alle unterschiedliche Hash-Werte erhalten würden. Das heißt, wenn wir sie alle in ein set einfügen würden, hätten sie alle individuelle Einträge:

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

Wir können dies beheben, indem wir eine eigene Hash-Funktion erstellen, die auf dem tatsächlichen Inhalt des Objekts basiert und nicht auf der Platzierung des Objekts im Speicher. Die Hash-Funktion kann eine beliebige Funktion sein, solange sie für ein und dasselbe Objekt immer das gleiche Ergebnis liefert (es gibt auch Überlegungen zur Entropie der Hash-Funktion, die wir später noch besprechen werden). Die folgende Neudefinition der Klasse Point führt zu den erwarteten Ergebnissen:

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

So können wir Einträge in einem Set oder Wörterbuch erstellen, die durch die Eigenschaften des Point Objekts und nicht durch die Speicheradresse des instanziierten Objekts indiziert sind:

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x109b95910>])
>>> Point(1, 1) in set([p1, p2])
True

Wie bereits bei der Diskussion über Hash-Kollisionen angedeutet, sollte eine benutzerdefinierte Hash-Funktion darauf achten, die Hash-Werte gleichmäßig zu verteilen, um Kollisionen zu vermeiden. Viele Kollisionen verschlechtern die Leistung einer Hash-Tabelle: Wenn die meisten Schlüssel kollidieren, müssen wir ständig die anderen Werte "sondieren" und dabei einen potenziell großen Teil des Wörterbuchs ablaufen, um den fraglichen Schlüssel zu finden. Im schlimmsten Fall, wenn alle Schlüssel in einem Wörterbuch miteinander kollidieren, ist die Leistung von Nachschlagewerken im Wörterbuch O(n) und damit die gleiche, als ob wir eine Liste durchsuchen würden.

Wenn wir wissen, dass wir 5.000 Werte in einem Wörterbuch speichern und eine Hash-Funktion für das Objekt erstellen müssen, das wir als Schlüssel verwenden wollen, müssen wir uns darüber im Klaren sein, dass das Wörterbuch in einer Hashtabelle der Größe 16.384 gespeichert wird⁷ gespeichert wird und daher nur die letzten 14 Bits unseres Hashes zur Erstellung eines Indexes verwendet werden (für eine Hash-Tabelle dieser Größe lautet die Maske bin(16_384 - 1) = 0b11111111111111).

Diese Vorstellung davon, "wie gut meine Hash-Funktion verteilt ist", nennt man die Entropie der Hash-Funktion. Die Entropie ist definiert als

$$S=-\sum _{i}p\left(i\right)-loggen\left(p\left(i\right)\right)$$

Dabei ist p(i) die Wahrscheinlichkeit, dass die Hash-Funktion den Hash-Wert i liefert. Sie ist maximiert, wenn jeder Hash-Wert die gleiche Wahrscheinlichkeit hat, gewählt zu werden. Eine Hash-Funktion, die die Entropie maximiert, wird idealeHash-Funktion genannt, da sie die minimale Anzahl von Kollisionen garantiert.

Für ein unendlich großes Wörterbuch ist die Hash-Funktion, die für ganze Zahlen verwendet wird, ideal. Das liegt daran, dass der Hash-Wert für eine ganze Zahl einfach die ganze Zahl selbst ist! Bei einem unendlich großen Wörterbuch ist der Maskenwert unendlich, und daher berücksichtigen wir alle Bits im Hash-Wert. Daher können wir bei zwei beliebigen Zahlen garantieren, dass ihre Hash-Werte nicht gleich sind.

Wenn wir dieses Wörterbuch jedoch endlich machen würden, könnten wir diese Garantie nicht mehr haben. Bei einem Wörterbuch mit vier Elementen und einer Größe von 8 ist die Maske, die wir verwenden, zum Beispiel0b111. Der Hash-Wert für die Nummer 5 ist also 5 & 0b111 = 5 und der Hash-Wert für 501 ist 501 & 0b111 = 5. Die Einträge werden also kollidieren.

Hinweis

Um die Maske für ein Wörterbuch mit einer beliebigen Anzahl von Elementen, N, zu finden, ermitteln wir zunächst die Mindestanzahl von Eimern, die das Wörterbuch haben muss, um noch zu zwei Dritteln gefüllt zu sein (N * (2 / 3 + 1)). Dann suchen wir die kleinste Wörterbuchgröße, die diese Anzahl von Elementen aufnehmen kann (8; 32; 128; 512; 2.048; usw.) und finden die Anzahl der Bits, die nötig sind, um diese Zahl zu speichern. Wenn wir zum Beispiel N=1039 wählen, müssen wir mindestens 1.731 Bereiche haben, was bedeutet, dass wir ein Wörterbuch mit 2.048 Bereichen brauchen. Die Maske lautet also bin(2048 - 1) = 0b11111111111.

Es gibt keine beste Hash-Funktion für ein endliches Wörterbuch, aber wenn du im Voraus weißt, welcher Wertebereich verwendet wird und wie groß das Wörterbuch sein wird, kannst du eine gute Wahl treffen. Wenn wir zum Beispiel alle 676 Kombinationen von zwei Kleinbuchstaben als Schlüssel in einem Wörterbuch speichern(aa, ab, ac usw.), wäre eine gute Hash-Funktion die in Beispiel 4-6 gezeigte.

Beispiel 4-6. Optimale Hash-Funktion mit zwei Buchstaben

def twoletter_hash(key):
    offset = ord('a')
    k1, k2 = key
    return (ord(k2) - offset) + 26 * (ord(k1) - offset)

Dies ergibt keine Hash-Kollisionen für jede Kombination von zwei Kleinbuchstaben, wenn man eine Maske von 0b1111111111 berücksichtigt (ein Wörterbuch mit 676 Werten wird in einer Hash-Tabelle der Länge 2.048 gespeichert, die eine Maske von bin(2048 - 1) = 0b11111111111 hat).

Beispiel 4-7 zeigt sehr deutlich die Auswirkungen einer schlechten Hash-Funktion für eine benutzerdefinierte Klasse - hier sind die Kosten einer schlechten Hash-Funktion (tatsächlich ist es die schlechtestmögliche Hash-Funktion!) eine 41,8-fache Verlangsamung der Suchvorgänge.

Beispiel 4-7. Zeitliche Unterschiede zwischen guten und schlechten Hashing-Funktionen

import string
import timeit

class BadHash(str):
    def __hash__(self):
        return 42

class GoodHash(str):
    def __hash__(self):
        """
        This is a slightly optimized version of twoletter_hash
        """
        return ord(self[1]) + 26 * ord(self[0]) - 2619

baddict = set()
gooddict = set()
for i in string.ascii_lowercase:
    for j in string.ascii_lowercase:
        key = i + j
        baddict.add(BadHash(key))
        gooddict.add(GoodHash(key))

badtime = timeit.repeat(
    "key in baddict",
    setup = "from __main__ import baddict, BadHash; key = BadHash('zz')",
    repeat = 3,
    number = 1_000_000,
)
goodtime = timeit.repeat(
    "key in gooddict",
    setup = "from __main__ import gooddict, GoodHash; key = GoodHash('zz')",
    repeat = 3,
    number = 1_000_000,
)

print(f"Min lookup time for baddict: {min(badtime)}")
print(f"Min lookup time for gooddict: {min(goodtime)}")

# Results:
#   Min lookup time for baddict: 17.719061855008476
#   Min lookup time for gooddict: 0.42408075400453527

Übung

1. Zeige, dass es bei einem unendlichen Wörterbuch (und damit einer unendlichen Maske) keine Kollisionen gibt, wenn du den Wert einer ganzen Zahl als Hashwert verwendest.

2. Zeige, dass die inBeispiel 4-6 angegebene Hash-Funktion ideal für eine Hash-Tabelle der Größe 2.024 ist. Warum ist sie für kleinere Hash-Tabellen nicht ideal?

Wörterbücher und Namensräume

Das Nachschlagen in einem Wörterbuch ist schnell, aber wenn du es unnötigerweise tust, wird dein Code langsamer, genau wie alle anderen Zeilen. Ein Bereich, in dem dies deutlich wird, ist die Verwaltung von Namensräumen in Python, die häufig Wörterbücher zum Nachschlagen verwendet.

Jedes Mal, wenn eine Variable, eine Funktion oder ein Modul in Python aufgerufen wird, gibt es eine Hierarchie, die bestimmt, wo nach diesen Objekten gesucht wird. Zuerst schaut Python im Array locals() nach, das Einträge für alle lokalen Variablen enthält. Python arbeitet hart daran, die Suche nach lokalen Variablen schnell zu machen, und dies ist der einzige Teil der Kette, der keine Suche im Wörterbuch erfordert. Wenn das Objekt dort nicht vorhanden ist, wird das Wörterbuch globals() durchsucht. Wenn das Objekt dort nicht gefunden wird, wird das __builtin__ Objekt durchsucht. Es ist wichtig zu wissen, dass locals() und globals() explizit Wörterbücher sind und __builtin__technisch gesehen ein Modulobjekt ist. Wenn wir __builtin__ nach einer bestimmten Eigenschaft durchsuchen, führen wir lediglich eine Wörterbuchsuche in der locals() Map durch (das gilt für alle Modulobjekte und Klassenobjekte!).

Um dies zu verdeutlichen, schauen wir uns ein einfaches Beispiel für den Aufruf von Funktionen an, die in verschiedenen Bereichen definiert sind(Beispiel 4-8). Wir können die Funktionen mit dem Modul dis disassemblieren(Beispiel 4-9), um besser zu verstehen, wie diese Namespace-Lookups ablaufen (siehe "Verwendung des dis-Moduls zur Untersuchung von CPython-Bytecode").

Beispiel 4-8. Nachschlagen von Namensräumen

import math
from math import sin

def test1(x):
    """
    >>> %timeit test1(123_456)
    162 µs ± 3.82 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    """
    res = 1
    for _ in range(1000):
        res += math.sin(x)
    return res

def test2(x):
    """
    >>> %timeit test2(123_456)
    124 µs ± 6.77 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    """
    res = 1
    for _ in range(1000):
        res += sin(x)
    return res

def test3(x, sin=math.sin):
    """
    >>> %timeit test3(123_456)
    105 µs ± 3.35 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    """
    res = 1
    for _ in range(1000):
        res += sin(x)
    return res

Beispiel 4-9. Demontierte Namensraum-Lookups

>>> dis.dis(test1)
    ...cut..
             20 LOAD_GLOBAL              1 (math)
             22 LOAD_METHOD              2 (sin)
             24 LOAD_FAST                0 (x)
             26 CALL_METHOD              1
    ...cut..

>>> dis.dis(test2)
    ...cut...
             20 LOAD_GLOBAL              1 (sin)
             22 LOAD_FAST                0 (x)
             24 CALL_FUNCTION            1
    ...cut...

>>> dis.dis(test3)
    ...cut...
             20 LOAD_FAST                1 (sin)
             22 LOAD_FAST                0 (x)
             24 CALL_FUNCTION            1
    ...cut...

Die erste Funktion, test1, ruft sin auf, indem sie explizit in der mathematischen Bibliothek nachschaut. Das zeigt sich auch im erzeugten Bytecode: Zuerst muss ein Verweis auf das Modul math geladen werden, und dann führen wir eine Attributsuche in diesem Modul durch, bis wir schließlich einen Verweis auf die Funktion sin haben. Dies geschieht durch zwei Wörterbuchabfragen: eine, um das Modul math zu finden, und eine, um die Funktionsin innerhalb des Moduls zu finden.

Andererseits importiert test2 explizit die Funktion sin aus dem Modul math, und die Funktion ist dann direkt im globalen Namensraum zugänglich. Das bedeutet, dass wir die Suche im Modul math und die anschließende Suche nach Attributen vermeiden können. Allerdings müssen wir die Funktion sin immer noch im globalen Namensraum finden. Das ist ein weiterer Grund, warum du genau angeben solltest, welche Funktionen du aus einem Modul importierst. Diese Praxis macht den Code nicht nur lesbarer, weil der Leser genau weiß, welche Funktionen aus externen Quellen benötigt werden, sondern vereinfacht auch die Änderung der Implementierung bestimmter Funktionen und beschleunigt den Code im Allgemeinen!

Schließlich definiert test3 die Funktion sin als Schlüsselwortargument, dessen Standardwert ein Verweis auf die Funktion sin innerhalb des Moduls math ist. Wir müssen zwar immer noch einen Verweis auf diese Funktion innerhalb des Moduls finden, aber das ist nur notwendig, wenn die Funktion test3 zum ersten Mal definiert wird. Danach wird der Verweis auf die Funktion sin innerhalb der Funktionsdefinition als lokale Variable in Form eines Standard-Schlüsselwortarguments gespeichert. Wie bereits erwähnt, müssen lokale Variablen nicht im Wörterbuch nachgeschlagen werden; sie werden in einem sehr schlanken Array gespeichert, das sehr schnelle Suchzeiten hat. Aus diesem Grund ist das Auffinden der Funktion ziemlich schnell!

Diese Effekte sind zwar ein interessantes Ergebnis der Art und Weise, wie Namensräume in Python verwaltet werden, aber test3 ist definitiv nicht "pythonisch". Glücklicherweise beeinträchtigen diese zusätzlichen Wörterbuchabfragen die Leistung nur dann, wenn sie häufig aufgerufen werden (z. B. im innersten Block einer sehr schnellen Schleife, wie im Beispiel der Julia-Menge). Eine bessere Lösung wäre es, eine lokale Variable mit der globalen Referenz zu setzen, bevor die Schleife gestartet wird. Wir müssen dann zwar immer noch einmal nach der globalen Referenz suchen, wenn die Funktion aufgerufen wird, aber alle Aufrufe der Funktion in der Schleife werden schneller ausgeführt. Das zeigt, dass selbst kleine Verlangsamungen im Code verstärkt werden können, wenn der Code Millionen Mal ausgeführt wird. Auch wenn eine Wörterbuchabfrage selbst nur einige hundert Nanosekunden dauert, können sich diese Nanosekunden schnell summieren, wenn wir diese Abfrage millionenfach in einer Schleife durchführen.

Hinweis

Ein Hinweis zu Mikrobenchmarks: Es mag verwirrend erscheinen, dass wir in Beispiel 4-8 mit der Schleife for und der Änderung der Variable res zusätzliche Arbeit hinzufügen. Ursprünglich hatte jede dieser Funktionen nur die entsprechende return sin(x) Zeile und sonst nichts. Das führte dazu, dass wir Laufzeiten von Nanosekunden und Ergebnisse erhielten, die keinen Sinn ergaben!

Als wir innerhalb jeder Funktion eine größere Arbeitslast hinzufügten, wie durch die Schleife und die Änderung der Variable res, bekamen wir die erwarteten Ergebnisse. Mit einer größeren Arbeitslast innerhalb der Funktion können wir sicherer sein, dass wir keinen Overhead durch den Benchmarking-/Zeitmessungsprozess messen. Wenn du Benchmarks durchführst und einen Unterschied in der Zeitmessung im Nanosekundenbereich feststellst, ist es wichtig, dass du dich kurz zurücklehnst und überlegst, ob das Experiment, das du durchführst, gültig ist oder ob du Rauschen oder nicht zusammenhängende Zeitmessungen als Ergebnis der Instrumentierung misst.

Nachbereitung

Dictionaries und Sets bieten eine fantastische Möglichkeit, Daten zu speichern, die durch einen Schlüssel indiziert werden können. Die Art und Weise, wie dieser Schlüssel durch die Hashing-Funktion verwendet wird, kann die Leistung der Datenstruktur stark beeinflussen. Wenn du verstehst, wie Wörterbücher funktionieren, weißt du nicht nur besser, wie du deine Daten organisieren kannst, sondern auch, wie du deinen Code organisieren musst, denn Wörterbücher sind ein wesentlicher Bestandteil der internen Funktionen von Python .

Im nächsten Kapitel werden wir uns mit Generatoren beschäftigen, die es uns ermöglichen, dem Code Daten mit mehr Kontrolle über die Reihenfolge zur Verfügung zu stellen, ohne dass wir vorher ganze Datensätze im Speicher ablegen müssen. Auf diese Weise können wir viele der Hürden umgehen, die bei der Verwendung von Python-eigenen Datenstrukturen auftreten können.

¹ Wie wir in "Hash-Funktionen und Entropie" erläutern werden , sind Wörterbücher und Mengen sehr stark von ihren Hash-Funktionen abhängig. Wenn die Hash-Funktion für einen bestimmten Datentyp nicht O(1) ist, hat jedes Wörterbuch oder jede Menge, die diesen Typ enthält, nicht mehr seine O(1) Garantie.

² Eine Maske ist eine Binärzahl, die den Wert einer Zahl abschneidet. So steht 0b1111101 & 0b111 = 0b101 = 5 für die Operation 0b111, bei der die Zahl 0b1111101 maskiert wird. Diese Operation kann man sich auch so vorstellen, dass man eine bestimmte Anzahl der niederwertigsten Stellen einer Zahl nimmt.

³ Die Diskussion, die zu dieser Verbesserung führte, findest du unter https://oreil.ly/Pq7Lm.

⁴ Der Wert von 5 ergibt sich aus den Eigenschaften eines linearen kongruenten Generators (LCG), der bei der Erzeugung von Zufallszahlen verwendet wird.

⁵ Die amortisierte Analyse betrachtet die durchschnittliche Komplexität eines Algorithmus. Das bedeutet, dass einige Einfügungen viel teurer sein werden, aber im Durchschnitt werden die Einfügungen O(1) sein.

⁶ Weitere Informationen dazu findest du unter https://oreil.ly/g4I5-.

⁷ 5.000 Werte benötigen ein Wörterbuch mit mindestens 8.333 Feldern. Die erste verfügbare Größe, in die so viele Elemente passen, ist 16.384.