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 [2024-06-10 10:53] (aktuell) – hof
Zeile 98: Zeile 98:
 </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 105: Zeile 105:
 ### 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 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 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 Komplexität $O(log(n))$ hat.
  
 #### Hashing #### 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 $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.
  • gf_informatik/daten/processing/dictionaries_tutorial.1705932076.txt.gz
  • Zuletzt geändert: 2024-01-22 14:01
  • von hof