Wir haben uns in den letzten beiden Vorlesungen mit Hashtabellen
beschäftigt.
Dabei habe ich zuerst mal eine relativ einfache Implementierung von
Hashtabellen über einfach verkettete Listen vorgestellt.
Und die dann beim letzten Mal auch analysiert.
Und wir haben dann sozusagen von 0 auf 100 ein bisschen
Wahrscheinlichkeitstheorie gelernt, also insbesondere die Konzepte von
einem Ereignisraum, wie zum Beispiel die Menge aller Hashtfunktionen,
Ereignisse, Wahrscheinlichkeiten, Zufallsvariablen,
Indikatorzufallsvariablen, Erwartungswerten und deren Linearität
werden Ihnen in der Vorlesung noch öfter begegnen.
Lohnt sich also das zu lernen?
Es ist nicht nur relevant für Hashtabellen.
Wir haben das dann erstmal nochmal auf das Geburtstagsparadoxon
angewendet und sozusagen ausgerechnet, was ist die erwartete Anzahl
von Partyteilnehmern mit gleichem Geburtstag und das ist eigentlich
das Gleiche wie bei Hashtabellen, die Anzahl Kollisionen.
Und das hat uns dann geholfen zu zeigen, dass wenn die Anzahl Elemente
in unserer Hashtabelle und die Tabellengröße von der gleichen
Größenordnung sind, dass dann die erwartete Listenlänge konstant ist,
die man findet, wenn man nach einem Element sucht.
Genau, ein wichtiges Detail wollte ich hier darauf hinweisen.
Man kann bei der Analyse von dieser Hashtabell-Sache auch einen
ziemlich blöden Fehler machen, wenn man sagt, naja, offenbar muss ich
zeigen, dass die mittlere Länge der Listen konstant ist.
Das ist irgendwie immer so, wenn Sie O von M Elemente auf M
Tabelleneinträge vergleichen, wenn Sie das mitteln, kommt immer M
durch M raus.
Der Trick ist, wenn jetzt alle Elemente in der gleichen Liste landen,
dann ist die mittlere Listenlänge immer noch konstant, aber die
erwartete Listenlänge für einen Schlüssel, der in dieser Liste davor
kommt, ist N.
Dann landen die halt alle in der gleichen und das nützt mir nichts,
dass die anderen alle leer sind, weil ich da nie hinkomme.
Da muss man ein bisschen aufpassen.
Aber unsere Analyse berücksichtigt das, indem sie sich anguckt, okay,
die anderen Schlüssel, wo landen die?
Und wenn die an der gleichen Stelle landen wie ich, kriege ich ein
Problem.
Das Dumme an dieser Analyse war, dass sie halt angenommen hat, dass
wir zufällige Hashfunktionen haben und es ist nicht klar, wie man das
erreicht.
Wir haben das dann abgeschwächt und gesagt, nee, wir nehmen nicht alle
möglichen Funktionen, die Elemente oder Schlüssel auf Tabelleneinträge
abbilden, sondern nur eine Teilmenge und zwar nicht irgendeine
Teilmenge, sondern eine mit dieser Universalitätseigenschaft, dass
nämlich die Kollisionswahrscheinlichkeit zwischen zwei beliebigen
Elementen, zwischen zwei beliebigen Schlüsseln eins durch
Tabellengröße sein soll.
Und diese Definition war halt gerade so gewählt, dass unsere Analyse
von hier immer noch funktioniert.
Das haben wir dann gezeigt für eine einfache Familie von
Hashfunktionen, die im Wesentlichen auf dem Skalarprodukt in einem
Vektorraummodulo einer Primzahl beruht hat.
Jetzt wollte ich Ihnen noch zwei weitere Beispiele vorstellen, die
vielleicht noch ein bisschen näher an der Intuition von Informatikern
liegen, die mit Modulorechnungen nichts am Hut haben und vielleicht
unter bestimmten Umständen auch effizienter sind.
Das eine wäre Matrixmultiplikation mit einer Bitmatrix.
Unsere Hashfunktionen werden alle generiert über eine Matrix von W mal
K zufälligen Koeffizienten 0 oder 1, also Bits.
W war die Anzahl Bits einer Adresse in meiner Tabelle, also ich habe
zwei hoch W Tabelleneinträge und K war die Anzahl Bits meines
Schlüssels.
Dann ist die ausreichende Hashfunktion gleich eine
Matrixmultiplikation Modulo 2.
Wenn Sie sich das angucken, bedeutet das, Sie nehmen den Schlüssel,
nehmen den als Spaltenvektor, transponieren den auf eine Zeile und
gehen dann immer durch die Zeilen der Matrix, machen dann
Skalarprodukt Modulo 2.
Was bedeutet denn das?
Sie müssen im Prinzip eine Koeffizientenweise Multiplikation,
Multiplikation Modulo 2 ist einfach das logische Und.
Und dann wird das alles addiert, das ist XOR, also ist das im Prinzip
die Parität jeder dieser Zeile.
Sie können das dann auch gleich für eine ganze Spalte immer
aufaddieren, da gibt es dann Möglichkeiten, das noch ein bisschen
effizienter zu implementieren.
Trotzdem ist das so, dass das nicht so super schnell ist.
Eine Matrixmultiplikation ist halt schon irgendwie dann W mal K Bit
-Operationen, die können Sie dann den Bit-Parallelismus Ihres
Maschinenworts ausnutzen.
Trotzdem sind es dann immer noch eine ganze Reihe Operationen.
Sie würden jetzt gerne eine ganz kleine Anzahl Operationen haben.
Da kann man dann den Tabellenzugriff nehmen.
Das ist jetzt von der Notation her ein bisschen abschreckend, deshalb
nehmen wir uns da mal ein bisschen Zeit, das zu lesen.
Also hier wird die Hash-Funktion erzeugt durch mehrere Lookup
-Tabellen.
Da könnten Sie sagen, aha, jetzt macht er doch wieder einfach
zufällige Funktionen.
Aber diese Lookup-Tabellen sind jetzt eben nicht über den ganzen
Schlüssel, sondern immer über kleine Stücke von A Bits des Schlüssels.
Das ist sozusagen das, was Sie jetzt als Vereinfachung gegenüber dem
völlig allgemeinen Fall zufälliger Hash-Funktionen machen.
Also es ist dann indiziert mit B solchen Tabellen.
Die Idee versteht man am besten, wenn man nicht sofort versucht, diese
Formel zu lesen, sondern sich einfach das simple Bild hier anguckt.
Sie haben halt Ihren Schlüssel mit K Bits.
Den teilen Sie ein in einen Block mit W Bits.
Das sind zum Beispiel die least significant Bits von diesem Schlüssel.
Die werden direkt verwendet.
Die könnte man ja benutzen, um die Hash-Tabelle zu adressieren.
Aber das ist keine gute Hash-Funktion, weil man dann die anderen Bits
nicht verwendet.
Deshalb verwendet man die auch.
Man teilt die jetzt in Blöcke von jeweils A Bits ein.
Für jeden dieser Blöcke macht man einen Tabellenzugriff in einer
Tabelle mit Zufallswerten.
Und für jeden dieser Blöcke muss man eine eigene Tabelle haben, damit
das funktioniert.
Ausrechnen der Hash-Funktion ist ganz einfach.
Man zerschneidet den Schlüssel in diese Teile, macht dann für diese
hier einen Zugriff auf die Tabelle, nimmt das hier direkt und die
Teilergebnisse, die man kriegt, werden alle per XOR zusammen addiert.
Mehr steht hier auch nicht.
Und da kann man relativ leicht zeigen, dass das universell ist.
Es ist sogar so, wenn Sie das hier weglassen, also das wirklich mit
jedem Stück Ihres Datums diese Tabellenzugriffe machen, dann kann man
unter bestimmten Umständen noch stärkere Eigenschaften dieser Hash
-Funktion zeigen.
Dann zum Beispiel die sich verhalten fast wie zufällige Hash
-Funktionen.
Das braucht man aber für Hash-Tabellen oder wenn die nur erwartet
schnell sein sollen, braucht man das nicht.
Gibt es Fragen zu diesen universellen Familien von Hash-Funktionen?
Okay, dann wäre das halt der Teil zu Hashing mit linearer Verkettung
und ihrer Analyse.
Jetzt machen wir ein anderes Verfahren, wo die theoretische Analyse
nicht ganz so einfach ist, die aber in der Praxis, ich sage mal,
genauso nützlich oder wichtig sind wie Hashing mit linearer
Verkettung.
Und zwar Hashing mit linearer Suche oder im Englischen linear probing.
Wir gehen hier einen Schluck zurück zu der Ursprungsidee, die ja darin
bestand, die Elemente direkt in der Hash-Tabelle abzuspeichern.
Und da war ja das Problem, es gibt diese Kollisionen.
Und jetzt ist die Idee, naja, wenn mehrere Elemente auf die gleiche
Stelle in der Tabelle abgespeichert werden, dann verteile ich die halt
irgendwie.
Da gibt es verschiedene Ansätze.
Aber der einfachste und effizienteste Ansatz in der Praxis besteht
darin, einfach linear weiterzusuchen.
Also stellen Sie sich mal vor, man würde diese Elemente wirklich
nacheinander platzieren in der Tabelle.
Also der kommt dahin, der dahin, der dahin, der dahin und jetzt wollen
Sie den dahin tun, da ist aber schon was.
Dann sagen Sie, okay, jetzt werde ich verdrängt, jetzt suche ich so
lange, bis ich einen freien Eintrag in der Tabelle finde.
Und dann gibt es noch den Spezialfall, es könnte jetzt passieren, dass
man irgendwie bei der Suche nach einem freien Eintrag ans Ende der
Tabelle kommt.
Da ist die Standardimplementierung, dass man dann am Anfang wieder
anfängt.
Und da kann man sich dann überlegen, das ist korrekt, solange die
Anzahl Elemente in der Menge, die man speichern will, nicht größer ist
als die Tabellengröße.
Wenn die größer wird, würden Sie irgendwann unendlich suchen.
Warum stelle ich das vor?
Das Ganze ist sehr einfach.
Sie brauchen also keine Pointer, keine verketteten Listen.
Es ist ziemlich platzeffizient unter bestimmten Umständen.
Also insbesondere, wenn Sie hier jetzt sehr geizig sind, können Sie
dafür sorgen, dass die Tabelle nur wenig größer ist als die Menge, die
ich abspeichern will.
Und dann haben Sie auch keinen zusätzlichen Platz für Zeiger von
verketteten Listen, Elementen und sowas.
Das heißt im Extremfall ist der Speicherplatz in gewisser Weise
bestmöglich.
Sie haben ein paar leere Einträge, aber eigentlich fast volles Array,
das direkt die Elemente speichert, die Sie haben wollen.
Viel besser geht es im Allgemeinen ja nicht.
Und in der Praxis vielleicht noch wichtiger, das Ganze ist cache
-effizient.
Während Sie suchen, greifen Sie auf einen Teil dieser Tabelle zu und
suchen da linear drin.
Dann kriegen Sie eine Cache-Lokalität.
Caching funktioniert ja so, in Wirklichkeit ist diese Tabelle in
mehrere Cache-Blöcke eingeteilt.
Und wenn Sie einen Block davon lesen, in dem vielleicht dann acht
Elemente passen oder sowas, lesen Sie gleich die anderen Elemente in
dem Block mit.
Und im Mittel ist das dann so, dass Sie bei dieser Suche dann keine
weiteren Cache-Falls mehr erzeugen oder vielleicht nur ein oder zwei
im Mittel.
Deshalb ist das in der Praxis manchmal einen deutlichen Faktor
schneller als Caching durch Verkennen.
So, jetzt gucken wir uns das mal als Pseudocode an.
Was sich herausstellen wird, ist, einfügen und suchen ist super
einfach.
Entfernen muss man ein bisschen nachdenken.
Da ist es sogar so, dass in den meisten Lehrbüchern da ziemlicher
Unsinn steht zum Entfernen.
Das heißt, die stellen da Verfahren vor, die im Allgemeinen nicht
funktionieren, die langsam sind, die kompliziert sind.
Ich werde ein Verfahren vorstellen, das ein bisschen kompliziert ist,
dafür aber funktioniert und effizient ist.
Aber erst mal die einfachen Teile.
Also, die Klasse nenne ich Bounded Linear Probing.
Ich werde also nicht eine allgemeine Hashtabelle vorführen, deren
Größe sich mit der Menge der zu speichernden Elemente adaptiv
vergrößert, sondern man muss dann bei der Erzeugung die Tabellengröße
mit angeben und es ist wichtig, dass die Anzahl Elemente da nicht
darüber hinaus wächst.
Wenn Sie das nicht wollen, dann schauen Sie sich das Kapitel über
anbauende Arrays an und es ist völlig analog.
Also Sie müssen dann irgendwas einbauen, wenn die Anzahl Elemente zu
groß wird, dann wird ein neues Array allociert und das Ganze
umkopiert.
Um das noch einfacher zu machen, habe ich hier einen Dirty Trick
gemacht und eine etwas ungewöhnliche Implementierung gewählt, die man
in der Praxis vermutlich auch nicht machen würde, aber ich möchte halt
möglichst viele von diesen Funktionen auf eine Folie kriegen, damit
das hier in der Vorlesung möglichst einfach erklärbar wird.
Man macht jetzt folgendes, Sie haben diese Tabelle mit m Einträgen,
die ist hier rot dargestellt, und dann hängt man da noch ein paar m
Strich zusätzliche Einträge dran als Überlaufbereich.
Dann muss man niemals dieses Wraparound machen, also das ist wieder am
Anfang anfangen.
Allerdings im schlechtesten Fall werden dann alle Elemente hier auf
das letzte Element der Tabelle gemappt und dann können Sie nur m
Strich Elemente speichern.
Das wird in der Praxis nicht so schlimm sein, weil das
unwahrscheinlich ist, dass so viele Elemente auf die gleiche Stelle
kommen.
Aber eigentlich ist dieses Wraparound nicht so schlimm.
Aber wir machen das jetzt, weil das uns ein paar zusätzliche Kotzeilen
und Komplikationen spart.
Meine Tabelle ist jetzt ein Array von Elementen, wie gehabt, und hat
wie viele Einträge?
Naja, m plus m Strich.
Und was wichtig ist, ich habe irgendeinen Wert Bottom, der
unterscheidbar ist von allen tatsächlichen gültigen Werten.
Das ist so ein bisschen ein Implementierungsproblem, dass das
vielleicht, wenn ich jetzt eine Software-Library bauen will, müsste
ich mir überlegen, kann ich das für jedes beliebige Element
sicherstellen, beziehungsweise ich müsste dann halt verlangen, dass
jeder Elementtyp so eine Methode Bottom zur Verfügung stellt, von
einem Element, das unterscheidbar ist von allen richtigen Elementen.
In einer konkreten Anwendung geht das immer, in der Library ist das
gleich ein bisschen ein Problem.
Oder man müsste halt explizit ein zusätzliches Gültig-Bit oder so
hinzufügen.
Okay?
Die Invariante ist auf den ersten Blick auch ziemlich hässlich, auf
den zweiten Blick aber drückt sie nur das aus, was man sich
vielleicht, hoffentlich ohnehin denkt.
Also die konzeptionelle Schwierigkeit, die wir uns einhandeln bei
diesem Linear-Probing-Algorithmus ist, dass wir ja Elemente zum Teil
an Stellen abspeichern, die gar nicht die Stelle sind, die die Hash
-Funktion vorgibt.
Deshalb muss es einen Grund geben, dass ein Element woanders
abgespeichert ist.
Und das wird hier ausgedrückt.
Also das steht für beliebige I, also für beliebige Tabelleneinträge
gilt, wenn der Tabelleneintrag ein Element speichert, dann muss gelten
für alle Tabelleneinträge von H von T von I.
Das ist die Stelle, wo die Hash-Funktion eigentlich sagt, da sollte
dieses Element hin.
Bis zu dieser Stelle steht tatsächlich irgendwas Nützliches drin.
Der Grund ist ganz einfach und den sieht man am besten, wenn man sich
das Find anschaut.
Also wie funktioniert das Suchen?
Ich werte die Hash-Funktion aus, gucke an der Stelle nach, ist da mein
Element?
Wenn nein, suche ich so lange weiter, bis ich entweder das Element
gefunden habe oder so ein Undefined gefunden habe.
Wenn ich ein Undefined gefunden habe, gehe ich davon aus, das Element
ist nicht drin und sage, hallo, ist gar nicht da.
Aber dafür muss ich sicherstellen, dass wenn das Element nicht da ist,
wo die Hash-Funktion sagt, dass dazwischen nicht irgendwelche leeren
Einträge sind, weil dann würde es nicht mehr wiedergefunden werden.
Und das sagt diese Invariante und das wird später beim Entfernenbefehl
zu einem Problem führen, warum wir da keinen völlig naiven Algorithmus
anwenden können.
Insert ist auch einfach, also Insert eines Elements.
Ich initialisiere meine Suchposition I mit der Hash-Funktion von E.
Wohlgemerkt, H von E ist nur eine Kurzform für H von Key von E.
Und solange dieser Tabelleneintrag nicht leer ist, suche ich weiter.
Das ist jetzt wichtig, dass ich diesen Überlaufbereich habe.
Selbst wenn ich jenseits von Position M bin, habe ich immer noch M
Strichstellen, wo ich weitersuchen kann.
Und die Hash-Funktion wird aber nie hier hingehen, sondern
schlimmstenfalls hier hin.
Und da müsste ich dann statt I++ so ein I++ Modulo M oder sowas
machen, wenn ich den Wraparound haben will.
So, jetzt verlange ich, dass die Position kleiner ist als M plus M
Strich minus 1.
Und zwar echt kleiner.
Kann mir jemand sagen, warum echt kleiner und warum nicht kleiner
gleich?
Also ich verlange hier, dass der allerletzte Tabelleneintrag hier
unten, dass der immer leer ist.
Warum tue ich das?
Ja?
Gibt es eine Idee da oben?
Genau, also wenn ich das nicht machen würde, könnte es passieren, dass
ich sozusagen aus der Tabelle rauslaufe, hier einen Zugriff mache, der
out of array bound ist oder sowas.
Da würde mein Programm abschmieren.
Das will ich nicht.
Deshalb mache ich vorher schon so eine Assertion, die dann testet,
aha, wenn ich jetzt wirklich ganz am Ende bin, dann werfe ich eine
Fehlermeldung aus, da ist irgendwas falsch.
Genau, also jetzt suche ich die erste freie Position und da speichere
ich mein Element hin.
Also eigentlich ein Zweizeiler, also diese Vorschleife und das.
Meistens sind ja meine Schleifen in diesem Pascal-Stil, weil ich den
typografisch schöner finde.
Hier ist jetzt mal ein Fall, wo man ganz gerne eine Abbruchbedingung
wie eine Weil-Schleife haben will und weiterschalten wie eine
Vorschleife.
Das kann man in c-artigen Sprachen etwas schöner ausdrücken, deshalb
mache ich das einfach.
Die Freiheit nehme ich mir.
Suchen geht genauso.
Ich werte die Hash-Funktion diesmal für den Schlüssel aus, weil das
Element kenne ich ja gar nicht.
Solange das nicht leer ist,
suche ich weiter, aber es gibt noch eine Abbruchbedingung.
Wenn der Schlüssel des Eintrags der an der i-ten Stelle
abgespeicherten Elements gleich dem gesuchten Schlüssel ist, dann gebe
ich dieses Element zurück.
Wenn das nicht der Fall ist, heißt das, dass ich hier einen nicht
definierten Eintrag gefunden habe.
Das heißt, das Element ist nicht drin und das stellt mir diese
Invariante sicher.
Gibt es dazu Fragen?
Zum Entfernen.
Jetzt gucken wir uns mal so einen Fall an, wo da etwas Relevantes
auftritt.
Dann nehmen wir mal an, unsere Tabelle sieht so aus.
Hier steht x, y, z.
Z würde eigentlich gerne an die Stelle, wo das x ist.
Aber zu dem Zeitpunkt, wo es eingefügt wurde, waren schon x und y da,
sagen wir mal.
Deshalb wurde es dahinter gespeichert.
Und wie handhabe ich sowas?
Ich will da jetzt gar nicht sofort in den Pseudocode gehen, sondern
einfach mal ein Beispiel erst mal rechnen.
Und dann sieht man, glaube ich, schon eher, was passiert.
Und zwar einschließlich Aufbau der Datenstruktur.
Hier haben wir wieder unsere beliebten Synonyme von toHash.
x.top.clip.cube.dice.fell.hack.hash.lob.slash.
Unsere Hash-Funktion ist letzter Buchstabe,
durchnummeriert von 0 bis 26, Modulo 13, 0 bis 25 und das ganze Modulo
13.
Also a wieder auf 0, b auf 1, c auf 2, d auf 3 und so weiter, m auf 12
und dann n wieder auf 0, o, p, q und so weiter.
Also Sie sehen hier mal die Position in der Tabelle, hier die
Buchstaben, die darauf abgebildet werden und ich nehme den letzten
Buchstaben.
Wieder die Warnung, das ist keine gute Hash-Funktion, aber vereinfacht
uns das Rechnen von Beispielen.
So, jetzt füge ich die Elemente in dieser Reihenfolge ein.
x, okay, i, freier Tabelleneintrag, super.
Chop, p, wo ist das p?
Da, freier Tabelleneintrag, super.
Grau eingefärbt sind hier immer die zugegriffenen Tabellenteile.
Jetzt wird es interessanter.
Clip, auch ein p als letzten Buchstaben, der will hier hin.
Chop steht da schon, ich suche einen weiter, da ist frei, prima.
Jetzt Cube, e, da steht schon das e, einen weitersuchen, ich finde
was, prima.
Dice, e, da steht das x, jetzt muss ich zwei weitersuchen, da habe ich
was.
Ich glaube, mir verhungert gleich wieder mein Laser.
Das heißt, der behauptet voll zu sein.
Prima,
ich hoffe, dass er durchhält.
Fell, das l ist hier, aber da ist frei, da gibt es nichts viel zu
sagen.
Hack, k, das ist auch unproblematisch.
Hash, h, auch frei.
Und jetzt wird es heftig.
Lob, will hier hin und da steht jetzt dieser ganze Müll schon, der
überhaupt nichts mit der Hash-Funktion p am Ende zu tun hat.
Und da muss ich das also hinter dieses Ding schieben.
Also da muss man sich jetzt überlegen, da werden Elemente mit
verschiedensten Schlüsseln durcheinander gemixt, auch mit
verschiedensten Hash-Funktions-Werten und ich muss die trotzdem
korrekt wiederfinden.
Da muss man schon ein bisschen aufpassen.
Lob, muss hier auch nochmal ganz durch, also Lob hatten wir gerade und
das Slash, das muss ein bisschen suchen.
So, jetzt wollen wir, ich habe mir dann natürlich ein hässliches
Beispiel ausgesucht, das Clip entfernen.
Jetzt suchen wir erstmal das Clip, okay, Hash-Funktion ist p, ich
suche bis ich es finde, das ist hier.
Jetzt merke ich mir, ich würde das gerne entfernen.
So, jetzt frage, was geht schief, wenn ich hier einfach so ein Bottom
-Element reinschreiben würde?
Wäre ich dann fertig?
Es würde zu Problemen führen und können Sie das näher sagen, zu
welchen Problemen?
Genau, also man kriegt Probleme beim Suchen, zum Beispiel, was würde
ich nicht mehr finden?
Genau, also der Kollege sagt, das Lob finde ich dann nicht mehr, weil
wenn hier ein Bottom wäre, dann würde er sagen, oh, p, chop, nee, das
ist nicht Lob.
Undefined, oh, ist nicht drin.
Und wird vergessen, dass das da tatsächlich drin steht noch.
Wie gehe ich damit um?
Ja, gucken wir mal.
Also ich merke mir jetzt erstmal, hier ist eigentlich ein Loch in der
Tabelle, das ich stopfen muss.
Ich muss meine Invariante reparieren, das mache ich schrittweise,
indem ich hier durchscanne.
Gucken wir mal, mit dem Axe habe ich kein Problem, das ist an der
Stelle, wo es hin will.
Da ist es nicht schlimm, dass da ein Loch ist.
Das Cube ist zwar nicht da, wo es hin will, aber das adressiert erst
hier hin, sucht dann da, kein Problem.
Dice wird auch über hier gefunden.
Hash, ja, das steht da, wo es hin will, auch kein Problem.
Lob, das ist jetzt das Problem, das Ihr Kommilitone gerade genannt
hatte.
Da suche ich von hier und würde da hin laufen.
Woran erkenne ich das, dass ich ein Problem habe?
Das erkenne ich daran, der Hash-Funktionswert für p, das ist 2, steht
links von dem Loch.
Da kriege ich ein Problem, aber dann mache ich doch folgendes.
Ich schiebe das Lob einfach hier rüber, dann wird es sogar eher
gefunden, das ist sozusagen gut für das Lob.
Und dann kann ich mein Loch hier hinschieben.
Und jetzt muss ich weitersuchen.
Jetzt kommt das Slash, das würde eigentlich gerne hier hin.
Ah, Hash-Funktion ist links von dem Loch, Lob.
Ja, dann mache ich doch folgendes, dann schiebe ich das Slash hier
hin, in das Loch, und mache mein Loch hier hin.
So, und jetzt mache ich weiter, Hack ist da, wo es hin will, Fell ist
auch da, wo es hin will, Undefined.
Ah, jetzt bin ich fertig.
Jetzt bin ich fertig und dann kann ich das Loch einfach mit so einem
Bottom überschreiben.
Also allgemeiner, ich scanne durch die Tabelle, bis ich das nächste
Undefined finde.
Das ist so wie bei einem nicht erfolgreichen Find, also gar nicht so
schlimm.
Und ich repariere immer die Schleifen-Invariante bis zu meiner
aktuellen Position.
Und ich kann hier abbrechen, weil da immer sowas steht, naja,
dann steht da sowieso das Loch dazwischen und dann kann das nicht mehr
zu irgendwas führen.
Weil vorher ja die Invariante erfüllt war, kann hier nichts mehr
stehen, was relevant ist für das Loch, das ich gerade habe.
So, und jetzt gucken wir uns das als allgemeinen Pseudocode an.
Hier ist nochmal die Invariante angegeben, Funktion Remove für
eingegebenen Schlüssel.
Das hat jetzt zwei Phasen.
Erstmal suche ich den Schlüssel selber.
Wenn der nicht drin ist, dann brauche ich auch nichts zu tun.
Ansonsten würde ich den gerne löschen, also in dieser Sprachweise von
diesem Code.
Wir haben ein Loch an der Stelle i.
So, und jetzt gehe ich ab der Stelle i plus 1 weiter und repariere die
Invariante.
Und Problem tritt nur dann auf, wenn der Hash-Funktionswert von der
aktuellen Stelle j kleiner gleich dem Loch ist.
Dann schiebe ich das aktuelle Element tj in das Loch und verschiebe
meine Lochposition auf die aktuelle Position.
Und ganz am Ende kann ich das Loch mit diesem Bottom überschreiben.
Fragen dazu?
Also das Ganze ist wirklich nicht so schlimm.
Ich scanne von der Hash-Position bis zum nächsten Bottom.
Das ist so wie bei einem erfolglosen Find.
Ich habe das Ganze aufgeteilt in zwei Schleifen.
Ich habe genau eine Abbruchbedingung und ich muss einen zusätzlichen
kleinen Kleinergleich-Test machen.
Und wenn der gilt, irgendeinen Swap machen.
Also das Ganze kostet vielleicht zweimal so viel wie ein erfolgloses
Find.
Ist also insgesamt relativ schnell.
Zum Vergleich, was andere Bücher vorschlagen, ist dann...
Entweder verbieten sie das Remove-Gant, das ist halt auch nicht schön.
Oder sie sagen, man macht da irgendwie eine Markierung hin, dies ist
ein gelöschter Tabelleneintrag.
Das erste Problem, dass man sich damit einhandelt, ist, man braucht
nochmal einen zusätzlichen Wert, der von allen anderen unterscheidbar
ist.
Das zweite Problem ist, wenn man viel löscht, füllt sich irgendwann
die ganze Tabelle mit diesen Löschmarkierungen.
Das heißt, man muss dann, selbst wenn die eigentliche Logik sagt, ich
weiß, da sind nie mehr als tausend Einträge drin, muss ich trotzdem
irgendwie was haben, was dafür sorgt, dass nach ganz vielen Insert-
und Remove-Operationen die Tabelle irgendwie neu aufgebaut wird.
Oder man einmal ganz durchscannt und diese Löscheinträge beseitigt und
dann wieder alles richtig baut.
Ich bin sicher, das ist komplizierter als die fünf Zeilen, die wir
hier gebaut haben, um das Ganze einmal richtig zu machen.
Und es ist natürlich langsamer, wenn Sie dann diese Löschmarkierungen
haben, die zwischendurch Ihnen die Suchen verlangsamen und für diesen
Reparaturschritt nochmal zusätzliche Zeit brauchen.
Ist mir ja unverständlich, warum diese Lösung nicht in jedem Lehrbuch
so drinsteht.
Beispiel hatten wir schon.
Und jetzt möchte ich mal dieses Hashing durch Verketten vergleichen
mit dem Hashing durch lineare Suche.
Was ist denn jetzt besser?
Ich war lange ein Fan von dieser linearen Suche, weil ich was übrig
habe für cache-effiziente Algorithmen.
Aber je mehr Anwendungen ich gesehen habe, je mehr Experimente wir
ausprobiert haben, desto weniger kenne ich eine Antwort.
Das kommt auf so viele Dinge an, dass das sehr schwierig zu sagen ist
und das möchte ich jetzt einfach mal so ein bisschen Ihnen vorführen,
worum es da überall alles gehen kann.
Ein klarer Vorteil von Verketten ist, wenn meine Tabelle vollläuft,
plötzlich mehr Elemente enthält, als ich ursprünglich geplant habe,
dann reagiert dieses Verketten sehr robust, dann werden die Listen
etwas länger, aber im Mittelhalt, Anzahl Elemente durch
Tabelleneinträge, solange das irgendeine Konstante ist, ist das
einigermaßen schnell.
Während die lineare Suche, selbst wenn man die dann über ein unbounded
Array implementiert, dann plötzlich nur noch amortisiert konstante
Einfügezeit hat.
Beim Cache ist die lineare Suche klar besser, vor allem auch, manchmal
möchte man nicht nur suchen, entfernen, einfügen, sondern auch etwas
für alle Elemente in der Hashtabelle tun.
Das ist halt viel schneller, wenn man einfach nur durch so ein Array
durchscannt und einfach alles mal durchführt.
Welche der Methoden ist denn jetzt schneller und platzeffizienter?
Und wie ist da der Trade-off?
Das ist unheimlich kompliziert.
Wovon hängt das ab?
Zunächst mal von der Anzahl Elemente.
Insbesondere diese Cache-Effizienz-Sachen hängen natürlich davon ab,
ist das Ganze im Cache oder nicht.
Dann vom Füllgrad.
Mathematisch ist es ganz spannend, dass bei Hashing mit linearer
Suche, wenn Sie sich einer komplett gefüllten Tabelle nähern, dann
wachsen die Suchzeiten irgendwann immer stärker.
So dass es traditionell, wenn man sich Anzahl-Schlüssel-Vergleiche
anguckt, immer gesagt wird, Hashing mit linear Probing ist langsamer,
vor allem wenn der Füllgrad sehr hoch ist.
Und das muss man dann wieder in Beziehung setzen zu der höheren Cache
-Effizienz und dann weiß man es irgendwann nicht mehr, was schneller
oder langsamer ist.
Jedenfalls sollte man darauf achten, dass wenn man Hashing mit
linearer Suche verwendet, um etwas Schnelles hinzukriegen, dass man
dann auch ein bisschen großzügig sein sollte mit dem Platz.
Während umgekehrt manchmal macht man das, um das Platz effizient zu
haben, dann muss man sich aber bewusst sein, dass das auch für die
Laufzeit Auswirkungen hat.
Also es hängt ab von der Größe, es hängt ab vom Füllgrad, es hängt
auch ab von der Elementgröße.
Wenn die Objekte, die ich in der Hashtabelle speichere, sehr groß
sind, Kilobytes von mir aus, dann ist der Speicher-Overhead für so
einen Zeiger in der verketteten Liste vernachlässigbar.
Dann sind aber andererseits leere Einträge in dieser Tabelle
unheimlich teuer.
Also dann ist es viel platzeffizienter, mit verketteten Listen zu
arbeiten.
Und umgekehrt, wenn die Elemente sehr klein sind, dann schlagen
Disappointer ziemlich ins Kontor.
Dann geht es, wenn man das genauer aufdröseln will, auch noch um
Implementierungsdetail bei den verketteten Listen.
Ich habe ja schon mal gesagt, man sollte auf keinen Fall bei Hashing
with Linear Probing diese Default-Implementierung aus dem ersten
Kapitel nehmen, wo man diese Dummy-Elemente hat, weil wenn die
mittlere Listenlänge in der Nähe von 1 liegt, dann ist so ein Dummy
-Element sehr teuer.
Also man macht dann entweder wieder diesen Fall mit dem Nullzeiger als
Endeindikator, und da man hier nur ganz wenig verschiedene Operationen
braucht, ist das nicht zu kompliziert, oder man hat ein einziges Dummy
-Item, das sich alle Listen teilen.
Das funktioniert in diesem Fall.
Als Endemarkierung zumindest geht das.
Dann, was speichern Sie in der Tabelle?
Ich sage mal, die klassische Implementierung ist die, dass man sagt,
und das wäre in Java wahrscheinlich erst recht so, na ja, da steht im
Endeffekt ein Zeiger auf das erste Listen-Element.
Aber das ist ein Problem für die Laufzeit.
Also wenn Sie jetzt suchen, selbst wenn Sie es sofort finden, selbst
wenn keine Liste länger als 1 ist, Sie müssen erst mal die Tabelle
zugreifen, dann den Zeiger dereferenzieren, und dann dieses Item
zugreifen und da halt Schlüsselvergleich und sowas.
Das heißt, Sie kriegen dann bei einer großen Tabelle immer zwei Cache
-Faults.
Das kann man verhindern, indem man in dieser Tabelle selber schon
diese List-Items speichert.
Ich glaube nicht, dass man das in Java hinkriegt, aber in C könnte
man, da hat man viel mehr Kontrolle über das Speicher-Layout, könnte
man das so machen, in der Tabelle steht erst mal ein List-Item drin,
mit dem Element.
Und dann hat man, wenn man Glück hat, ist da schon alles gefunden und
dann habe ich nur einen Cache-Fault.
Und man spart sich eben auch einen Zeiger wieder.
Andererseits werden die Tabelleneinträge wieder größer.
Ich speichere da immer ein Element und einen Zeiger.
Und ob das jetzt besser ist oder schlechter, hängt wiederum von der
Elementgröße ab.
Also das ist wahnsinnig kompliziert auszurechnen.
Sie haben verschiedenste Implementierungsdetails.
Je nach Situation ist das eine oder das andere ein bisschen besser.
So, das geht dann noch weiter.
Was ist denn überhaupt der Platzverbrauch?
Das hängt ja auch davon ab, wie Ihre Speicherverwaltung funktioniert.
Und auch, was das Zugriffsmuster ist.
Also Speicherverwaltung erstmal für diese List-Items, da brauche ich
Garbage -Collection in Java oder Freilisten oder was auch immer.
Und wenn Sie eine unbounded Array-Implementierung haben für das
lineare Suchen, ist das auch nicht schön.
Da haben Sie das Umkopieren und dann muss die Speicherverwaltung
irgendwelche großen freien Blöcke finden, die es vielleicht nicht mehr
gibt.
Wobei es durchaus vielleicht noch ein paar Terabyte Platz hätte in
ganz kleinen Objekten, sodass Verketten dann wieder besser wäre.
Also es ist wirklich schwierig, da eine konkrete Antwort zu geben.
Es kommt immer darauf an.
Man muss es dann ausprobieren.
Oder eben sehr genau analysieren, was die Situation ist.
Also wir haben zum Beispiel relativ oft Anwendungen, wo man eine obere
Schranke für die Tabellengröße kennt.
Und dann ist meistens das lineare Suchen besser.
Dann gibt es noch Sachen, die nicht nur mit Effizienz zusammenhängen.
Referentielle Integrität, was meine ich damit?
Ganz oft möchte man in einer Hashtabelle Objekte speichern, auf die
man auch über Zeiger direkt zugreift.
Und möchte die dann vielleicht auch mal ändern und sowas.
Also das Hashing mit linearer Suche, zumindest in C++, verschiebt aber
direkt die Objekte.
Und das ist auch Grund dafür, dass ich diese hohe Cache-Effizienz
habe.
Andererseits in dem Moment, wo ich Objekte ungefragt verschiebe, kann
ich nicht anderswo Zeiger darauf halten.
Die würden dann inkorrekt oder ich müsste zusätzliche Maßnahmen
treffen, um diese Zeiger auf den neuesten Stand zu bringen.
Und das ist auch wieder hässlich.
Also wenn ich diesen Aspekt haben will, dass ich diese referenzielle
Integrität haben will, irgendwo Zeiger auf meine Objekte haben will,
dann kann ich praktisch nur mit verketteten Listen arbeiten.
Und aus theoretischer Sicht ist es also diese Analyse für universelles
Hashing, die funktioniert so, wie ich sie vorgeführt habe, nur für das
Verketten.
Da ist tatsächlich sogar in den letzten Jahren noch relativ viel
Forschungsarbeit passiert, um überhaupt zu verstehen, was passiert bei
dem Hashing mit linearer Suche.
Also der Trick, ich kann da nicht in die Details gehen, das ist
wirklich ziemlich kompliziert.
Der grundsätzliche Punkt, warum das schwierig ist beim linearen
Suchen, ist aber, dass die Tabelleneinträge nicht völlig unabhängig
voneinander sind.
Die Tabelleneinträge für einen Schlüssel A können einen Schlüssel B
beeinflussen, obwohl die komplett unterschiedliche Hashfunktionen
haben und auch obwohl die auf komplett verschiedene Teile der
Hashtabelle gemappt werden, einfach weil man bei dem Auflösen dann
trotzdem wieder auf dieses B stoßen kann.
Und das macht die Mathematik in der Analyse viel komplizierter.
Das läuft dann daraus hinauf, dass man Hashfunktionen braucht mit
stärkeren Eigenschaften als nur Universalität.
Da muss man dann auch irgendwie so Unabhängigkeitsannahmen machen.
Gibt es noch Fragen zu Verketten versus lineare Suche?
Ich weise darauf hin, dass das auch wieder ein schönes Reservoir für
so kurze Fragen in der Klausur ist.
Argumentieren Sie in beide Richtungen, was ist an der folgenden
Aussage zu ungenau?
Hashing durch Verketten ist plus effizienter als Hashing durch lineare
Suche.
Argumentieren Sie in beide Richtungen.
Irgendwie sowas könnte man fragen.
Gibt es jetzt Fragen dazu?
Dann gibt es im Buch ein Kapitel über perfektes Hashing, das ist aber
ein bisschen fortgeschrittener und eher was für Algorithmen 2.
Blick über den Tellerrand für Hashing.
Habe ich schon gesagt, für Linear Probing muss man ein paar Sachen
tun.
Wir haben uns in unserer Analyse auch im Wesentlichen die erwarteten
Suchzeiten angeschaut.
Manchmal möchte man so etwas haben wie Aussagen mit hoher
Wahrscheinlichkeit.
So etwas wie die Wahrscheinlichkeit, dass eine Liste bei Hashing mit
Chaining länger wird als zweimal Log N ist höchstens 1 durch N
Quadrat.
Oder solche Aussagen möchte man manchmal haben.
So etwas kann man auch zeigen, braucht aber stärkere Eigenschaften der
Hash -Funktionen.
Vielleicht möchte ich auch im schlechtesten Fall gut sein, dass sich
zumindest die Suchzeiten immer konstant sind.
Das geht auch mit relativ einfachen, praktikablen Hashtabellen
-Datenstrukturen.
Das steht hier dann auch nochmal.
Das ist eine Möglichkeit, das zu implementieren, ist dann wieder
perfektes Hashing.
Und dann möchte ich darauf hinweisen, dass man unterscheiden sollte
zwischen der Datenstruktur Hashtabelle, wie ich sie jetzt vorgestellt
habe, und der Technik Hashing oder der Verwendung von Hash-Funktionen.
Da gibt es noch deutlich mehr Anwendungen, als nur konkret
Hashtabellen zu machen.
Zum Beispiel gibt es da Anwendungen für Speicherserver, zum Beispiel
zur Platzierung von Daten auf diesen Servern, oder zur Verwaltung von
P2P -Netzwerken, oder für Volltextsuche und vieles andere mehr.
Also Hash-Funktionen sind eine sehr wichtige Technik in der Informatik
mit vielen weiteren Anwendungen.
Und Hashtabellen sind nur eine davon.
Weitere Fragen zu Hashing?
Ja, vielleicht doch noch ein bisschen mehr Zusammenfassung nochmal.
Ich möchte immer wieder darauf hinweisen, dass das Ziel hier nicht
ist, einfach eine Technik, einen Algorithmus, eine Datenstruktur nach
der anderen vorzustellen, sondern auch allgemeine Techniken.
Jetzt ist es tatsächlich so, Hashtabellen sind so häufig benötigt, die
kann man auch schon wieder als eine Algorithmenentwurfstechnik
ansehen.
Also wenn Sie ein algorithmisches Problem haben, bei dem es darum
geht, Daten abzuspeichern und wiederzufinden, und das ist ganz oft der
Fall natürlich, dann sollten Sie immer daran denken, geht das mit
Hashtabellen oder gibt es einen Grund, warum das nicht geht und welche
nehme ich dann?
Wir haben hier außerdem ein erstes sehr schönes Beispiel für den
Einsatz von Zufall im Algorithmenentwurf gesehen.
Dadurch, dass wir ein zufälliges Element aus einer Familie von
Funktionen wählen, können wir für beliebige Eingaben im Erwartungswert
effizient sein.
Wenn ich das ohne den Einsatz von Zufall erreichen will, ist das
deutlich schwieriger, bzw.
ich wüsste überhaupt kein Verfahren, dass das wirklich in konstanter
Zeit für beliebige Eingaben erreicht.
Das heißt, Zufall kann uns echt weiterbringen, wir werden noch weitere
Möglichkeiten dafür sehen und das ist eine allgemeine Technik, die man
kennen sollte als Informatiker, nämlich randomisierte Algorithmen und
Datenstrukturen.
Ah, da ist noch eine Frage.
Wie wird der Zufall konkret implementiert, wenn man zum Beispiel die
Java -Standardbibliothek verwendet?
Ich bin jetzt kein Java-Experte, ich vermute, dass das so ähnlich
funktioniert wie in C++.
Man benutzt dann normalerweise sogenannte Pseudo-Zufallsgeneratoren,
die kann man am Anfang mal auf den Anfangszustand setzen und danach
produzieren die eigentlich deterministisch Werte, allerdings mit Hilfe
von mathematischen Berechnungsvorschriften, die so viel Chaos
produzieren, dass es sich in der Praxis wie Zufall verhält.
Diese Zufallszahlengeneratoren werden dann meistens so getestet, dass
man eine große Menge von statistischen Tests drauf loslässt.
Zum Beispiel, man würfelt ganz viele Zufallszahlen zwischen 1 und 1
.000, guckt dann, wie lange das dauert, bis man alle Zahlen von 1 bis
1.000 mindestens einmal gesehen hat.
Da kann man ausrechnen mathematisch, wie lange das im Mittel dauert,
wenn man echten Zufall hat.
Und dann vergleicht man das mit dem, was man gemessen hat und den
statistischen Abweichungen, die man erwartet, wiederholt das ganz oft.
Und dann gibt es vielleicht noch 100 weitere Tests von dieser Art.
Man macht irgendwas, wo man weiß, wie es ausgehen soll und guckt, ist
das im Bereich des Erwarteten und wenn der Generator alle diese Tests
passiert, dann gilt der als gut.
Andere Möglichkeit ist, physikalischen Zufall zu verwenden, das ist
aber normalerweise aufwendiger und für Algorithmen eigentlich nicht
nötig.
Das macht man eher, wenn man Zufall für kryptografische Anwendungen
braucht.
Weil in dem kryptografischen Fall kann es halt sein, dass irgendein
Mathematiker auf diese Funktion guckt und sagt, wie kann ich die
invertieren und findet dann was und dann ist das komplette System
gebrochen.
Eine relativ neue Entwicklung ist, dass die Intel-Prozessoren seit der
letzten Generation einen Hardware-Zufallsgenerator haben, der, falls
die NSA nicht zu viel da reingebaut hat, auch kryptografisch sicher
sein sollte.
Und der auch sehr schnell ist und so weiter.
Aber den in algorithmischen Anwendungen zu verwenden, weiß ich nicht,
wie einfach das ist.
Das ist ein bisschen komisch gelöst.
Die haben halt diesen Hardware-Zufallsgenerator als einen separaten
Prozessor auf den Chip gepackt und dann muss jeder Core des Prozessors
mit diesem Ding wieder interagieren.
Und was dann passiert, wenn alle Cores mit maximaler Geschwindigkeit
auf dieses Ding zugreifen, ist mir nicht so klar.
Ob man dann wirklich noch echten Zufall kriegt oder ob die dann alle
die gleichen Daten kriegen oder ob dann das ganze System irgendwann
blockiert.
Da sind diese deterministischen Pseudo-Zufallszahlengeneratoren
irgendwie klarer zu handhaben, finde ich.
Beantwortet das die Frage?
Ah, genau, das ist eine super Frage.
Also was ich eben gesagt habe, gilt für Zufallsgeneratoren.
Und eigentlich sollte man ja hoffen, dass die Leute alle universelles
Hashing verwenden und dann eben am Anfang, wenn man so einen
Konstruktor baut, für diese Hash-Tabelle dann zumindest einmal so eine
Hash -Funktion ziehen, mit Hilfe dieses Zufallszahlengenerators und
danach halt diese Hash-Funktion verwenden.
Und dann vielleicht sogar noch adaptiv gucken, oh, bin ich jetzt in
einem der seltenen Fälle, wo die Hash-Funktion total schlecht ist.
Das kann ja vorkommen.
Und dann eine neue Hash-Funktion generieren.
Das wäre sozusagen die theoretische Sichtweise, wie man sozusagen eine
algorithmisch sichere Hash-Tabelle baut.
In der Praxis läuft das leider anders.
Wenn Sie eine Hash-Tabelle in Java generieren, vermutlich ist das so,
es gibt irgendeine Default-Hash-Funktion, die halt das System
automatisch generiert.
Und wenn Sie Glück haben, ist die Implementierung gut und funktioniert
eben in der Praxis meistens.
Und wenn Sie Pech haben, ist die nicht so gut.
Und dann steht irgendwo im Kleingedruckten, Sie hätten ja auch Ihre
eigene Hash-Funktion irgendwie als optionalen Parameter angeben
können.
Deshalb sind Sie immer selber schuld, wenn es nicht gut funktioniert.
Und da ist es dann auch so ähnlich.
Es gibt eben tatsächlich Hash-Funktionen, auf die die Leute ganz viele
statistische Tests losgelassen haben.
Und denen man einigermaßen vertrauen kann in der Praxis und die auch
einigermaßen effizient sind.
Aber auch die sind im Allgemeinen nicht universell in unserem Sinne.
Und meine Vermutung wäre aber, wenn man sowas wie diese Skalarprodukt
-Hash -Funktionen wirklich nehmen würde, wäre das genauso schnell wie
die Sachen, die da im Moment in der Praxis verwendet werden.
Und man hat echte Leistungsgarantien.
Aber das ist eben tatsächlich so.
Entweder macht es das System irgendwie per Default oder Sie müssen es
selber machen.
Und dann sollten Sie auch darüber Bescheid wissen, dass es da irgendwo
Libraries von Hash-Funktionen gibt, die ganz gut funktionieren.
Weitere Fragen dazu?
Achso, vielleicht noch ein praktischer Hinweis dazu.
In der Praxis wird man dann natürlich sagen, hier ist eine Hash
-Tabelle, die benutze ich und es geht gut mit Ihren Tests.
Vielleicht mit Ihren Anfangstests, die sowieso mit Zufallszahlen
arbeiten oder so.
Und dann haben Sie irgendwann reale Instanzen und das gilt dann nicht
mehr.
Und in den meisten Fällen geht es trotzdem gut.
Aber mein Rat ist, wenn Sie Hash-Tabellen verwenden und es irgendeinen
Zweifel gibt darüber, ob die vielleicht zu langsam sind, weil Sie
keine gute Hash-Funktion haben, machen Sie Profiling.
Gucken Sie, wo bleibt die Zeit in meinem Algorithmus und wenn dann
halt das anzeigt, aha, die Zeit bleibt in den Hash-Tabellen-Zugriffen,
dann gucken Sie da halt genauer hin.
Wir haben es da auch wirklich schon oft erlebt, dass die...
Manchmal ist es dann so, das liegt dann wirklich daran, dass die
Anwendung nichts anderes macht als Hash-Tabellen-Zugriffe.
Und die Hash-Funktion ist aber in Ordnung.
Dann ist es vielleicht trotzdem sinnvoll, mal zu gucken, sollte ich
jetzt auf Hashing mit Linear-Probing umschalten oder sowas.
Das hat bei uns schon öfter mal einen Faktor 2 oder 3 gebracht.
Das bringt uns zum Ende dieses Kapitels über Hashing.
Und nein, wir hören jetzt nicht auf, sondern ich denke, es ist früh
genug, noch mit dem nächsten Kapitel anzufangen über Sortieren.
Wer weiß, wer der Herr da ist?
Das ist Hermann Hollerith, klingt sehr deutsch, ist aber ein
Amerikaner, allerdings Sohn von deutschen Einwanderern.
Der hat Ende des 19.
Jahrhunderts diese Maschinen hier gebaut.
Und das erzähle ich, weil das da eine Sortiermaschine ist.
Und das ist kein exotisches Ding, sondern aus der Firma Hollerith
wurde dann irgendwann die Firma IBM.
Also das war der Startpunkt für eine der erfolgreichsten
Computerfirmen der Welt.
Und es ging darum, die Anwendung waren Volkszählungen.
Es ist wohl in der amerikanischen Verfassung sogar verankert, dass es
alle 5 oder 10 Jahre eine Volkszählung gibt.
Und der war daran beteiligt, der Herr Hollerith.
Und ich glaube, das war dann halt 1890 oder sowas.
Da hat dann die Auszählung länger gedauert als die Zeit bis zur
nächsten Volkszählung.
Weil die USA so stark gewachsen waren, dass das an seine Grenzen
stieß.
Und seine Antwort darauf war, wir brauchen Hardware-Unterstützung
dafür.
Der hat dann Lochkarten genommen, die hat er glaube ich auch nicht
selber erfunden, sondern die wurden vorher für programmierbare
Webstühle schon verwendet.
Sogar seit dem 18.
Jahrhundert schon in Frankreich.
Und er hat das angewendet auf diese Volkszählung.
Das heißt, die Antworten auf die Fragen wurden kodiert in Löcher in
einer Lochkarte.
Da hat er dann auch schon so Maschinen zum Beschreiben der Lochkarten,
ich nehme an, dass das hier auch sowas ist, gebaut.
Das war relativ einfach und lässt sich auch massiv parallelisieren.
Dann gibt es halt ein paar tausend Leute, die diese Lochkarten da
stanzen.
Dann hat man halt Stapel von diesen Lochkarten, 100 Millionen Stück
oder sowas, also das war damals schon Big Data.
Auch ohne echte Computer, das finde ich beeindruckend.
Und dann kann man so einen Stapel von Lochkarten nehmen und in diese
Zählmaschine stopfen.
Und dann zum Beispiel das Ding so programmieren, dass man fragt, wie
viele Frauen gibt es in den USA oder sowas.
Aber manchmal sind die Fragen komplexer, man möchte wissen, wie viele
US -Bürger im Alter von 18 bis 60 Jahre gibt es, wenn die
arbeitsfähige Bevölkerung.
Dann braucht man eine Range-Query, man will dann die Lochkarten
ausfiltern, bei denen das Alter im richtigen Bereich ist.
Dafür sortiert man am besten erstmal die Lochkarten nach Alter und
nimmt dann halt die passenden raus und stopft die dann in die
Zählmaschine.
Das heißt, sortieren ist eine ganz zentrale Funktion für diese,
eigentlich war das schon so etwas wie eine relationale Datenbank mit
Hardware, mechanischer Hardware implementiert.
Das heißt, da war schon ein bisschen Elektrik dabei, da waren so
Aluminiumbürsten, wenn die durch das Loch durchgingen, dann wurde ein
Kontakt gemacht.
Also es war elektromechanisch, diese Hardware.
Und wir werden dann tatsächlich als letzten Sortieralgorithmus
RADIXORT kennenlernen und das war der Algorithmus, der hier angewendet
wurde.
Mal gucken wir uns aber erstmal ganz andere Algorithmen an, die
vielleicht auch ein bisschen breiter anwendbar sind.
Fragen zu diesen Maschinen oder zu Herrn Hollerith?
Also formal, wir haben wieder eine Folge von Elementen, das kennen wir
jetzt schon, Folgen, Elemente, Schlüssel haben die.
Wir suchen die Folge S, das ist Eingabe, N Elemente, wir suchen die
Folge S' und wieder N Elementen mit zwei Eigenschaften.
S' ist eine Permutation von S und die Ausgabe ist sortiert.
Die genaue mathematische Definition davon ist so ein bisschen haarig.
Also im Wesentlichen ist das halt eine totale Ordnung bezüglich der
Schlüssel, die man da haben will.
Ich habe da einen anderen Begriff gewählt, lineare Ordnung, aber meine
Kollegen diskutieren ständig mit mir, ob das der richtige Begriff ist.
Ich weiß es jetzt auch nicht mehr.
Die Komplikation stammt daher, dass man zum Teil unterschiedliche
Schlüssel hat, die aber bezüglich dieser Ordnung als Äquivalent
gelten.
Zum Beispiel im Deutschen ist es so, da gibt es verschiedene
Sortierordnungen für Namen oder für Zeichenketten.
In einigen davon wird das U mit dem Ü identifiziert und in anderen
wird das Ü in den UE übersetzt und dann im Endeffekt mit dem UE
identifiziert.
Das heißt, Sie haben zwei verschiedene Schlüssel, Übung und UEbung,
die aber in dieser Ordnung gleich sind.
Und wo Sie dann nicht festlegen wollen, in welcher Reihenfolge die
kommen und egal in welcher Reihenfolge Sie das schreiben, ist es
beides korrekt oder solche Sachen wollen Sie manchmal haben.
Aber das ist jetzt nicht so wichtig.
Nehmen Sie mal an, es ist eine totale Ordnung.
Also beliebige Schlüssel sind miteinander vergleichbar und es kommt
immer raus, kleiner, gleich oder größer und gleich heißt, dass sie
auch wirklich identisch sind oder zumindest in irgendeiner Form
Äquivalent.
Und dann kann es trotzdem natürlich noch sein, dass es mehrere
Elemente gibt, die den genau gleichen Schlüssel haben, aber
unterschiedliche Zusatzinformationen daran hängen.
Fragen zu der Definition von Sortieren.
Ich glaube, Sie haben das in Grundbegriffe auch grob schon
kennengelernt.
Anwendungsbeispiele für Sortieren.
Ganz allgemein ein häufiger Vorverarbeitungsschritt.
Warum brauche ich den?
Na ja, zum Beispiel, um etwas suchen zu können.
Wer von Ihnen hat zu Hause noch ein gedrucktes Telefonbuch?
Ah, die meisten, ja.
Ich habe das zu Hause nicht mehr, aber meine Eltern natürlich noch
irgendwo.
Wer benutzt es noch?
Wer outet sich?
Manchmal ist es ganz nützlich.
Ich finde, das ist ein super schönes Beispiel dafür, wieso man
Sortieren braucht.
Stellen Sie sich vor, in diesem Telefonbuch wären alle Namen und
Telefonnummern aufgeführt, aber in der Reihenfolge, in der die Leute
ihren Vertrag abschließen, dann haben Sie da nichts von.
Dann müssen Sie ja komplett durchsuchen, finden Sie nichts.
Aber so können Sie in dem Telefonbuch das eingrenzen.
Das Verfahren nennt man binäre Suche.
Ich glaube, das kennen Sie auch schon aus Grundbegriffe.
Und dann eben zeitlogarithmisch in der Anzahl Adressen im Telefonbuch
die richtige Adresse finden.
Oder eben herausfinden, dass es den Eintrag, den Sie suchen, nicht
gibt.
Gruppieren.
Man möchte irgendwie gleichartige Objekte zusammenbringen, weil man
sie zusammenverarbeiten möchte.
Da kann man dann darüber nachdenken, ob man das besser über Hashing
machen kann, aber oft macht man es über Sortieren aus verschiedenen
Gründen.
Im Buch gibt es eine ganze Reihe Beispiele dafür.
Diese Suche werden wir insbesondere wiederfinden in dem Kapitel über
Suchbäume bzw.
sortierte Listen.
Und deren Aufbau ist ein Sortierproblem.
Dann einen der Algorithmen zur Berechnung von minimalen Spannbäumen,
den von Kruskal, der sortiert die Kanten eines Graphen nach
aufsteigendem Gewicht.
Und für die Korrektheit des Algorithmus ist es ganz wichtig, dass man
die leichtesten Kanten zuerst anschaut.
Dann werden wir Intervallgraphen kennenlernen als eine Möglichkeit,
sehr dichte Graphen, sehr kompakt zu repräsentieren und die man dann
auch direkt in dieser kompakten Form verarbeiten kann.
Und dafür ist Sortieren immer ganz wichtig.
Wir werden ein Optimierungsproblem kennenlernen, das Rucksackproblem.
Bei dem man Gegenstände in einen Rucksack packt, sodass man eine
bestimmte Profitfunktion maximiert.
Und da wird sich dann herausstellen, dass es eine ganz gute Strategie
ist, die Kandidatengegenstände in einer bestimmten vorgegebenen
Reihenfolge auszuprobieren.
Ein anderes Optimierungsproblem ist das Scheduling von Jobs auf
identische Maschinen.
Da werden wir sehen, dass es eine gute Strategie ist, die
aufwendigsten Probleme zuerst einzuplanen.
Auch wieder in sortierter Reihenfolge.
Und wenn wir dazu kommen, im Buch steht es zumindest
Sekundärspeicheralgorithmen.
Also wenn die Daten auf der Festplatte stehen,
kann man bestimmte Operationen am besten durchführen, wenn man
sortiert.
Zum Beispiel eine der wichtigsten Operationen in relationalen
Datenbanken, die Join-Operation, erfordert sortieren, wenn die
zusammengefügten Listenrelationen sehr groß sind.
Und es gibt eine ganze Reihe Verwandterprobleme, wo man so ähnliche
Dinge wie sortieren tut.
Und wo es eine gute Idee ist, zu wissen, wie gute Sortieralgorithmen
aussehen.
Das ist zum Beispiel Transposition dünnbesetzter Matrizen, Aufbau
eines sogenannten invertierten Indexes für Volltextsuche oder die
Konversion zwischen verschiedenen Repräsentationen von Graphen.
Also mit anderen Worten, Sortieren ist eine der fundamentalsten
Operationen der Informatik.
Und effiziente Algorithmen dafür sind oft wichtig, zu einer insgesamt
effizienten Anwendung zu kommen.
Fragen dazu?
Dieses Kapitel ist so aufgebaut, wir werden uns zuerst ganz einfache
Algorithmen angucken, die für kleine Eingaben gut geeignet sind und
die wir dann zum Teil als Basisfall verwenden können, für Algorithmen,
die größere Datenmengen sortieren und die oft rekursiv sind.
Wir werden dann einen solchen rekursiven Algorithmus kennenlernen,
Merge Sort, der basiert auf dem Zusammenmischen von sortierten
Teilobjekten.
Dann schauen wir uns eine untere Schranke an, also wir werden zeigen,
dass unter bestimmten Annahmen, Sortieren nicht schneller geht als
eine bestimmte obere Schranke, nämlich dieses Merge Sort ist in
gewisser Weise nicht zu schlagen.
Zumindest was die Anzahl Vergleichsoperationen zwischen Schlüsseln
angeht, das werden wir beweisen.
Das gibt uns ein erstes Beispiel für untere Schranken in der
Algorithmik, eine theoretisch ganz spannende Geschichte.
Wie beweisen wir, dass man etwas nicht besser lösen kann als?
Da muss ich eigentlich argumentieren über alle möglichen Algorithmen,
die ein Problem lösen und das ist halt ganz schwierig, weil es gibt
ganz viele mögliche Algorithmen.
Dann lernen wir einen weiteren effizienten Sortieralgorithmus kennen,
der in der Praxis viel verwendet wird, Quicksort.
Und auf Basis von diesem Quicksort-Algorithmus werden wir ein anderes
Problem effizient lösen können, das ein bisschen einfacher ist als
Sortieren, nämlich Auswahl.
Zum Beispiel, wenn Sie den Median einer Menge von Objekten auswählen
wollen, wäre es ganz einfach, erst zu sortieren und dann das mittlere
Element zu wählen, aber das geht besser.
Und dann werden wir die untere Schranke schlagen.
Untere Schranken sind nämlich nicht dazu da, uns zu zeigen, was
unmöglich ist, sondern uns zu zeigen, wie wir uns drum herumwinden
können.
Das ist meine These.
Und spannenderweise ist dieses tolle Drumherumwind-Verfahren gerade
das, das der Herr Hollerith verwendet hat.
Da schließt sich dann der Kreis.
So, aber dann fangen wir erstmal mit den einfachen Algorithmen an.
Sortieren durch Einfügen.
Wieder ein superschönes Beispiel dafür, wie Invarianten eigentlich
schon den ganzen Algorithmus erklären.
Das kann man am besten an dem Bild erklären.
Unsere Invariante sagt, alles was rot ist, ist sortiert.
Das ist eine Schleifen-Invariante.
Die Strategie ist, mach den roten Teil immer größer.
Na ja, der Anfang ist ganz einfach.
Das erste Element eines Arrays ist für sich genommen immer eine
sortierte Folge.
Deshalb fängt diese Schleife auch bei 2 an.
Ich weiß als Voraussetzung, die Elemente 1 bis i-1 sind bereits
sortiert.
Und jetzt habe ich immer dieses grüne Element, das würde ich gerne
hinzunehmen zu meiner Invariante.
Oder zu meinem sortierten Präfix des Arrays.
Und was muss ich dafür machen?
Na ja, ich muss die richtige Position für das grüne Objekt finden und
es dahin schieben.
Ganz einfach.
Also schiebe ai auf die richtige Stelle.
Gucken wir uns das mal am Beispiel an.
Die Eingabe 4711.
Am Anfang sage ich, okay, der Präfix 4 ist sortiert.
47, oh ich habe Glück, ist auch sortiert.
471 ist nicht sortiert.
Aber wenn ich die 1 an den Anfang schiebe, ist das okay?
1471 ist nicht sortiert, aber ich schiebe das hier hin.
Und jetzt gilt plötzlich meine Invariante für die ganze Eingabe und
ich bin fertig.
Fragen dazu?
Ganz einfach.
Hier ist jetzt Pseudocode dafür.
Und der ist jetzt auch wieder zwei Zeilen länger als der
allereinfachste denkbare Pseudocode dafür.
Demonstriert aber wieder mal eine Technik, die wir schon kennengelernt
haben, nämlich Wächter-Elemente.
Fangen wir einfach mal an.
Also in Search and Sort Eingabe ist ein Array.
Ich nummeriere von 1 bis n von Elementen.
Ich fange bei 2 an, weil der bis 1 ist schon alles sortiert.
Die Invariante sagt alles bis i-1 ist schon sortiert.
Jetzt speichere ich mir das i-te Element, das ich positionieren will,
in einer eigenen Variable e.
So und jetzt kommt eine Fallunterscheidung.
Wenn e das kleinste Element ist, also kleiner als a1, dann muss ich
auch nichts weiter vergleichen.
Dann schiebe ich einfach alles von 1 bis i-1 um eine Position nach
rechts.
Das steht hier.
Das geht am einfachsten über so eine Schleife, die rückwärts zählt.
Ich gehe rückwärts, schiebe immer nach rechts, dann habe ich immer ein
Loch, wo ich es hinschieben kann.
Überlegen Sie sich, dass wenn ich von links schieben würde, hätte ich
ein Problem, weil ich immer nicht weiß, wo ich die Sachen hinschieben
will.
Und ich möchte jetzt nicht ein temporäres Array haben, wo ich schieben
will.
Also ich schiebe immer rüber.
Wohlgemerkt, der allererste Schritt hier vorne ist schon ganz
interessant.
Vor j gleich i, aj gleich aj minus 1.
Und ich will gerade das j-Element positionieren.
Ich überschreibe das j-Element und das darf ich mir nur leisten, weil
ich es vorher in Sicherheit gebracht habe und in e zusätzlich nochmal
gespeichert habe.
Und ganz zum Schluss speichere ich das e an der ersten Stelle.
Weiterer Trick hier, viele Lehrbücher schreiben einfache
Sortieralgorithmen immer in Termen von Swap-Operationen, man
vertauscht Objekte.
Aber wenn Sie sich das in Maschinencode angucken, sind das dann
dreimal so viele Befehle wie einfach so eine Zuweisung pro
Schleifendurchlauf, wie Sie das hier machen.
Das merkt man dann schon ein bisschen in der Laufzeit.
Okay, also das war dieser Spezialfall, e ist das Minimum.
Sonst laufe ich auch wieder von rechts nach links durch das Array,
verschiebe immer nach rechts um 1 und höre aber auf, sobald ich ein
Element gefunden habe, das größer ist als mein e.
Und der Trick ist halt, dadurch dass ich diese Fallunterscheidung hier
treffe, weiß ich, wenn e größer als a1 ist, dann muss diese
Abbruchbedingung irgendwann zutreffen.
Und insofern wirkt das Element a1 hier als Wächterelement.
Ich muss nicht explizit bei jedem Schleifendurchlauf zusätzlich noch
abtesten, oder ist vielleicht jetzt j gleich 0 und ich muss aufhören.
Dann müsste ich in jedem Durchlauf einen zusätzlichen Test machen,
mein Programm wird etwas langsamer und es könnten vielleicht auch ein
paar andere Dinge schief gehen.
Also diese beiden Schleifen machen ungefähr das gleiche, haben nur
eine andere Abbruchbedingung.
Und das a1 wirkt halt als Wächterelement.
Gibt es dazu Fragen?
Analyse.
Naja, das ist kein besonders schneller Algorithmus.
Stellen wir uns mal vor, die Eingabe ist absteigend sortiert.
Dann muss ich in jeder Iteration komplett hier durchlaufen.
Also in der i-ten Iteration brauche ich i Schritte.
Wenn ich das summiere von 2 bis n, kriege ich, naja von 1 bis n ist n
mal n plus 1 halbe, dann ist von 2 bis n ist 1 weniger.
Dann habe ich so viel Schleifendurchlauf, das ist Theta n Quadrat.
Das ist ziemlich langsam.
Gerade in so Datenbankanwendungen will man oft große Datenbanken
sortieren.
Ich denke auch Herr Hollerith hätte ein Problem damit gehabt, 100
Millionen Einträge in quadratischer Zeit zu sortieren.
Ich meine, das Schöne ist, diese Sortieralgorithmen können Sie sich
auch wirklich mit diesen Lochkarten jetzt vorstellen.
Oder leider müssen wir das auch manchmal mit Klausuren machen.
Sortieren wir ja je nachdem nach Namen oder Matrikelnummern oder nach
Punktzahl bei der Korrektur.
Und dann wäre ein Searching zuurteilt, Sie haben jetzt so 400
Klausuren da stehen, gucken, aha, hier ist jetzt die Punktzahl.
Und jetzt blättern Sie so lange, bis Sie die Klausur mit der richtigen
Punktzahl gefunden haben, schieben das da rein.
Das dauert ziemlich lange.
Das können wir uns für fast alle Sortieralgorithmen hier auch dann
überlegen, ob das von Hand praktikabel wäre oder nicht.
Und dieses Sortieren durch Einfügen würde man vermutlich machen, wenn
man 10 Klausuren hat.
Dann kann man das so schnell machen und alles andere wäre ohnehin zu
aufwendig, zu kompliziert, sage ich mal.
So, der beste Fall von Sortieren durch Einfügen ist eigentlich
ziemlich gut.
Es könnte ja sein, wenn es zum Beispiel aufsteigend sortiert ist,
meine Eingabe, dann muss ich immer nur ein Element nach links gucken
und sehe, aha, es ist größer, prima, fertig.
Dann habe ich insgesamt I gleich 2 bis N, O von 1, O von N-Zeit,
Linearzeit.
Da gibt es einen ganzen Forschungsbereich drüber, der sich diesem
Phänomen widmet.
Offenbar ist es so, die Laufzeit eines Sortieralgorithmus kann
abhängig sein von der Eingabe.
Schwankt hier zwischen linear, wir werden sehen, das ist halt besser
als der Worst Case zumindest von auch sehr guten Sortieralgorithmen,
bis zu quadratisch, was katastrophal schlecht ist.
Deshalb gibt es Leute, die sich adaptive Sortieralgorithmen anschauen.
Man möchte nicht nur, dass ein Algorithmus im Worst Case gut ist,
sondern auch, dass er in einfachen Fällen schneller läuft.
Und da kann man richtig viel Theorie drüber treiben und zum Teil ist
das auch praxisrelevant.
Und hier hätten wir ein erstes einfaches Beispiel für adaptives
Sortieren.
Fragen dazu?
Gleichster Fall?
Bester Fall?
Wir haben noch drei Minuten, genau, Sortieren durch Mischen braucht
ein bisschen länger, also hören wir hier auf.
Vielen Dank.