Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:daten:processing:dictionaries_tutorial [2023-05-29 15:45] – hof
+++ gf_informatik:daten:processing:dictionaries_tutorial [2024-06-10 10:53] (aktuell) – hof
@@ Zeile 98: / Zeile 98: @@
 </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
@@ Zeile 158: / Zeile 158: @@
 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.
+#### 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]]: