Wörterbuchimplementierung in Python

Hallo allerseits, am 30. April beginnt der Kurs Algorithmen für Entwickler bei OTUS, und die Veröffentlichung des heutigen Materials ist diesem Thema gewidmet. Fangen wir an.



In diesem Artikel erfahren Sie, wie Wörterbücher in Python implementiert werden.
Wörterbücher werden mithilfe von Schlüsseln indiziert und können als zugeordnete Arrays betrachtet werden. Fügen wir dem Wörterbuch 3 Schlüssel / Wert-Paare hinzu:

>>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3} 

Auf Werte kann wie folgt zugegriffen werden:

 >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'd' 

Der Schlüssel “d” ist nicht vorhanden, daher tritt ein KeyError-Fehler auf.

Hash-Tabellen

Wörterbücher in Python werden mithilfe von Hash-Tabellen implementiert. Dies sind Arrays, deren Indizes mithilfe von Hash-Funktionen berechnet werden. Das Ziel der Hash-Funktion besteht darin, die Schlüssel im Array gleichmäßig zu verteilen. Eine gute Hash-Funktion minimiert die Anzahl von Kollisionen, d.h. die Wahrscheinlichkeit, dass verschiedene Schlüssel denselben Hash haben. In Python gibt es keine solchen Hash-Funktionen. Die wichtigsten Hash-Funktionen (für Zeichenfolgen und ganzzahlige Werte) erzeugen im Allgemeinen ähnliche Werte:

 >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462] 

Wir gehen davon aus, dass wir bis zum Ende dieses Artikels Zeichenfolgen als Schlüssel verwenden werden. Die Hash-Funktion in Python für Zeichenfolgen ist wie folgt definiert:

 arguments: string object returns: hash function string_hash: if hash cached: return it set len to string's length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don't need to calculate it again return x as the hash 

Wenn Sie in Python hash('a') 12416037344 , wird string_hash() und 12416037344 . Hier verwenden wir standardmäßig die 64-Bit-Maschine.

Wenn ein Array der Größe zum Speichern der Wert / Schlüssel-Paare verwendet wird, wird eine Maske verwendet, um den Index der Zelle der Zelle im Array zu berechnen, der als -1 berechnet wird. Dieser Ansatz erleichtert die Berechnung von Zellindizes. Die Wahrscheinlichkeit, eine leere Zelle zu finden, ist aufgrund des unten beschriebenen Größenänderungsmechanismus ziemlich hoch. Dies bedeutet, dass eine einfache Berechnung in den meisten Fällen sinnvoll ist. Die Größe des Arrays beträgt 8, der Index für 'a' lautet: hash('a') & 7 = 0 . Der Index für 'b' ist 2, der Index für 'c' ist 3, der Index für 'z' ist 3, genau wie für 'b' , und hier erhalten wir eine Kollision.



Wie wir sehen können, erledigt eine Hash-Funktion in Python ihre Arbeit auf qualitativ hochwertige Weise, wenn die Schlüssel sequentiell sind, was gut ist, da Sie häufig mit solchen Daten arbeiten müssen. Sobald wir jedoch die Taste 'z' hinzufügen, tritt eine Kollision auf, da diese nicht mit den vorherigen übereinstimmt.

Wir könnten eine verknüpfte Liste verwenden, um Paare mit demselben Hash zu speichern, aber dies würde die Suchzeit verlängern und im Durchschnitt nicht gleich O (1) sein. Der folgende Abschnitt beschreibt die Kollisionsauflösungsmethode, die für Wörterbücher in Python verwendet wird.

Offene Adressierung

Open Addressing ist eine Kollisionsauflösungstechnik, bei der die Prüfung verwendet wird. Im Fall von 'z' wird der Index von Zelle 3 bereits im Array verwendet, daher müssen wir nach einem anderen Index suchen, der noch nicht verwendet wurde. Der Vorgang des Hinzufügens eines Schlüssel / Wert-Paares erfordert im Durchschnitt O (1) sowie den Suchvorgang.

Um nach freien Zellen zu suchen, wird eine quadratische Abtastsequenz verwendet. Es wird wie folgt implementiert:

 j = (5*j) + 1 + perturb; perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index; 

Die Rekursion bei (5 * j) +1 erhöht schnell große Unterschiede in Bits, die den ursprünglichen Index nicht beeinflusst haben. Die Variable "perturb" in diesem Fall die anderen Bits des Hash-Codes auf.

Lassen Sie uns aus Neugier schauen, was passiert, wenn wir eine Beispielsequenz mit der Tabellengröße 32 und j = 3 haben.

3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2 ...

Weitere Informationen zu dieser Prüfsequenz finden Sie im Quellcode dictobject.c . Eine ausführliche Erläuterung des Prüfmechanismus finden Sie oben in der Datei.



Schauen wir uns den Python-Quellcode mit diesem Beispiel an.

C Wörterbuchstrukturen

Die folgende C-Struktur wird verwendet, um den Eintrag im Wörterbuch zu speichern: Schlüssel / Wert-Paar. Der Hash, der Schlüssel und der Wert werden gespeichert. PyObject ist die Basisklasse für Objekte in Python.

 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry; 

Die folgende Struktur ist ein Wörterbuch. ma_fill ist die Gesamtzahl der verwendeten und inaktiven Zellen. Eine Zelle gilt als inaktiv, wenn ein Schlüsselpaar gelöscht wird. ma_used ist die Anzahl der verwendeten (aktiven) Zellen. ma_mask entspricht der Größe des -1-Arrays und wird zur Berechnung des Zellenindex verwendet. ma_table ist ein Array und ma_smalltable ist das ursprüngliche Array der Größe 8.

 typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; }; 

Wortschatzinitialisierung

Wenn Sie nur ein Wörterbuch erstellen, wird die Funktion PyDict_New() . Ich habe einige Zeilen gelöscht und den C-Code in Pseudocode konvertiert, um mich auf Schlüsselkonzepte zu konzentrieren.

PyDict_New() -Funktion:

• Gibt ein Wörterbuchobjekt zurück.
• Ordnet ein neues Wörterbuchobjekt zu.
• Löscht die Wörterbuchtabelle.
• Setzt die Anzahl der verwendeten Wörterbuchzellen und nicht verwendeten Zellen ( ma_fill ) auf 0;
• Setzt die Anzahl der aktiven Zellen ( ma_used ) auf 0;
• Setzt die Wörterbuchmaske ( ma_value ) auf einen Wert, der der Größe des Wörterbuchs entspricht - 1 = 7;
• Legt die Wörterbuchsuchfunktion lookdict_string .
• Gibt das zugewiesene Wörterbuchobjekt zurück.

Element hinzufügen

Wenn ein neues Schlüssel / Wert-Paar hinzugefügt wird, wird PyDict_SetItem() aufgerufen. Diese Funktion akzeptiert einen Zeiger auf ein Wörterbuchobjekt und ein Schlüssel / Wert-Paar als Eingabe. Es prüft, ob der Schlüssel eine Zeichenfolge ist, wertet den Hash aus oder verwendet den zwischengespeicherten erneut, falls vorhanden. insertdict() wird aufgerufen, um ein neues Schlüssel / Wert-Paar hinzuzufügen, und die Wörterbuchgröße ändert sich, wenn die Anzahl der verwendeten und nicht verwendeten Zellen mehr als 2/3 der Größe des Arrays beträgt.

Warum genau 2/3? Dies ist notwendig, um sicherzustellen, dass die Sondensequenz freie Zellen schnell genug finden kann. Später werden wir die Funktion zum Ändern der Größe betrachten.

 arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key's hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary's table 

inserdict() verwendet die lookdict_string() , um eine freie Zelle zu finden. Die gleiche Funktion wird verwendet, um nach einem Schlüssel zu suchen.

lookdict_string() berechnet den Zellenindex mithilfe von Hash- und lookdict_string() . Wenn sie den Schlüssel nicht anhand des Werts von Zellenindex = Hash & Maske (Slot-Index = Hash & Maske) finden kann, beginnt sie mit der Prüfung mit dem oben beschriebenen Zyklus, bis sie eine freie Zelle findet. Wenn der Schlüssel beim ersten Versuch zu prüfen ist, wird eine nicht verwendete Zelle zurückgegeben, wenn sie bei der ersten Suche gefunden wurde. Dies stellt die Priorität für die Wiederverwendung zuvor gelöschter Zellen sicher.
Wir möchten die folgenden Schlüssel / Wert-Paare hinzufügen: {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} . Folgendes wird passieren:

Die Wörterbuchstruktur wird mit einer Tabellengröße von 8 zugewiesen.

• PyDict_SetItem: key = 'a', value = 1
  
  • Hash = Hash ('a') = 12416037344
  • insertdict
    
    • lookdict_string
      
      • Slot Index = Hash & Maske = 12416037344 & 7 = 0
      • Steckplatz 0 wird nicht verwendet. Geben Sie diese Zelle zurück
    • Initialisierung des Eintrags bei Index 0 mit Schlüssel, Wert und Hash
    • ma_used = 1, ma_fill = 1
• PyDict_SetItem: key = 'b', value = 2
  
  • Hash = Hash ('b') = 12544037731
  • insertdict
    
    • lookdict_string
      
      • Slot Index = Hash & Maske = 12544037731 & 7 = 3
      • Steckplatz 3 wird nicht verwendet. Geben Sie diese Zelle zurück
    • Initialisierung des Eintrags bei Index 3 mit Schlüssel, Wert und Hash
    • ma_used = 2, ma_fill = 2
      
• PyDict_SetItem: key = 'z', value = 26
  
  • Hash = Hash ('z') = 15616046971
  • insertdict
    
    • lookdict_string
      
      • Slot Index = Hash & Maske = 15616046971 & 7 = 3
      • Steckplatz 3 wird verwendet, versuchen Sie es mit einer anderen Zelle: 5 ist frei
        
      
      Initialisierung des Eintrags bei Index 5 mit Schlüssel, Wert und Hash
      ma_used = 3, ma_fill = 3
      
• PyDict_SetItem: key = 'y', value = 25
  
  • Hash = Hash ('y') = 15488046584
  • insertdict
    
    • lookdict_string
      
      • Slot Index = Hash & Maske = 15488046584 & 7 = 0
      • Steckplatz 0 wird verwendet, versuchen Sie es mit einer anderen Zelle: 1 ist frei
    • Initialisierung des Eintrags bei Index 1 mit Schlüssel, Wert und Hash
    • ma_used = 4, ma_fill = 4

PyDict_SetItem: key = 'c', value = 3

• Hash = Hash ('c') = 12672038114
• insertdict
  
  • lookdict_string
    
    • Slot Index = Hash & Maske = 12672038114 & 7 = 2
    • Steckplatz 2 wird nicht verwendet. Geben Sie diese Zelle zurück
  • Initialisierung des Eintrags bei Index 2 mit Schlüssel, Wert und Hash
  • ma_used = 5, ma_fill = 5

PyDict_SetItem: key = 'x', value = 24

• Hash = Hash ('x') = 15360046201
• insertdict
  
  • lookdict_string
    
    • Slot Index = Hash & Maske = 15360046201 & 7 = 1
    • Steckplatz 1 wird verwendet, versuchen Sie es mit einer anderen Zelle: 7 ist frei
  • Initialisierung des Eintrags bei Index 7 mit Schlüssel, Wert und Hash
  • ma_used = 6, ma_fill = 6

Folgendes bekommen wir:



Jetzt werden 6 von 8 Zellen verwendet, mehr als 2/3 der Array-Kapazität sind belegt. dictresize() wird aufgerufen, um ein größeres Array zuzuweisen. Diese Funktion kopiert auch Datensätze aus der alten Tabelle in die neue.

dictresize () wird in unserem Fall mit minused = 24 aufgerufen, wobei 4 * ma_used . 2 * ma_used verwendet, wenn die Anzahl der verwendeten Zellen sehr groß ist (mehr als 50.000). Warum sind 4 mal mehr Zellen? Dies reduziert die Anzahl der Schritte zum Implementieren der Größenänderung und erhöht die Spärlichkeit.

Die neue Größe der Tabelle sollte größer als 24 sein. Sie wird berechnet, indem die aktuelle Größe um 1 Bit nach links verschoben wird, bis die Größe der Tabelle größer als 24 wird. Infolgedessen sind es 32, z. B. 8 -> 16 -> 32.

Folgendes passiert mit unserer Tabelle während der Größenänderung: Eine neue Tabelle der Größe 32 wird hervorgehoben. Alte Tabelleneinträge werden mit einem neuen Maskenwert von 31 in die neue Tabelle eingefügt. Das Ergebnis ist das Folgende:



Elemente löschen

PyDict_DelItem() wird aufgerufen, um Datensätze zu löschen. Der Hash wird für den Datensatzschlüssel berechnet, dann wird die Suchfunktion aufgerufen, um den Datensatz zurückzugeben. Jetzt ist die Zelle leer.

Wir möchten den Schlüssel c aus unserem Wörterbuch entfernen. Als Ergebnis erhalten wir das folgende Array:



Beachten Sie, dass durch das Löschen eines Elements die Größe des Arrays nicht geändert wird, wenn die Anzahl der verwendeten Zellen viel geringer ist als ihre Gesamtzahl. Wenn jedoch ein Schlüssel / Wert-Paar hinzugefügt wird, hängt die Notwendigkeit einer Größenänderung von der Anzahl der verwendeten und inaktiven Zellen ab, sodass die Additionsoperation auch das Array reduzieren kann.

Diese Veröffentlichung ist zu Ende gegangen, und wir warten traditionell auf Ihre Kommentare und laden alle zu einer offenen Lektion ein , die am 18. April stattfinden wird.