Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
gf_informatik:daten:processing:dictionaries_tutorial [2023-05-29 15:21] – [Variante 3 - Hash-Map] hofgf_informatik:daten:processing:dictionaries_tutorial [2024-06-10 10:53] (aktuell) – hof
Zeile 13: Zeile 13:
 Eine einfache Möglichkeit, in Python selber ein Dictionary zu implementieren, wäre eine Liste von Tupeln `(key, value)` zu speichern. Ein [[https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences|Tupel]] ist nichts anderes als eine unveränderliche Liste und wird (fast) immer in runde Klammern eingebettet. Eine einfache Möglichkeit, in Python selber ein Dictionary zu implementieren, wäre eine Liste von Tupeln `(key, value)` zu speichern. Ein [[https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences|Tupel]] ist nichts anderes als eine unveränderliche Liste und wird (fast) immer in runde Klammern eingebettet.
  
-Wenn wir möchten, dass unsere TupelListe die Python Syntax mit eckigen Klammern unterstützt, verwenden wir für die obigen Operationen die folgenden [[https://docs.python.org/3/reference/datamodel.html#specialnames|Special Method Names]]:+Wenn wir möchten, dass unsere Tupel-Liste die Python Syntax mit eckigen Klammern unterstützt, verwenden wir für die obigen Operationen die folgenden [[https://docs.python.org/3/reference/datamodel.html#specialnames|Special Method Names]]:
  
   * Lookup: ''[[https://docs.python.org/3/reference/datamodel.html#object.__getitem__|__getitem__(key)]]''   * Lookup: ''[[https://docs.python.org/3/reference/datamodel.html#object.__getitem__|__getitem__(key)]]''
Zeile 23: Zeile 23:
  
 <code python> <code python>
-class TupelList:+class TupleList:
     """A linear mapping type using list of (key, value) tuples."""     """A linear mapping type using list of (key, value) tuples."""
     def __init__(self):     def __init__(self):
Zeile 56: Zeile 56:
             yield k             yield k
          
-map = TupelList()       # calls __init__+map = TupleList()       # calls __init__
 map['one'] = 42         # calls __setitem__ map['one'] = 42         # calls __setitem__
 map['two'] = 21 map['two'] = 21
Zeile 88: Zeile 88:
         print(f"{map_type.__name__}: N={count:7}  Time per Op: {time_per_op:2.1e}")         print(f"{map_type.__name__}: N={count:7}  Time per Op: {time_per_op:2.1e}")
  
-perf_test(TupelList)+perf_test(TupleList)
 </code> </code>
  
 Output: Output:
 <code> <code>
-TupelList: N=   100  Time per Op: 5.4e-06 +TupleList: N=   100  Time per Op: 5.4e-06 
-TupelList: N=  1000  Time per Op: 2.9e-05 +TupleList: N=  1000  Time per Op: 2.9e-05 
-TupelList: N= 10000  Time per Op: 2.5e-04+TupleList: N= 10000  Time per Op: 2.5e-04
 </code> </code>
  
-Die Zeit, um eine einzelne Zuordnung abzurufen wächst also linear mit der Anzahl Zuordnungen - wir sagen auch, dass die Lookup-Operation eine Laufzeit-Komplexität von $\mathcal{O}(n)$ hat.+Die Zeit, um eine einzelne Zuordnung abzurufen wächst also linear mit der Anzahl Zuordnungen - wir sagen auch, dass die Lookup-Operation eine Laufzeit-Komplexität von $O(n)$ hat.
  
 #### Aufgabe 1 - Zeitmessung #### Aufgabe 1 - Zeitmessung
Zeile 108: Zeile 108:
  
 Falls die verwendeten Schlüssel miteinander vergleichbar sind, könnten wir die Tupel-Liste ja sortieren, der Zugriff sollte dementsprechend schneller sein. Mathematiker sprechen auch davon, dass eine [[wpde>Ordnungsrelation#Totalordnung|Totalordnung]] über die Schlüssel besteht. In Python ist dies der Fall, wenn wir für die Schlüssel Zahlen oder Strings (lexikographische Ordnung) verwenden, oder wenn die Schlüssel die [[https://docs.python.org/3/reference/datamodel.html#object.__lt__|Spezial-Funktionen für die Ordnung]] aufweisen. Falls die verwendeten Schlüssel miteinander vergleichbar sind, könnten wir die Tupel-Liste ja sortieren, der Zugriff sollte dementsprechend schneller sein. Mathematiker sprechen auch davon, dass eine [[wpde>Ordnungsrelation#Totalordnung|Totalordnung]] über die Schlüssel besteht. In Python ist dies der Fall, wenn wir für die Schlüssel Zahlen oder Strings (lexikographische Ordnung) verwenden, oder wenn die Schlüssel die [[https://docs.python.org/3/reference/datamodel.html#object.__lt__|Spezial-Funktionen für die Ordnung]] aufweisen.
 +
 #### Aufgabe 2 - Sortierte Tupel-Liste #### Aufgabe 2 - Sortierte Tupel-Liste
-Implementiere eine `class SortedTupelList` - Hinweise: +Implementiere eine `class SortedTupleList` - Hinweise: 
-  * Wir können von `TupelList` erben: `class SortedTupelList(TupelList)` um einigen Code wiederzuverwenden:+  * Wir können von `TupleList` erben: `class SortedTupleList(TupleList)` um einigen Code wiederzuverwenden:
     * Die private Methode `_finditem(key)` muss angepasst werden um die Binärsuche zu implementieren.     * Die private Methode `_finditem(key)` muss angepasst werden um die Binärsuche zu implementieren.
     * In `__getitem__` und `__delitem__` bleiben sich gleich und müssen nicht angepasst werden.     * In `__getitem__` und `__delitem__` bleiben sich gleich und müssen nicht angepasst werden.
Zeile 120: Zeile 121:
 ++++Lösung:| ++++Lösung:|
 <code python> <code python>
-class SortedTupelList(TupelList):+class SortedTupleList(TupleList):
     """A logarithmic mapping type using a sorted list of (key, value) tuples."""     """A logarithmic mapping type using a sorted list of (key, value) tuples."""
     # Override _finditem to use binary search     # Override _finditem to use binary search
Zeile 157: Zeile 158:
 Können wir noch schneller sein als Binärsuche? Können wir noch schneller sein als Binärsuche?
  
-Binärsuche ist sehr viel schneller als lineare Suche: jedes Mal wenn wir die Anzahl Einträge quadrieren vergrössert sich die Zeit um einen konstanten Faktor. Mann kann auch sagen, dass die Zeit pro Lookup mit dem Logarithmus der Anzahl Einträge wächst, oder dass Lookup die Komplexität $\mathcal{O}(log(n))$ hat.+Binärsuche ist sehr viel schneller als lineare Suche: jedes Mal, wenn wir die Anzahl Einträge verdoppeln, vergrössert sich die Zeit um einen konstanten Faktor. Alternative Betrachtung: werden die Anzahl Einträge quadriert, verdoppelt sich die Zeit. Mann kann auch sagen, dass die Zeit pro Lookup mit dem Logarithmus der Anzahl Einträge wächst, oder dass Lookup die Komplexität $O(log(n))$ hat.
  
-Allerdings wissen wir auch, dass der eigentliche Zugriff auf die zugrundeliegende Liste nicht von deren Grösse abhängt. Wenn wir den richtigen Index kennen würden, könnten wir den Zugriff in konstanter Zeit (oder $\mathcal{O}(1)$) schaffen. Dies wird mit einer Hashmap erreicht, indem der Index aus dem Key berechnet wird. Dazu wird für jedes Key-Objekt ein _Hashwert_ (eine Ganzzahl) berechnet. Aus dem Hashwert wird der Index in der Tupel-Liste mittels `hash % len(self.tuples)` berechnet.+#### Hashing 
 + 
 +Allerdings wissen wir auch, dass der eigentliche Zugriff auf die zugrundeliegende Liste nicht von deren Grösse abhängt. Wenn wir den richtigen Index kennen würden, könnten wir den Zugriff in konstanter Zeit (oder $O(1)$) schaffen. Dies wird mit einer Hashmap erreicht, indem der Index aus dem Key berechnet wird. Dazu wird für jedes Key-Objekt ein _Hashwert_ (eine Ganzzahl) berechnet. Aus dem Hashwert wird der Index in der Tupel-Liste mittels `hash % len(self.tuples)` berechnet.
  
 In Python können wir die eingebaute `hash(object)` Funktion verwenden, um für jedes Objekt einen Hashwert zu erhalten. Für die meisten Objekte ist dies ein Wert, der aus der internen Speicheradresse abgeleitet wird; für Typen, die `__eq__` implementieren, wie beispielsweise Strings, basiert der Hashwert auf dem Inhalt, so dass zwei unterschiedliche String-Instanzen mit dem gleichen Inhalt trotzdem den gleichen Hashwert produzieren. In Python können wir die eingebaute `hash(object)` Funktion verwenden, um für jedes Objekt einen Hashwert zu erhalten. Für die meisten Objekte ist dies ein Wert, der aus der internen Speicheradresse abgeleitet wird; für Typen, die `__eq__` implementieren, wie beispielsweise Strings, basiert der Hashwert auf dem Inhalt, so dass zwei unterschiedliche String-Instanzen mit dem gleichen Inhalt trotzdem den gleichen Hashwert produzieren.
 +
 +#### Kollisionen
  
 Natürlich kann es vorkommen, dass zwei unterschiedliche Keys denselben Index ergeben, eine sogenannte Kollision. Wir müssen also beim Suchen sicherstellen, dass an der berechneten Adresse tatsächlich der gesuchte Key steht. Zur Behandlung von Kollisionen gibt es viele [[wp>Hash_table#Collision_resolution|Möglichkeiten]]: Natürlich kann es vorkommen, dass zwei unterschiedliche Keys denselben Index ergeben, eine sogenannte Kollision. Wir müssen also beim Suchen sicherstellen, dass an der berechneten Adresse tatsächlich der gesuchte Key steht. Zur Behandlung von Kollisionen gibt es viele [[wp>Hash_table#Collision_resolution|Möglichkeiten]]:
Zeile 170: Zeile 175:
   * Chaining: Jedes Listenelement ist eine weitere Liste, die wir nach dem richtigen Key durchsuchen.   * Chaining: Jedes Listenelement ist eine weitere Liste, die wir nach dem richtigen Key durchsuchen.
     * Solange die Kollisionsrate tief ist, kostet die lineare Suche kaum Zeit.     * Solange die Kollisionsrate tief ist, kostet die lineare Suche kaum Zeit.
-    * Es bietet sich an, gleich eine `TupelList` von oben zu verwenden - oder `SortedTupelList`, wobei dies bei der zu erwartenden Länge nicht ins Gewicht fällt.+    * Es bietet sich an, gleich eine `TupleList` von oben zu verwenden - oder `SortedTupleList`, wobei dies bei der zu erwartenden Länge nicht ins Gewicht fällt.
  
 Um die Anzahl Kollisionen tief zu halten ist es wichtig, dass die Liste nie ganz gefüllt ist - die Tupel-Liste wird also bewusst grösser gewählt als nötig und bei Bedarf ein _rehash_ ausgeführt: alle Einträge werden in eine neue, grössere Liste umgefüllt, wobei die Indices dann neu berechnet werden müssen. Je nach gewähltem Faktor für die tolerierbare Kollisionszahl benötigt die Hashmap also mehr Speicher, um damit eine bessere Laufzeit zu erreichen. Um die Anzahl Kollisionen tief zu halten ist es wichtig, dass die Liste nie ganz gefüllt ist - die Tupel-Liste wird also bewusst grösser gewählt als nötig und bei Bedarf ein _rehash_ ausgeführt: alle Einträge werden in eine neue, grössere Liste umgefüllt, wobei die Indices dann neu berechnet werden müssen. Je nach gewähltem Faktor für die tolerierbare Kollisionszahl benötigt die Hashmap also mehr Speicher, um damit eine bessere Laufzeit zu erreichen.
Zeile 179: Zeile 184:
  
 Hinweise: Hinweise:
-  * wir können `_tuples` und `__getitem__` wieder von `TupelList` erben.+  * wir können `_tuples` und `__getitem__` wieder von `TupleList` erben.
  
 <nodisp 1> <nodisp 1>
 ++++Mit linear Probing:| ++++Mit linear Probing:|
 <code python> <code python>
-class HashMap(TupelList):+class HashMap(TupleList):
     def __init__(self):     def __init__(self):
         self._tuples = [None] * 10  # The entries (None where empty)         self._tuples = [None] * 10  # The entries (None where empty)
Zeile 268: Zeile 273:
 <code python> <code python>
 class ChainingHashMap: class ChainingHashMap:
-    """A mapping that employs a TupelList in each slot to chain colliding entries."""+    """A mapping that employs a TupleList in each slot to chain colliding entries."""
     def __init__(self):     def __init__(self):
         self._tuples = [None] * 10  # The entries, either None or a linear TupleList.         self._tuples = [None] * 10  # The entries, either None or a linear TupleList.
Zeile 285: Zeile 290:
          
     def _finditem(self, key, raise_on_notfound=True):     def _finditem(self, key, raise_on_notfound=True):
-        """Returns the TupelList at the key's slot or raises an error. +        """Returns the TupleList at the key's slot or raises an error. 
-           If raise_on_notfound is False, an empty TupelList is inserted and returned."""+           If raise_on_notfound is False, an empty TupleList is inserted and returned."""
         h = self._hash(key) % len(self._tuples)         h = self._hash(key) % len(self._tuples)
    
Zeile 295: Zeile 300:
                 raise KeyError(key)                 raise KeyError(key)
             # create a new sublist             # create a new sublist
-            entry = TupelList()+            entry = TupleList()
             self._tuples[h] = entry             self._tuples[h] = entry
         return entry         return entry
  • gf_informatik/daten/processing/dictionaries_tutorial.1685373680.txt.gz
  • Zuletzt geändert: 2023-05-29 15:21
  • von hof