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:47] – [Variante 3 - Hash-Map] hofgf_informatik:daten:processing:dictionaries_tutorial [2026-05-25 10:14] (aktuell) – [Aufgabe 3 - HashMap] hof
Zeile 64: Zeile 64:
 print(map['one'])   print(map['one'])  
 </code> </code>
- 
  
 #### Laufzeit-Messung #### Laufzeit-Messung
Zeile 158: Zeile 157:
 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 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 $\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 [[wpde>Landau-Symbole|Komplexität]] $\mathcal{O}(log(n))$ hat. 
 +#### 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 $\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. 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.
  
 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 174: Zeile 176:
  
 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.
- 
- 
 #### Aufgabe 3 - HashMap #### Aufgabe 3 - HashMap
 Implementiere eine `class HashMap`. Implementiere eine `class HashMap`.
Zeile 183: Zeile 183:
  
 <nodisp 1> <nodisp 1>
-++++Mit linear Probing:|+++++Mit Linear Probing:|
 <code python> <code python>
 class HashMap(TupleList): class HashMap(TupleList):
Zeile 304: Zeile 304:
  
     def __delitem__(self, key):     def __delitem__(self, key):
-        return self._finditem(key).__delitem__(key)+        item = self._finditem(key).__delitem__(key) 
 +        self._len -= 1 
 +        return item
  
     def __setitem__(self, key, value):     def __setitem__(self, key, value):
Zeile 326: Zeile 328:
                 if entry:                 if entry:
                     for key in entry:                     for key in entry:
-                        self._finditem(key, raise_on_notfound=False)[key] = entry[key]+                        self._finditem(key, False)[key] = entry[key]
 </code> </code>
 ++++ ++++
 </nodisp> </nodisp>
  • gf_informatik/daten/processing/dictionaries_tutorial.1685375265.txt.gz
  • Zuletzt geändert: 2023-05-29 15:47
  • von hof