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 [2024-01-22 14:01] – ↷ Links angepasst weil Seiten im Wiki verschoben wurden 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 105: Zeile 104:
 ### Variante 2: Binary Search ### Variante 2: Binary Search
  
-Natürlich möchten wir schneller sein als linear - zum Glück erinnern wir uns an die Informatik 1 und die [[gf_informatik:suchen_und_sortieren_2023:binaersuche|Binärsuche]]!+Natürlich möchten wir schneller sein als linear - zum Glück erinnern wir uns an die Informatik 1 und die [[gf_informatik:suchen_und_sortieren:binaersuche|Binärsuche]]!
  
 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.
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 #### Hashing
  
Zeile 178: 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 187: Zeile 183:
  
 <nodisp 1> <nodisp 1>
-++++Mit linear Probing:|+++++Mit Linear Probing:|
 <code python> <code python>
 class HashMap(TupleList): class HashMap(TupleList):
Zeile 308: 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 330: 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.1705932076.txt.gz
  • Zuletzt geändert: 2024-01-22 14:01
  • von hof