Wir hatten uns die unbeschränkten Felder angeschaut.
Wie kann ich die Operationen Pushback und Popback unterstützen?
Das war relativ einfach.
Ein unbeschränktes Feld ist in unserem Maschinenmodell das gleiche wie
ein beschränktes Feld, es ist einfach ein Stück Speicher.
Und der Trick war, dass ich bei einem Pushback, wenn mein Feld voll
ist, das umkopiere in ein größeres Feld, sodass ich genug Platz habe.
Und umgekehrt, wenn ich ein Popback mache, wenn es zu leer wird, dann
kopiere ich es auch um, damit ich nicht so viel Verschnitt habe.
Wir konnten dann zeigen, dass eine beliebige Folge von Operationen,
von M, Pushback und Popback Operationen, Zeit O von M benötigen, war
eine ganz wichtige Analysetechnik, die man sich wie eine Art
Versicherungspolizei vorstellen kann.
Die Operationen Pushback und Popback müssen auf ein Konto zusätzliche
Tokens einzahlen, die dann abgehoben werden können, wenn diese
Reallocate -Operation tatsächlich aufgerufen wird.
Und dann konnten wir relativ leicht beweisen, dass das genügt, damit
dieses Konto niemals überzogen wird.
Allgemeiner werden wir verschiedene Anwendungen von amortisierter
Analyse kennenlernen.
Das könnte man mathematisch so darstellen.
Wir haben eine Menge von Operationen Z.
In unserem Beispiel Pushback und Popback.
Oder in der Übung hatten wir die Beispiele addieren und dekrementieren
in einer Bitfolge.
Wenn man dann einen Zähler hochzählt, konnte man auch sehen, manchmal
braucht es bei Zähler Stand N, Lock N Zeit, um die ganzen Carries zu
propagieren.
Aber amortisiert über ganz viele Inkrement-Operationen ist es nur
konstant viel.
Oder wir hatten diese Hotlist-Datenstruktur kennengelernt, in die man
dann in Zeit O von Wurzel N einfügen konnte und ab und zu musste man
aber mischen mit einer langen Folge, die O von N Zeit braucht.
Aber amortisiert war das Wurzel N Laufzeit.
Versuchen wir das mal zu verallgemeinern.
Also wir haben eine Menge von Operationen wie Pushback und Popback
oder Inkrement und Dekrement.
Inkrement und Dekrement geht nicht, da hätte man nur Inkrement.
Die Kosten hängen vom Zustand der Datenstruktur ab.
Und dann habe ich so etwas wie Funktionen, die amortisierten Kosten
einer Operation X abhängig vom Zustand S und die tatsächlichen Kosten
der Operation X abhängig vom Zustand S.
Ich habe eine Berechnung, die fängt mit dem Zustand S0 an.
Operation 1 verändert den Zustand der Berechnung in S1, Operation 2 in
S2, bis ich bei Zustand SN bin.
Und ich kann jetzt die Kosten der Operationen aufsummieren auf zwei
Seiten meines Gleichungssystems.
Einerseits die tatsächlichen Gesamtkosten, also ich summiere von I
gleich 1 bis N, die Kosten der Iden-Operation angewendet auf den I
-ersten Zustand.
Und das gleiche mache ich mit den amortisierten Kosten.
Und die amortisierten Kosten, die ich angesetzt habe, sind dann
korrekt oder zulässig, wenn die Summe der tatsächlichen Kosten kleiner
gleich der Summe der amortisierten Kosten ist.
Beziehungsweise ich erlaube dann auch so einen konstanten Offset C.
Gibt es dazu Fragen?
Warum mache ich das überhaupt, amortisierte Analyse?
Fassen wir das nochmal zusammen.
Also zunächst mal sind diese amortisierten Laufzeiten im Allgemeinen
leichter zu garantieren als tatsächliche Laufzeiten.
Den Gesamtlaufzeiten meines Algorithmus tut das keinen Abbruch.
Und wenn man das dann hat, dann kann man tatsächlich auch hergehen und
sagen, vielleicht gibt es ja auch systematische Methoden zur
Deamortisierung.
Das ist tatsächlich auch ein Thema in der Algorithmik.
Man könnte sich zum Beispiel jetzt mal überlegen, wie kann ich denn
ein unbeschränktes Feld bauen, bei dem die Pushback- und Popback
-Operationen Worst Case Zeit U von 1 haben.
Hat da jemand eine Idee?
Ich kann mal versuchen, das zu skizzieren.
Die erhöhten Kosten für Pushback und Popback treten ja dadurch auf,
gehen wir da nochmal in den Pseudocode, dass ich hier dieses
Umkopieren machen muss.
Ich könnte das ja in vorauseilendem Gehorsam machen.
Wenn ich jetzt merke, der Platz wird langsam klappen, dann fange ich
an, bei jedem Pushback drei Elemente vom momentanen Array in die Kopie
rüber zu kopieren.
Und wenn ich das richtig mache, ist es dann so, wenn ich das letzte
Pushback mache, das den komplett füllt, dann habe ich auch schon die
Kopie komplett.
Und das nächste Pushback braucht dann nur noch Umschalten auf die
Kopie.
Das nimmt jetzt an, dass ich das Allozieren von Arrays in konstanter
Zeit machen kann, nehmen wir das jetzt mal an.
Und so ähnlich kann ich das auch für das Popback machen, dass ich auch
eine kleinere Kopie sozusagen schon vorhalte und wenn das dann
tatsächlich diese Schranke unterschreitet, muss ich nur noch
Umschalten.
Aber in der Praxis ist das erheblich komplizierter, dann müssen Sie
bei jedem Pushback irgendwie noch zusätzliche Operationen machen, die
Sachen kopieren, die Sie vielleicht gar nicht brauchen, weil es dann
wieder Popbacks gibt, die das Ganze in dem Rahmen lassen, den ich habe
und ich arbeite sozusagen in vorauseilendem Gehorsam.
Also wird man das in der Praxis wahrscheinlich eher nicht machen.
Aber es gibt halt Anwendungen, wo das nützlich sein könnte.
Also überlegen wir uns mal, wann ist es das wert?
Also ich habe kompliziertere Operationen, die in der Gesamtsumme
teurer sind.
Was habe ich davon?
Na ja, zum Beispiel bei Echtzeitsystemen.
Wenn Sie jetzt, keine Ahnung, eine Steuersoftware für ein Flugzeug
haben und das muss abhängig von bestimmten Berechnungen entscheiden,
sollte ich jetzt das Steuerruder einschlagen oder nicht.
Wenn das ab und zu mal eine Stunde dauert, diese Entscheidung, dann
möchte ich nicht mit diesem Flugzeug fliegen, auch wenn das
amortisiert in einer Nanosekunde geht.
Da ist dann die Worst-Case-Ausführungszeit relevant für die Funktion
Ihrer Software und dann haben Sie keine andere Wahl.
Allerdings ist es so, dass die meisten Echtzeitsysteme sowieso wenig
mit dynamischen Datenstrukturen arbeiten, weil das ohnehin eine
kitzlige Angelegenheit ist.
Eine andere Anwendung wäre Parallelverarbeitung.
Wenn Sie jetzt tausend Prozessoren haben, jeder dieser Prozessoren
verwaltet ein unbounded Array und jeder dieser Operatorprozessoren
soll ein Pushback machen in sein lokales Array und danach müssen die
sich synchronisieren und irgendwas anderes machen, dann ist es
irgendwie blöd, wenn einer davon jetzt ganz lange braucht und alle
anderen müssen auf ihn warten.
Dann will man das auch nicht haben.
Allerdings, was man in dem Fall oft macht, ist, dass man dafür sorgt,
dass diese teuren Operationen irgendwie synchronisiert werden, dass
die dann eben alle gleichzeitig ihre Arrays wachsen lassen, dann hat
man auch kein Problem.
Trotzdem könnte es da Fälle geben, wo man halt diese Deamortisierung
dann auch einsetzen will.
Gibt es noch Fragen zur amortisierten Analyse?
Was bedeutet amortisierte Komplexität?
Da werden wir sicherlich auch noch Übungsaufgaben stellen und da kann
man auch schöne Klausuraufgaben zu bauen.
So, dann gehen wir jetzt mal zu Anwendungen von Listen und
Folgendatenstrukturen.
Ich hatte ja am Anfang gesagt, es gibt drei Bedeutungsebenen.
Einerseits mathematisch, da schreibe ich einfach so eine Liste hin und
kann damit alles machen, interessiere mich aber auch nicht dafür, was
da passiert.
Dann softwaretechnisch, welche Operationen mache ich da drauf?
Und da gibt es zum Beispiel in ganz vielen Anwendungen die Fälle, dass
man nur Pushback und Popback braucht, also am Anfang oder am Ende was
löscht.
Äquivalent dazu wäre es dann so, dass man nur am Ende was löscht oder
einfügt.
Äquivalent dazu nur am Anfang,
dann haben Sie einen sehr begrenzten Satz von Operationen und können
dafür dann spezialisierte Implementierungen machen.
Ein weiterer Fall, den man oft hat, sind so Warteschlangen.
Ich füge am Anfang ein und lösche am Ende.
Und die verallgemeinerte Version ist dann eine sogenannte Deck, was so
eine Zusammenziehung aus Double Ended Queue im Englischen ist, wo man
an beiden Seiten einfügen und löschen kann, aber eben nicht irgendwie
mittendrin.
Man kann auch nicht Random Access machen, sondern man hat wirklich nur
diese Listendatenstruktur und man macht nur an den Enden was.
Also wozu ist das gut?
Also einerseits Sie haben eine einfache Schnittstelle, die Sie schnell
lernen können.
Es gibt trotzdem viele Anwendungen, die damit auskommen.
Sie können jetzt viele Implementierungen einsetzen und das werde ich
jetzt auch als Fallstudie verwenden.
Okay, welche dieser Dinger kann ich jetzt mit den verschiedenen
Repräsentationen am besten implementieren?
Und Sie können sich dann besonders effiziente Implementierungen auch
aussuchen.
Und vielleicht auch eher eine softwaretechnische Sicht, dass ich sage,
ich weiß, meine Anwendung sollte das jetzt nur als Stapel verwenden.
Und das sage ich sozusagen gegenüber dem Compiler auch hier.
Das hier ist jetzt ein Stack.
Ich verspreche, dass ich nur Pushback und Popback mache.
Bitte verhindere, dass irgendwelche Methoden unten drunter was anderes
machen, weil das führt nur zu Fehlern.
Also ich kann Fehlerquellen ausschließen, dadurch, dass ich bereits im
Programm sage, hier, das ist genau diese Datenstruktur, ich brauche
nur das und alles andere ist von übel.
Okay, fangen wir mal mit dem Stapel an.
Also wie gesagt, es ist äquivalent, ob ich sage, ich mache Einfügen
nur am Ende oder nur am Anfang.
Deshalb lässt man dieses Back und Front auch weg, sondern sagt, es
gibt nur ein Push und ein Pop.
Die beiden Operationen.
Also zum Beispiel, wenn Sie einen Stapel haben, das kann man sich dann
auch vorstellen wie so ein Bücherstapel.
Sie können immer nur das oberste Element wegnehmen oder eins
drauflegen.
Wenn Sie einen Stapel ABCD haben, Pop sagt, entferne das A oder Push X
sagt, tut das X oben drauf.
Kennen Sie alle, denke ich.
Ja, wie implementiere ich das?
Na ja, da gibt es viele Möglichkeiten.
Frage dazu.
Ich kann natürlich die doppelt vergessene Liste nehmen, aber das ist
vielleicht ein Overkill.
Da brauche ich zwei Pointer pro Element und für die paar Operationen
brauche ich das nicht.
Es reicht zum Beispiel eine einfach verkettete Liste.
Und da muss ich dann aber aufpassen, ich kann nicht Push Back und Pop
Back implementieren bei der einfach verketteten Liste.
Deshalb muss es hier Push Front und Pop Front sein.
Also Pop fügt am Anfang ein und Pop löscht am Anfang.
Dieses Dummy Item, das ich gebraucht habe, um meine Invariante zu
vereinfachen, ist für so eine Stack-Implementierung eigentlich auch
nicht nötig.
Weil beim Push weiß ich immer, was ich tun soll.
Leerheit überprüfen kann ich auch über irgendeinen Nullzeiger oder
sowas.
Suchen tue ich in Stacks auch nicht.
Also da kann man sich das vielleicht sparen und das speichert
insbesondere Speicherplatz.
Der Code bleibt trotzdem relativ einfach.
Und diesen Endezeiger, den ich eingeführt habe, um auch einen Push
Back machen zu können, brauche ich hier halt auch nicht.
Also man kann jetzt so eine Vereinfachung, man kann sozusagen die
allgemeine Datenstruktur so ein bisschen zurückkochen, wenn ich nur
einen Stack implementieren will.
Andererseits, ich könnte auch ein Unbounded Array verwenden.
Da würde ich dann Push Back und Pop Back verwenden.
Der Vorteil gegenüber einer verketteten Liste ist, dass das Ganze
cache -effizient ist.
Das bleibt alles in einem Speicher liegen.
Und wenn ich viele Push Backs hintereinander habe, viele Pops, habe
ich sehr hohe Lokalität.
Das kann dann eine Größenordnung oder mehr schneller sein als mit
verketteten Listen.
Nachteil ist halt, dass ich keine Worst-Case-konstante Laufzeit habe,
sondern nur amortisiert konstant.
Dass man das eben nicht in allen Fällen einsetzen will.
Könnte jetzt den Eindruck haben, naja gut, das wird es jetzt sein,
aber wir werden in der Vorlesung Algorithm Engineering vielleicht auch
in den Übungen tatsächlich uns nochmal angucken, dass man auch einen
Kompromiss aus den beiden Sachen kriegen kann.
Worst-Case-Constant-Time und so cache-effizient wie die Unbounded
Arrays ist auch gar nicht so kompliziert.
Aber hier soll mir das jetzt erstmal reichen.
Fragen zu Implementierungsvarianten von Stapeln.
Anwendungen von Stapeln, zum Beispiel als Rekursionsstapel, kennen Sie
das innerhalb der Programmiersprache.
Manchmal will man das bei den Algorithmen auch sozusagen von Hand
machen.
Man legt sozusagen das, was noch zu tun ist, auf dem Stapel ab und hat
dann eben ein iteratives Programm, das mit diesem Stapel arbeitet.
Das kann manchmal effizienter sein, wenn der Overhead für einen
rekursiven Funktionsaufruf irgendwie höher ist als für eine sehr
spezialisiert kodierte Aufgabenkodierung auf dem Stapel.
Parser, Klammerstrukturen abarbeiten, das sind alles Sachen, wo man
Stapel braucht.
Da werden Sie auch in Grundlagen der theoretischen Informatik noch
passende Maschinenmodelle dazu kennengelernt, sogenannte
Kellermaschinen, die dann wiederum die Basis bilden für die
Syntaxanalyse im Compilerbau.
Naja, und da Stapel so einfach ist, benutzen wir die auch manchmal,
wenn man Daten nur irgendwie ablegen will und später wiederholen.
So, was ist die nächst kompliziertere Datenstruktur?
Warteschlangen, auch genannt First-In-First-Out-Warteschlange oder
FIFO kurz.
Ich habe die Operationen Enqueue, Deck, Dequeue und das bedeutet dann
je nachdem, wie ich es interpretiere, entweder das Enqueue ist ein
Push -Front und dann ist das Dequeue ein Pop-Back oder umgekehrt, das
Enqueue ist ein Push-Back und dann ist das Dequeue ein Pop-Front.
Hier wäre jetzt ein Beispiel, wenn ich eine Warteschlange ABC habe, X
einfüge, dann wird das halt am Anfang eingefügt, First-In, und ein
Dequeue wird mir das letzte Element, hier das C, zurückliefern, First
-In -First-Out.
Fragen zu FIFO.
Implementierung, das wird jetzt ein bisschen interessanter,
natürlich kann ich wieder eine doppelt verkettete Liste verwenden, ist
wieder ein Overkill.
Ich kann auch Singly-Link-Lists verwenden, dann brauche ich aber
tatsächlich diesen Endezeiger.
Und dann muss es so sein, dass das Enqueue ist ein Push-Back und das
Dequeue ein Pop-Front, weil andersrum würde nicht funktionieren, weil
das Pop-Back kriege ich bei einer einfach verketteten Liste nicht
implementiert.
Dummy -Item brauche ich auch nicht.
So, jetzt wird es spannend.
Wie kriege ich das mit einem Array oder einem Unbounded Array hin?
Erstmal so einfach gar nicht, weil das Unbounded Array erlaubt ja nur
die Stapel-Operationen, Push-Back und Pop-Back.
Wenn ich das naiv machen würde, müsste ich für das Push-Front dann das
ganze Array um eine Position verschieben, das ist viel zu teuer.
Aber jetzt werden wir eine weitere Datenstruktur kennenlernen, was ich
mal ein zyklisches Array nennen möchte.
Ich werde das für den Fall eines beschränkten zyklischen Arrays
vorstellen und es ist dann eine Übungsgabe, wie Sie das anbauen und
machen können.
Das ergibt dann auch eine beschränkte Pfeife, die also eine bestimmte
Größe nicht überschreiten darf.
Auch hier lernen wir dann in der Vorlesung Algorithm Engineering noch
verbesserte Datenstrukturen.
Also was ist ein zyklisches Array?
Am besten kann man das an diesem Bild hier verstehen.
Sie können sich also wirklich vorstellen, Sie haben ein Array und
wiegen das zu einem Kreis zusammen.
Jetzt muss man sich halt überlegen, was das mathematisch bedeutet.
Ich fange jetzt an bei 0 zu nummerieren, dann ist die Mathematik ein
bisschen einfacher.
Also Sie haben Arraypositionen 0, 1, 2, 3 und so weiter bis n.
Das sind wohlgemerkt n plus 1 Elemente, so wie ich das hier
implementiert habe.
Ich darf aber höchstens n davon benutzen.
So und warum jetzt zyklisch?
Naja, der Trick ist der folgende.
Ich sage, das ist sozusagen meine Datenstruktur invariante.
Ich speichere Positionen h und t, Head and Tail, die den Anfang und
das Ende meiner Pfeife repräsentieren.
Und in diesem zyklischen Array liegen die Elemente der Pfeife
konsekutiv hintereinander.
Das ist die Idee.
Und der Trick ist jetzt halt, es darf durchaus sein, dass Head plus
Anzahl Elemente größer ist als n.
Wenn ich bei n angekommen bin, mache ich einfach bei 0 wieder weiter.
Solange ich nie mehr als n Elemente in diesem zyklischen Array
speichere, ist immer klar, wo meine gespeicherten Elemente sind und wo
jetzt undefinierte Elemente sind.
Also insbesondere wenn Sie jetzt hier diese Situation haben, das Rote
sind die Elemente in der Pfeife.
Wenn Sie immer abwechselnd eins einfügen, dann wird es hier eingefügt
und eins löschen.
Dann wird es da gelöscht.
Dann wandert dieser rote Bereich um diesen zyklischen Array drumherum.
Und das geht alles in konstanter Zeit.
Und wie, das zeigt uns dieser Pseudocode.
Da muss man halt ein paar Mathe-Tricks sich überlegen, wie man jetzt
dieses runde Bild auf einem dummen Rechner abbildet, der nichts von
Geometrie versteht.
Das ist eine Analogie, die man aber sehr einfach auf dem Rechner
abbilden kann.
Also wir haben hier wieder eine Klasse, Bounded Pfeife.
Die hat ein Konstruktorparameter n, das ist die maximale Anzahl
Elemente, die ich jemals abspeichern will in dieser Pfeife.
Wie gesagt, die unbounded Variante ist eine Übungsaufgabe.
Es gibt ein Member b, das ist ein Array mit n plus 1 Einträgen, 0 bis
n.
Und es gibt zwei Positionen, head und tail, die am Anfang 0 sind.
Und die Datenstruktur-Invariante sagt, h ist das erste gültige
Element, also b-Index-h ist das erste gültige Element.
Und b-Index-t ist das erste ungültige oder der erste freie Platz.
Und dann ist es halt so, wenn h gleich t ist, signalisiert das das
leere zyklische Array.
Oder die leere Pfeife.
Und das ist auch schon meine Funktion isEmpty, die war genau dann
zurückgibt, wenn h gleich t ist.
Dann ist auch ganz einfach das erste Element zurückgeben, das ist
einfach b-h.
Das macht nur Sinn, wenn Ding nicht leer ist, das ist eine
Vorbedingung.
So, size muss ich mir jetzt überlegen, das erste Mal, wie man da
rechnet.
Wenn h und t beide größer 0 sind, also wenn ich hier keinen Wraparound
habe, dann ist t größer h und t minus h ist gerade meine Größe.
Das sieht man hier, t minus h.
Aber in dem Fall, da wäre jetzt, glaube ich, t wäre 0, 1, 2, 3 und h
ist irgendwas viel Größeres.
Also 3 minus irgendwas Großes ist eine negative Zahl, das ist kein
sinnvolles Ergebnis.
Aber man kann sich überlegen, wenn ich jetzt einfach Modulo n plus 1
rechne, das ist die Größe dieses Kreises, kriege ich trotzdem wieder
das richtige Ergebnis.
Ich habe hier jetzt zusätzlich n plus 1 addiert, weil es in einigen
Programmiersprachen gar nicht genau definiert ist, was Modulorechnung
von negativen Zahlen bedeutet.
Aber indem ich hier immer n plus 1 addiere, ist das hier immer eine
positive Zahl, deren Wert Modulo n plus 1 immer genau die Größe ist.
Im Endeffekt könnten Sie hier auch eine einfache Fallunterscheidung
machen.
Wenn t größer h, dann return t minus h, else return t minus h plus n
plus 1.
Und dann können Sie sich überlegen, dass das immer die Größe ist.
Beweis wäre vielleicht auch eine schöne Übungsaufgabe.
Pushback?
Naja, ich habe ja gesagt, bt ist das erste freie Element.
Da wird einfach das x eingefügt, mein neues Element, und ich
inkrementiere t, aber damit das immer ein gültiger Arrayindex ist,
mache ich das Modulo n plus 1.
Und es gibt hier die Vorbedingung, dass die Größe kleiner n sein muss,
danach ist sie dann bis zu n.
Kann mir jemand sagen, was passieren würde, wenn ich in dieses Array,
das ja durchaus n plus 1 Plätze hat, auch wirklich n plus 1 Elemente
einfügen würde, was würde dann schiefgehen?
Ja, genau.
Also ich gebe es akustisch nochmal wieder, dann ist hat gleich t, dann
wäre ist empty gleich wahr.
Oder in anderen Worten, ich kann in dem Fall nicht unterscheiden
zwischen einem leeren und einem vollen Array.
Da könnte man sich auch mal überlegen, wie man damit umgeht, wie man
dieses überflüssige Speicherelement irgendwie loswerden könnte.
Ist mir aber nichts wirklich Elegantes zu eingefallen, deshalb habe
ich es so gemacht.
Gibt es noch Fragen zu dem zyklischen Array oder der Implementierung
von FIFOs mittels eines zyklischen Arrays?
Anwendung von Warteschlangen, ganz typisch sind Datenpuffer.
Das könnten zum Beispiel Datenpuffer in irgendwelchen Netzwerkswitches
sein oder wenn Sie in Unix eine Pipeline haben, also zwei Prozesse,
die Standardausgabe des ersten Prozesses ist die Standardeingabe des
zweiten Prozesses, dann implementieren Sie das so, dass Sie einen
kleinen Datenpuffer dazwischen haben, wo die Datenelemente dann FIFO
-mäßig in den Puffer reingeschrieben werden von dem ersten Prozess und
herausgelesen vom zweiten Prozess.
Innerhalb des Betriebssystems sind Job-Queues sehr oft FIFOs, einfach
um sicherzustellen, dass Sie eine faire Bearbeitung der Aufgaben
haben.
Oder wir werden innerhalb der Vorlesungen Algorithmus zur Breitensuche
in Graphen kennenlernen, den man auch mit Hilfe einer FIFO-Queue
implementieren kann.
Gibt es noch Fragen zu den Anwendungen?
Ja, dann schließe ich die Double-Ended-Queues, die könnte man jetzt
mit einer Doubly-Linked-List implementieren, eine Singly-Linked-List
reicht hier definitiv nicht mehr.
Allerdings, wie gesagt, die drei Operationen, Push-Front, Pop-Front
und Push-Back sind möglich, aber die vierte fehlt uns leider.
Array und Unbounded-Array gehen auch nicht, aber ich kann wieder ein
zyklisches Array verwenden.
Das wäre auch eine schöne Übungsaufgabe, sozusagen, wie können Sie
daraus jetzt eine DAG machen.
Dann müssen Sie halt zusätzliche Operationen Push-Front und Pop-Back
machen, die aber auch ganz einfach sind.
Völlig analog zu den beiden Push-Back und Pop-Front.
Anwendungen von DAGs.
In meiner Erfahrung relativ selten, also Stapel- und Pfeifos braucht
man sehr oft.
DAGs habe ich noch nicht so oft gesehen.
Oft sind es dann auch etwas spezialisierte Formen davon.
Zum Beispiel bei der Lastbalancierung mittels Work-Stealing in
Multichore -Rechnern hat man manchmal etwas spezialisierte DAGs, wo
dann sogar parallele Zugriffe bis zu einem gewissen Grad erlaubt sind.
Und manchmal hat man in Programmen wie zum Beispiel einem Texteditor
Operationen Puffer, in denen halt unten steht, was sind die letzten
Operationen, die Sie durchgeführt haben.
Und da kann man dann so die Operationen Undo und Redo machen und die
müssen dann in so einer allgemeineren DAG-Form auf diesen Puffer
zugreifen.
So, damit sind wir erstmal durch, durch die Algorithmen, die wir hier
vorstellen.
Und jetzt haben wir eine ganze Reihe Varianten kennengelernt und es
macht Sinn mal zu vergleichen, wann verwende ich was.
Also ich hatte ganz am Anfang schon gesagt, so ein Kipu kann man super
über die Andenpässe schleppen, während so eine Keilschrift-Tablet sich
schön lange hält und vielleicht übersichtlicher ist.
Übersetzen wir das mal auf Datenstrukturen.
Also Listen sind flexibel.
Ich habe Operationen wie Remove oder Splice, mit denen ich sehr viel
machen kann.
Und im Gegensatz zu Erase habe ich keinen Verschnitt.
Also ich kann hier auch bei dem Kipu immer noch neue Seitenfäden
dranknoten und wirklich nur das verwenden, was ich wirklich brauche.
Felder erlauben mir dafür einen beliebigen Zugriff.
Sie sind irgendwie einfacher als einfach ein Stück Speicher.
Und ich habe keinen Overhead für Zeiger.
Und was in der Praxis oft noch wichtiger ist, wenn ich jetzt durch so
eine Folge einmal nur komplett durchlaufen will, um alle Elemente zu
verarbeiten in der gegebenen Reihenfolge, ist das oft viel effizienter
als mit verketteten Listen wegen Cache-Effekten.
Jetzt gucken wir uns nochmal die Tabelle an, die ich ganz am Anfang
hatte.
Also wir haben hier Spalten, Doppeltverkettete Liste,
Einfachverkettete Liste, Unbounded Array und Cyclic Array.
Und jetzt gucken wir uns mal die einzelnen Operationen an.
Da gibt es natürlich die Paradedisziplin von Arrays.
Gebt mir das Ite-Element oder diese Klammer-Operation.
Wir können die in konstanter Zeit.
Das ist bei einer Liste leider so, dass Sie sich da entsprechend vom
Anfang hininhangeln müssen, sodass Sie da dann Linearzeit brauchen.
Größe berechnen geht bei den Arrays problemlos in konstanter Zeit.
Bei Listen hatten wir es in unserer Implementierung nicht vorgesehen.
Man kann es da zubauen, aber dann kann man die Splice-Operation nicht
mehr in konstanter Zeit machen.
Muss sich also überlegen, was man da will.
Erstes, letztes Element zugreifen können die alle.
Einfügen, also allgemeines Einfügen ist bei Arrays teuer.
Beim Singly Linked Lists kann ich zwar in konstanter Zeit einfügen,
aber mit einem merkwürdigen Interface.
Ich kann nämlich nur ein Insert After machen, aber nicht Insert
Before.
Was noch schlimmer ist, ich kann nur ein Remove After machen, was
irgendwie überhaupt nicht das ist, was man in der Praxis braucht,
meistens.
Da haben also die Doubly Linked Lists echte Vorteile.
Also man kann jetzt immer auch spaltenweise Vergleiche machen.
List, Singly Linked List, da sieht man, die sind sehr ähnlich, außer
dass hier dieser komische Stern steht, dass die Interfaces komisch
sind.
Und das Popback ist teuer.
Alles andere ist hier kaum unterscheidbar.
Und dann kann ich natürlich Listen und Arrays vergleichen.
Man muss das jetzt nicht alles im Detail machen, aber ich gehe jetzt
vielleicht trotzdem nochmal zeilenweise durch.
Dann gibt es hier diesen Block Pushback, Pushfront, Popback, Popfront.
Da geht halt, wie gesagt, bei den Listen alles ganz gut, außer das
Popback bei den einfachverketteten.
Beim Unbounded Array kann ich Pushback und Popback effizient.
Allerdings hier bedeutet das Stern nur amortisiert.
Und bei den Cyclic Arrays gehen die alle in konstanter Zeit.
Allerdings auch nur amortisiert, wenn ich das Unbounded noch dabei
haben will.
Gut, Konkatenieren kann ich mit verketteten Listen in konstanter Zeit.
Genauso Splice.
Und das Find Next braucht bei allen lineare Zeit, aber die konstanten
Faktoren bei den Arrays werden viel besser sein.
Gibt es dazu Fragen?
Also das ist auch eine populäre Klausuraufgabe.
Nennen Sie zwei Vorteile von Datenstruktur X gegenüber Datenstruktur
Y.
Und dann muss man sich aus dieser Tabelle da welche Sachen rauspicken.
Und natürlich erwarte ich nicht, dass Sie die auswendig lernen,
sondern was ich hoffe ist, dass Sie die Ideen dahinter verstehen.
Ja, wir haben ein paar Messungen dazu gemacht.
Das ist jetzt auch schon wieder ein gutes Beispiel für schlechtes
Algorithm Engineering.
Das hat ein Doktorand von mir gemacht, der inzwischen nicht mehr da
ist und ich habe die Codes nicht mehr und wir haben das auch nicht
sehr gut dokumentiert.
Deshalb kann ich Ihnen im Moment nicht sagen, was für Objekte wir da
einfügen und löschen und sowas.
Jedenfalls haben wir verglichen, einerseits Listen und Arrays und
andererseits mal C++ und Java.
Und da kommen schon ein paar ganz interessante und zum Teil auch
überraschende Sachen dabei raus.
Hier ist jetzt so ein Ding, ich iteriere einmal über alle Elemente
meiner Folge durch und addiere die auf oder sowas, wenn da Zahlen drin
stehen.
Und dann haben wir zwei verschiedene Fälle nochmal, nämlich
einerseits, also gerade bei den Listen, einerseits so, dass die List
-Items in der Reihenfolge im Speicher stehen, wie auch die
Verkettungen sind und andererseits, dass die irgendwie zufällig
durcheinander gewürfelt sind.
Und da sieht man dann nochmal massive Leistungsunterschiede.
Da gehen wir mal durch von unten nach oben.
Also das Schnellste sind, das ist nicht so überraschend hier, das
Blaue.
C++ Felder, da brauche ich sowas wie zwei Nanosekunden pro Element.
Das geht ein bisschen rauf bei großen Listen, weil das nicht mehr in
den Cache passt.
Das Nächste sind sehr nah beieinander zwei Sachen, die gar nicht viel
miteinander zu tun haben, nämlich Felder in Java und geordnete Listen
in C++.
Das ist also jetzt reiner Zufall, dass die die gleiche Laufzeit haben,
die aber schon erheblich höher liegt.
Das Nächste ist dann dieses türkise geordnete Listen in Java, dann
kommen randomisierte Listen in Java und dann erst die randomisierten
Listen in C++.
Also das war jetzt die große Überraschung.
Es ist zu erwarten, dass C++ eigentlich ein bisschen schneller ist als
Java.
Und bei den Arrays war das auch so, bei den randomisierten Listen aber
eben nicht.
Da war dann unsere Spekulation, dass das Memory Management von Java
einen Teil dieser Randomisierung wieder rückgängig macht.
Zum Beispiel, weil es während einer Garbage Collection dafür sorgt,
dass aufeinanderfolgende Listen-Elemente doch wieder konsekutiv
abgespeichert werden.
Das ist durchaus möglich.
Also bei den randomisierten Listen war Java schneller, bei den
geordneten Listen war nämlich C++ schneller.
Also manchmal muss man ziemlich vorsichtig sein mit Vorhersagen.
Java kann auch mal schneller sein, aber im Allgemeinen würde ich dann
sagen, wenn Sie einen effizienten Algorithmus haben wollen und durch
die Daten nur durchiterieren wollen, dann nehmen Sie sowieso Arrays
und da ist hier eigentlich Java erstaunlich viel langsamer.
Eine mögliche Erklärung, warum hier jetzt zufällig das hier genauso
langsam ist, wie die geordneten Listen bei C++ wäre, dass wir hier
tatsächlich einen Datentyp genommen haben, der nicht elementar ist und
dann erzeugt Java ohnehin zusätzliche Indirektionen.
Deren Kosten halt massiv ins Kontor schlagen und eigentlich
vergleichbar sind mit den Dereferenzier-Operationen, die man braucht,
um eine verkettete Liste zu verfolgen.
Also was super simples wie eine Folge, wenn man wirklich reale
performanceig anguckt, muss man wieder tausend Sachen angucken.
Wie liegen die im Speicher?
Was macht die Speicherverwaltung?
Sind das elementare Datentypen, gerade in Java, oder eben welche, die
wieder über eine Referenz abgespeichert sind?
Und das ist vielleicht auch nochmal ein Grund, warum wir lieber
Analyse machen in unseren abstrakten Maschinenmodellen und dann muss
man die Messungen nochmal separat machen.
Fragen dazu?
Jetzt haben wir mal Einfügungen zufälliger Positionen gemacht.
Da sieht man halt, dass je länger die Liste wird, desto weiter geht
die Schere auseinander.
Das ist wohlgemerkt eine logarithmische Skala zwischen den Zeiten für
Listen und Felder.
Also das Rote und das Grüne sind die C++-Zeiten.
Und da hat man hier bei großen Listen 0,2 Mikrosekunden für die Liste
und 80 Mikrosekunden für das Array, also mehrere Größenordnungen
dazwischen.
Und hier sind die Unterschiede zwischen C++ und Java nicht so
ausgeprägt.
Aber auch da ist es jetzt wieder so, wir haben mal vermutet, dass Java
eine effizientere Speicherverwaltung hat, aber die Listenzeiten sind
jetzt tatsächlich so, dass die Java-Implementierung für Einfügen
langsamer ist als die bei C++.
Also in dem Fall war da die Speicherverwaltung von Java langsamer.
Fragen dazu?
Aber das hier ist jetzt etwas, was natürlich bestätigt unsere
asymptotische Analyse.
Lineare Laufzeit wird hier halt sichtbar und macht riesige
Unterschiede am Ende gegenüber der konstanten Laufzeit.
Was wir sehen ist, dass die konstante Laufzeit keine Konstante ist,
weil hier natürlich Cache-Effekte und sowas eine Rolle spielen.
So, Ausblick.
Wir werden noch eine ganze Reihe weiterer Repräsentationen von Folgen
sehen in den folgenden Kapiteln mit anderen Interfaces.
Wir werden uns jetzt zunächst mal Hashtabellen angucken, wo ich
schnelles Einfügen, Löschen und Suchen habe, aber andere Operationen
zum Teil gar nicht unterstützt werden.
Prioritätslisten, da kann ich schnell einfügen oder das Minimum
entfernen und dann Suchbäume, die sozusagen sortierte Folgen
repräsentieren, da kann ich einfügen, löschen, suchen, aber auch
Bereichsanfragen machen, also gebe mir alle Elemente, deren Schlüssel
in einem bestimmten Bereich liegen.
Das ist zum Beispiel etwas, was ich mit den Hashtabellen nicht könnte.
Gut, damit kommen wir zum nächsten Kapitel.
Gibt es insgesamt noch Fragen zur Repräsentation von Folgen?
Das war in gewisser Weise so ein einfacher Warm-up, also die
Algorithmen sind noch sehr einfach, die Mathematik dahinter eigentlich
auch, auch wenn die amortisierte Analyse vom Konzept her ein bisschen
abstrakt ist.
Und wir werden uns natürlich jetzt langsam etwas kompliziertere
Algorithmen anschauen.
Interessanterweise, ich habe letztens Kurse anerkennen müssen von
einer Universität in Irland, da gab es dann einen ganzen
Algorithmenkurs nur über lineare Datenstrukturen.
Und da habe ich dann im Syllabus nicht viel mehr finden können, als
wir hier in einem Kapitel machen.
Ich hoffe, ich überfordere Sie nicht, aber ich glaube, mein Eindruck
ist, das können wirklich am Ende die meisten.
Gut.
Hash-Tabellen.
Ja, was bedeutet das überhaupt?
Das ist ein merkwürdiger Begriff.
To hash, da gibt es verschiedene Übersetzungen.
Man könnte es als völlig durcheinander bringen übersetzen.
Das passt, glaube ich, am besten zu den Tabellen.
Hash-Meat im Englischen ist das, was passiert, wenn man Stücke von
Fleisch nimmt und in einen Fleischwolf steckt und durchdreht.
Das ist insofern verwandt mit dem, was wir hier machen, dass wir also
unsere Datenstruktur irgendwie atomisieren, alles durcheinander mixen.
Allerdings werden wir in den Algorithmen keine Transportwändeln und
keine Durchdruckplatten und sowas finden.
Deshalb ist das vielleicht eher eine Spielerei.
Was man auch manchmal findet, ist so Schredderanlagen.
Wenn man Papier zerschreddert, damit man Sachen nicht wiederfindet.
Wir werden aber etwas anderes machen.
Paradoxerweise hilft dieses völlig durcheinander bringen dabei, Sachen
wiederzufinden.
Und ich werde versuchen zu erklären, warum das so ist.
Fangen wir erstmal mit unserer mathematischen Sichtweise an und der
Software -Engineering-Sichtweise.
Mathematisch speichern wir eine Menge von Elementen.
Jedes Element hat einen Schlüssel und die Funktion key von einem
Element e liefert uns diesen Schlüssel.
Und ich möchte die sogenannten Wörterbuch-Operationen unterstützen und
zwar in konstanter Zeit.
Diese Wörterbuch-Operationen sind Einfügen eines Elements, Löschen,
naja nicht eines Elements, weil das kenne ich vielleicht nicht, aber
gegeben ein Schlüssel, sage ich, bitte entferne das Element mit diesem
Schlüssel.
Find, gegeben ein Schlüssel, liefere mir das Element mit diesem
Schlüssel zurück.
Da können noch assoziierte Informationen dranhängen, insofern kann das
sehr wichtig sein.
Es gibt noch ein anderes Interface für Hashtabellen, das nennt man
dann auch assoziatives Array oder Map oder partielle Funktion.
Wir wollen die Schlüssel abbilden auf die Elemente und schreiben das
dann so wie, ja M ist jetzt unsere Hashtabelle und es gibt diese
eckige Klammer-Operationen, so wie bei einem Array.
Und das ist so was wie, führe die Finder-Operation für Schlüssel K
aus.
Das Schöne dabei ist jetzt, wenn ich das als Array hier schreibe,
niemand beschränkt mich darauf, dass die Schlüssel irgendwie
konsekutive, ganzzahlige Integers sein müssen.
Das kann irgendwas sein, das können Strings sein, das kann die
Stellung eines Schachbretts sein, in einem Schachprogramm, beliebig
komplizierte, auch sehr große Schlüsselmengen sind hier erlaubt.
Aber ich brauche Platz, trotzdem nur proportional zur Anzahl der
tatsächlich von dieser partiellen Funktion unterstützten Schlüssel.
Oder proportional zur Größe der Menge M.
Gibt es Fragen zu dem Interface für Hashtabellen?
Wer hat Hashtabellen schon mal irgendwo kennengelernt beim
Programmieren?
Sogar innerhalb der Vorlesung programmieren vielleicht?
Nee, eher so selber.
Aber das ist, wie gesagt, eine der wichtigsten Datenstrukturen, die
man immer wieder braucht und was Sie hier lernen ist, wie man die
implementiert und wie man beweist, dass sie effizient sind.
Okay, ich muss jetzt die Gelegenheit nutzen, mal so ein paar
Konventionen für Elemente darzustellen.
Weil wir haben das immer wieder, wir speichern Mengen von Elementen
und die haben Schlüssel.
Man nennt im Englischen auch diese Datenstrukturen Collection Classes.
Die spielen gerade auch in den Standardbibliotheken der
Programmiersprachen wie C++ Standard Template Library und Java UTL
heißt die, glaube ich, eine große Rolle.
Also, unsere Mengenelemente haben Schlüssel.
Die Funktion, die den Schlüssel liefert, ist Markie von E.
Und wir werden sehr oft Elementvergleiche machen auf kleiner, größer,
gleich, ungleich, kleiner, gleich, größer, gleich.
Und wir werden dann manchmal Elemente auch direkt vergleichen und das
ist sozusagen nur eine Abkürzung für Vergleich der Schlüssel der
Elemente.
So, Anwendungen von Hashing.
Im Buch habe ich immer versucht, ein Kapitel einzuführen durch eine
Anwendung, die erstmal nichts mit Computern zu tun hat, die man auch
mit Papier und Bleistift sinnvoll durchführen kann.
Und da gibt es tatsächlich eine und zwar hier nebenan.
In der Universitätsbibliothek hier ist es, wenn ich mich recht
entsinne, so, wenn Sie ein Buch aus dem Magazin ausleihen, dann
bestellen Sie das halt durchaus mit einem Rechner, aber da wäre es
theoretisch auch denkbar, dass Sie da einem Bibliothekar einen Zettel
mit der Bestellung geben.
Und dann liegt das halt irgendwann später in einem Auslieferungsregal.
Und dann muss man überlegen, welches Auslieferungsregal ist das und
das ist so etwas wie die letzten Ziffern Ihres Bibliotheksausweises
geben dann die Nummer des Regalfachs an.
Und das ist irgendwie eine ziemlich gute Idee.
Und das ist auch ein Beispiel für eine Hash-Funktion.
Man will jetzt die Menge der Benutzer der Bibliothek abbilden auf
einen Regalfach.
Das sind zigtausende von Benutzern und hunderte von Regalfächern.
Da muss ich jetzt irgendwie eine Abbildung finden, die nicht dazu
führt, dass plötzlich alle ausgelieferten Bücher im gleichen Regalfach
liegen und die aber trotzdem einfach zu berechnen ist.
Und da ist das irgendwie ganz gut, die letzten Ziffern des
Bibliotheksausweises zu nehmen.
Hat jemand eine Idee, warum es eine schlechte Idee wäre, die ersten
Ziffern des Bibliotheksausweises zu nehmen?
Genau, also die werden so viel ich weiß konsekutiv vergeben.
Das heißt innerhalb eines Jahrgangs haben dann alle die gleiche
Nummer.
Das heißt, wenn dann irgendeine Massenvorlesung wie Algorithmen 1
plötzlich in die Bibliothek strömt, dann bestellen plötzlich tausend
Leute Bücher.
Während die Jahrgänge von vor zehn Jahren, die sind vielleicht nicht
mehr so oft in der Bibliothek, sodass man dadurch erheblich mehr
Kollisionen kriegen würde von Leuten, die das gleiche Regalfach
brauchen.
Ja, dann kann man sich verschiedenste Anwendungen überlegen.
Das ist auch eine sehr beliebte Aufgabe für die Klausur.
Hier ist eine einfache Programmieraufgabe, lösen Sie das in Linearzeit
oder in erwarteter linearer Zeit, werden wir dann sagen.
Das ist dann schon ein Hinweis, da muss ich irgendwie Hashtabellen
benutzen.
Oder sortieren, unter bestimmten Umständen geht das auch in
Linearzeit, aber nicht immer.
Also das ist eine der Standardwerkzeuge, mit denen Sie einfache Sachen
hinkriegen und ich nenne einfach mal Beispiele.
Angenommen, Sie haben jetzt eine Menge von Objekten und Sie wollen
sozusagen die Duplikate entfernen, dann geht das am besten mit
Hashtabellen.
Da habe ich jetzt sogar eine Masterarbeit darüber gehabt, wie man das
auf dem Parallelrechner mit wenig Kommunikation macht.
Da treten dann ziemlich spannende Effekte auf.
Schach oder andere kombinatorische Suchprogramme.
Wir merken uns, welche Stellungen unser Suchprogramm schon untersucht
hat und was die Stellungsbewertung war, um Sachen nicht mehrfach
machen zu müssen.
Die Symboltabelle bei Compilern.
Also ich möchte eigentlich nicht, wenn ich einen Compiler habe, jedes
Mal, wenn ein Bezeichner im Programm auftritt, durch irgendeine lange
Liste von Abbildungen von Bezeichnern auf Speicherstelle suchen.
Das mache ich über eine Hashtabelle und das geht viel schneller.
Assoziative Felder sind für Skriptsprachen wie Perl oder AWK zum Teil
die einzige Datenstruktur.
Man kann damit aber sehr viel machen und das ist sehr high level.
Und mit Hilfe von Hashfunktionen ist es trotzdem schnell oder von
Hashtabellen.
Datenbanken.
Eine der wichtigsten Operationen ist der Gleichheitsjoin.
Wer von Ihnen weiß, was das ist?
Einige, aber die wenigsten.
Das kommt glaube ich auch erst im fünften oder vierten Semester.
Aber ich versuche es mal grob zu erklären.
Sie haben bei relationalen Datenbanken oft mehrere Tabellen.
Und manchmal wollen Sie zwei Tabellen nehmen und bezüglich zweier
gegebener Spalten sagen, ich möchte die zusammenpassende Zeilen der
beiden Tabellen haben, die nämlich insofern zusammenpassen, als die
spezifizierten Spalten die gleichen Werte haben.
Das ist eine der Basisoperationen von relationalen Datenbanken.
Und was man dann macht, ist, dass man die kleinere Tabelle in einer
Hashtabelle speichert, mit Schlüssel die spezifizierte Spalte und dann
scannt man einfach durch die größere Tabelle einmal durch und guckt
sich dann an, okay, diese Spalte, ist die in der Hashtabelle schon
drin?
Und wenn ja, liefere ich alle Ergebnisse zurück, die da passen.
Das mache ich für jedes Element und schon habe ich meinen Join
berechnet.
Das geht davon aus, dass die kleinere Tabelle zumindest in den
Speicher passt, aber das ist in den meisten Fällen gegeben und deshalb
ist das sozusagen die Methode der Wahl für Gleichheitsjoins.
Oder in meiner Arbeitsgruppe entwickeln wir Routenplaner.
Und da brauchen wir eine Datenstruktur, die die bereits besuchten
Knoten speichert.
Und das sind, weil wir sehr effiziente Algorithmen haben, nicht alle
Knoten, sondern nur eine kleine Teilmenge.
Und da lohnt es sich, die in einer Hashtabelle zu speichern.
Das ist sozusagen der Suchraum unserer Routenplanungsalgorithmen.
Speichern wir in Hashtabellen zum Teil.
Und vieles, vieles mehr.
Also Hashtabellen sind vielleicht eine der zwei oder drei wichtigsten
Datenstrukturen überhaupt.
Fragen zu Hashing noch?
Anwendungen von Hashing?
Dann werden wir uns jetzt die Grundidee erstmal anschauen und dann
eine Implementierung Hashing mit verketteten Listen.
Kriegen Sie auch gleich mal ein Beispiel für verkettete Listen.
Und dann in der nächsten Vorlesung schauen wir uns die Analyse an.
Und dann vermutlich in der übernächsten Vorlesung, oder wir fangen
auch in der nächsten schon damit an, Hashing mit Arrays.
Jetzt machen wir mal einen idealisierten Ansatz.
Also schön wäre es, wenn wir eine Funktion hätten, nennen wir eine
Hash -Funktion H, die die Elemente der Menge M, die wir speichern
wollen, das ist jetzt M, injektiv abbildet auf eine Tabelle T mit M
-Einträgen.
Und das wird uns jetzt immer wieder begegnen.
Das ist jetzt eine idealisierte Hashtabelle, die werden wir noch
verfeinern müssen, aber die Bezeichnungen werden Sie immer wieder
sehen, deshalb sollten Sie sich die vielleicht auch merken.
Also es gibt eine Hash-Funktion H, es gibt eine Tabelle T und es gibt
M -Einträge.
Klein-M-Einträge.
Und irgendwie sollte das Klein-M was mit der Größe von dem Groß-M zu
tun haben.
Dann würde es zum Beispiel ganz gerne linear damit skalieren.
Und idealerweise hätte ich gerne, dass eine gute Femie eine Hash
-Funktion verrät mit der Eigenschaft, dass die injektiv ist auf M.
Dann könnte ich nämlich einfach hergehen und ein Element E an der
Stelle H von Ki von E speichern in der Tabelle.
Also T von H von Ki von E ist einfach E.
Das heißt insbesondere, wenn ich dann ein Insert mache, würde ich
einfach sagen, T von H von Ki von E Doppelpunkt gleich E.
Wenn ich ein Find mache, sage ich, okay, Return T von H von K, wenn
ich den Schlüssel K gegeben habe.
Das wäre super einfach, alles wäre ein Einzeiler, wenn mir denn jemand
diese injektive Hash-Funktion geben würde, aber das ist leider nicht
so einfach.
Im Allgemeinen, wenn ich hergehe und zum Beispiel eine zufällige
Funktion nehme, dann kann es vorkommen, dass zwei Schlüssel auf den
gleichen Hash-Wert abgebildet werden.
Dann könnte man sagen, naja, dann probiere ich es halt so lange, bis
es gut geht.
Oder vielleicht hilft es ja, die Tabelle ein bisschen größer zu
machen.
Es ist klar, wenn die Tabelle nur genau M-Betrag-Einträge hat, dann
muss ich super viel Glück haben, damit die alle auf verschiedene
gemappt werden.
Aber reichen dann zweimal M-Betrag, dreimal M-Betrag-Tabellen, dass
ich eine gute Chance habe, bei Wahl einer zufälligen Hash-Funktion
eine Injektive zu finden?
Spannenderweise gibt es da ein Ergebnis aus der
Unterhaltungsmathematik, das uns da einen Hinweis gibt.
Wer kennt das Geburtstagsparadox?
So die Hälfte.
So eine beliebte Party-Beschäftigung ist, zu gucken, wenn da genug
Leute sind, stellt man sich hin und sagt, ich wette, zwei Leute hier
auf der Party haben am gleichen Datum Geburtstag.
Und dann hofft man irgendwie, genug Leute zu finden, die dagegen
wetten und dann fragt man alle nach ihrem Geburtstag und alle sagen,
oh tatsächlich, hast du ein Glück gehabt.
Ich denke, wenn ich die Wette hier im Hörsaal mache, würde kaum jemand
gegen mich wetten, weil hier fast so viele Leute sind wie Tage im
Jahr.
Das ist nicht so überraschend, aber was glauben Sie denn, wie groß die
Party sein muss, damit man Gewinnwahrscheinlichkeit von größer gleich
50 % hat?
Haben Sie eine Frage oder wollen Sie es sagen?
Ich würde jetzt lieber mal eine Umfrage starten.
Wer glaubt, dass 10 Leute reichen?
Wer glaubt, dass 20 Leute reichen?
Wer glaubt, dass 30 Leute reichen?
Wer glaubt, dass 50 Leute reichen?
Wer glaubt, dass man mehr als 100 braucht, damit man eine gute
Gewinnwahrscheinlichkeit hat?
Okay, also Sie lagen ziemlich richtig.
Die 20er hätten eine gute Gewinnwahrscheinlichkeit, aber ich glaube,
am Ende würden Sie im Mittel ein bisschen verlieren.
Wenn ich mich recht erinnere, brauchen Sie 23 Leute.
Das ist trotzdem erstaunlich klein und man kann jetzt natürlich als
geübter Science-Fiction-Leser sagen, wie ist das denn, wenn ich auf
einem Planeten bin mit größeren Jahreslängen?
Wie muss dann die Anzahl Party-Gäste wachsen mit der Anzahl Tage?
Man kann das dann umdrehen, wie muss die Anzahl Tage wachsen mit der
Anzahl Party-Gäste, damit das gerade passt.
Und was man feststellt ist, es reichen sowas wie Wurzel-N-Gäste, damit
man auf einem Planeten mit N Tagen pro Jahr hier gewinnt.
Mal einen konstanten Faktor.
Und die Analogie zum Hashtag ist halt die, die Elemente von m sind
unsere Gäste, die Tabellengröße klein m ist die Jahreslänge und zwei
Leute haben den gleichen Geburtstag, heißt die Hashtag-Funktion
produziert eine Kollision.
Das heißt, wenn Sie sich die Analyse jetzt anschauen, wenn Sie
wirklich eine zufällige Funktion würfeln wollen, dann brauchen Sie
eine Größe der Tabelle, die quadratisch wächst mit ihrer Menge.
Das ist nicht besonders praktikabel.
Da gibt es dann wieder Tricks, wie man das doch wieder praktikabel
macht.
Das ist aber eher Gegenstand der Algorithm Engineering Vorlesung.
Da haben wir auch gerade ein Papier auf einer Konferenz zu.
Da kann man also immer noch ein bisschen dran forschen.
Aber erstmal, perfekte Hashtag-Funktionen, nette Idee, aber nicht so
einfach.
Jetzt muss man das reparieren.
Wie gehe ich mit diesen Kollisionen um?
Und eine Möglichkeit ist ganz einfach.
Ich speichere in der Tabelle nicht Elemente, sondern Folgen von
Elementen.
Zum Beispiel einfach verkettete Listen.
Die typische Implementierung.
Und das nennt man auch Hashing with Chaining.
Also jetzt hatten wir hier unser Beispiel, die beiden Elemente
kollidieren, nicht schlimm, dann speichere ich hier einfach eine Liste
mit zwei Elementen.
Solange das nicht zu oft passiert und diese Listen nicht zu lang
werden, kann man damit leben.
Dann gucken wir uns mal an, wie man das implementiert.
Also, wir implementieren Folgen von Tabelleneintragen durch einfach
verkettete Listen.
Wie geht dann das Insert von E?
Naja, wir fügen E am Anfang von T von H von E ein.
Das ist also einfach eine Push-Front-Operation.
Remove für K.
Wir durchlaufen den Tabelleneintrag, der von H von K spezifiziert
wird.
Das ist ja eine Folge von Objekten.
Und schauen nach, ist das Ding da drin?
Wenn ich eins finde mit Key von E gleich K, wird es halt entfernt.
Das kann man mit Insert, mit Remove After, auch mit einfach
verketteten Listen.
Man muss sich ja nur den Vorgängerpointer merken.
Und dann liefere ich das halt zurück.
Das Find ist so ähnlich.
Find K heißt, ich durchlaufe den Tabelleneintrag, der durch H von K
spezifiziert wird.
Und wenn ich ein Element mit Key von E gleich K finde, liefere ich das
zurück.
Und sonst muss ich irgendwie signalisieren, dass ich es nicht gefunden
habe.
Und dann weiß ich aber auch, es ist in der Tabelle nicht drin.
Kann mir jemand sagen, was die entscheidende Datenstruktur-Invariante
von dieser Datenstruktur ist?
Von Hashing mit verketteten Listen.
Immer eine Idee.
Also die Invariante wäre jetzt einfach, ein Element ist in dem
Tabelleneintrag gespeichert, den seine Hash-Funktion angibt.
Und das nutze ich jetzt aus und das muss ich aufrecht erhalten, wenn
ich Operationen durchführe.
Und da werde ich jetzt nicht groß beweisen, dass die hier das tun.
Das ist relativ naheliegend, hoffe ich.
Gibt es Fragen zu der Hashing mit verketteten Listen?
Gucken wir uns mal ein Beispiel an.
Ich habe hier eine Tabelle mit 25 Einträgen.
Meine Hash-Funktion ist eine ziemlich dämliche Hash-Funktion.
Ich nehme mich den letzten Buchstaben eines Wortes.
Natürlich auf rein pädagogischen Gründen, weil sie dann im Kopf
relativ leicht diese Hash-Funktion auswerten können.
Ich habe mir einfach alle Synonyme von To Hash gesucht.
Also es ist nicht so, dass ich Gewaltfantasien hege oder sowas.
Sondern ich habe einfach im Wörterbuch nach Synonymen des englischen
Wortes To Hash gesucht.
Und da kommen dann To Axe, Dice, Cube, Hash, Hack, Feld, Chop, Clip
und Lob raus.
Und dann habe ich noch eins gefunden, Slash.
Wo füge ich das ein?
Naja, Hash-Funktion sagt mir, der letzte Buchstabe ist H.
Der Tabelleneintrag zu H ist hier.
Also da war vorher nur Hash drin und jetzt steht hier Slash Hash.
Also ich habe einen Push Front gemacht.
Oder was ist, wenn ich jetzt in dem Zustand das Clip entfernen möchte?
Naja, also P, okay.
Da steht Chop, Clip, Lob.
Ich laufe da durch, das ist eine verkettete Liste.
Da kann ich einen Remove After Chop machen, dann ist das Clip weg.
Fragen dazu?
Analyse.
Einfügen geht in konstanter Zeit.
Das ist egal, wie lange diese Liste ist.
Am Anfang Einfügen meiner verketteten Liste geht in konstanter Zeit.
Remove, naja, wenn es das Element zum Beispiel nicht gibt, muss ich
halt die Liste, die an der Stelle H von K steht, durchsuchen.
Wie lange dauert das?
Das ist linear in der Länge dieser Liste.
Das gleiche gilt für das Find.
Nur die Frage ist natürlich, wie lang werden die Listen?
Im schlechtesten Fall kollidiert alles.
Alle Elemente werden in einer dieser Listen gespeichert.
Dann habe ich nur eine sehr umständliche Formulierung, Speichern einer
Menge in einer verketteten Liste.
Und dann muss ich lange suchen.
Und da ist halt jetzt die Schlüsselidee, je mehr Chaos ich anrichte,
desto unwahrscheinlicher wird es, dass die wirklich alle in einer
Liste landen.
Und da kommt jetzt diese Idee zum Tragen, dass Chaos das Auffinden
erleichtert.
Und das hängt natürlich damit zusammen, dass ich das Chaos sozusagen
im Griff habe.
Es ist zwar irgendwie erstmal nicht offensichtlich, wo die Elemente
gespeichert werden, aber die Hash-Funktion sagt genau, was passiert.
Und deshalb kann ich das begrenzt beherrschen.
Übrigens scheint das auch in der Realität, also bei Hardware sozusagen
realen Gegenständen, jetzt wieder verwendet zu werden.
Da gibt es viele spannende Presseartikel darüber, wie große Internet
-Versender wie Amazon ihre Auslieferungslager organisieren.
Nämlich auch nach so einem Zufallsprinzip.
Wenn da irgendeine Ware ankommt, wird die an einer zufälligen Stelle
in der Halle gelagert.
Und man denkt auf den ersten Blick, sind die denn blöd?
Aber der Trick ist, dass sich dann halt die Leute, die da durch diese
Halle rennen und die Sachen einsammeln oder die Roboter, weiß ich
nicht, wie das genau läuft, nicht zu sehr in die Quere kommen.
Und wiederfinden ist kein Problem, weil der Computer eben genau
ausrechnen kann, wo die Positionen waren.
Genau.
So, und da möchte ich aber heute nicht mehr mit der Mathe anfangen.
Das ist so ein bisschen ein Problem.
Wir brauchen hier Wahrscheinlichkeitsrechnungen, die Sie aber
eigentlich erst im nächsten Semester lernen.
Deshalb werde ich sozusagen da so einen kleinen Crashkurs in
Wahrscheinlichkeitstheorie machen und Ihnen genau das beibringen, was
Sie hier für diese Analysen brauchen.
Damit aber heute noch anzufangen, ist nicht so sinnvoll.