So, dann herzlich willkommen zur vierten Übung.
Unser Professor Sanders ist heute nicht da.
Der ist in Boston auf einer Konferenz.
Deswegen gibt es heute 90 Minuten Übung und ein bisschen Wiederholung
und ein bisschen Vorlesung, genau.
Okay, also als erstes nochmal eine Ankündigung.
Wir haben schon in der ersten Vorlesungswoche angekündigt, dass es
eine Mitsemesterklausur gibt, wo ihr alle die Möglichkeit habt, euer
Wissen unter Beweis zu stellen und uns zu zeigen, wie gut ihr schon
seid.
Der Termin für diese Mitsemesterklausur ist Montag, der 3.
Juni 15.45 Uhr und das wird statt der Vorlesung stattfinden.
Und zwar genau an dieser Stelle.
Also genau hier im Audimax werden wir diese Mitsemesterklausur
schreiben und das wird ähnlich voll sein, eventuell sogar noch ein
bisschen voller.
Und dann werden da halt ein Haufen Übungsaufgaben gestellt und dann
gibt es dafür nachher Punkte.
Aber wie diese Punkte vergeben werden, das haben wir ja schon gesagt.
Dann machen wir den Einlass um 15.35 Uhr und beginnen die Klausur um
15.45 Uhr.
Und das ist nicht böse gemeint, aber wir lassen Nachzügler auf gar
keinen Fall mehr rein.
Also wenn ihr nach 15.45 Uhr da seid, kommt ihr halt nicht mehr rein.
Genau.
Dann ist es so, dass wie auch in der Hauptklausur nachher, wenn ich
richtig informiert bin, dürft ihr einen einseitig beschriebenen DIN A4
-Zettel benutzen.
Könnt ihr alles draufschreiben, was ihr möchtet.
Und ja, also ich denke, das sollte euch dann helfen, die Aufgaben auch
zu bearbeiten.
Ganz wichtig ist, dass ihr eure Tutoriumsnummer im Kopf habt, weil
ohne Tutoriumsnummer können wir euch dann leider nicht zuordnen und in
dem Fall gibt es dann halt auch keine Punkte.
Das heißt, bevor ihr zur Midsemesterklausur kommt, schaut euch nochmal
an, in welchem Tutorium ihr seid, also insbesondere die Nummer.
Genau.
Gut, also wir machen heute einen Haufen abgefahrener Datenstrukturen
am Anfang.
Dann gehen wir zurück oder machen wir weiter mit Sortieren aus der
Vorlesung.
Und der Timo hat heute was dabei, was ich selber nicht vorher sehen
durfte.
Also ich denke, das wird ganz interessant.
Mal gucken, was es ist.
Genau, also das Erste, was wir uns anschauen, sind unbounded
Hashtables.
Wir haben ja in der Vorlesung und in der Übung schon gesehen, was
unbounded Arrays sind.
Also das ist eine Datenstruktur, die man verwendet, um Elemente zu
speichern.
Und zwar weiß man vorher nicht, wie viele das sind.
Und bei diesen unbounded Arrays hat man diese Eigenschaft, dass jede
Operation in amortisiert konstanter Zeit abläuft.
Was wir in der Vorlesung schon gelernt haben, ist, was ist eine
Hashtabelle?
Also das Ziel ist im Wesentlichen, eine Schlüsselmenge auf ein
kleineres Intervall abzubilden.
Also eine ziemlich große Schlüsselmenge auf ein kleineres Intervall
abzubilden.
Und in der Vorlesung ist es dann so, dass man die Größe oder die
Anzahl der Elemente, die man in diese Hashtabelle einfügt, dass man
die kennt und damit dann die Analyse macht.
Also man wählt die Größe der Hashtabelle so, dass die Anzahl der
Kollisionen für ein Schlüsselelement in O von 1 ist.
Und jetzt haben wir aber das Problem, dass wir in der Praxis gar nicht
wissen, wie viele Elemente wir in einer Hashtabelle einfügen wollen.
Also insbesondere wenn ich zum Beispiel, oder ich persönlich verwende
zum Beispiel in C++ häufig die Unordered Map von den Technical Report
1 oder von C++11.
Und dort ist es ja so, dass man in der Regel einfach von vornherein
gar keine Größe für diese Hashtabelle angibt.
Sondern man verwendet die einfach, benutzt die als Blackbox und ist
mit den Eigenschaften erstmal zufrieden.
Und genau, also das nochmal richtig klarzustellen, wir wissen in der
Praxis nicht, wie viele Elemente wir in diese Hashtabelle einfügen
wollen.
Wir wollen aber die Leistungsgarantien, die uns diese Hashtabellen
geben, in der Praxis immer noch haben.
Also wir wollen immer noch konstant viele Kollisionen für ein
Schlüsselelement haben.
Jetzt ist die Frage als erstes, die man sich stellt, was passiert,
wenn so eine Hashtabelle zu voll wird.
Also wenn ich Hashing mit Linear Probing mache, dann kann ich maximal
die Anzahl der spezifizierten Elemente im Vorhinein speichern.
Das heißt, wenn ich zu viele Elemente versuche, in diese Hashtabelle
einzufügen, dann läuft die einfach über.
Wenn ich Hashing mit verketteten Listen mache, dann heißt das ja, dass
die Elemente immer an der Schlüsselposition in diese verketteten
Listen hineingefügt werden.
Und was dann passiert ist, dass diese Find-Operation, die ja durch
diese verkettete Liste in dieser Hashtabelle laufen muss, langsamer
wird.
Also die Lösung, die man jetzt macht, ist ganz ähnlich zu diesen
Unbounded Arrays, die wir in der Vorlesung hatten und auch in der
Übung.
Wir vergrößern und verkleinern unsere Hashtabelle einfach dynamisch.
Also hier steht jetzt, wie man unsere Unbounded Hashtables mit
verketteten Listen implementiert und insbesondere auch, wie man die
Operation modifiziert.
Also die Find-Operation ist unverändert.
Wenn man Hashing mit verketteten Listen macht, berechnet man den
Hashtwert von dem Schlüsselelement und sucht das dann in der
entsprechenden doppeltverketteten Liste oder einfachverketteten Liste
in dieser doppeltverketteten Liste.
Wenn man jetzt einen Insert macht, dann ist es wie bei den Unbounded
Arrays, wenn mein Array Anzahl Slots Elemente hat und füge alle
Elemente in die neue Hashtabelle, also die doppelte Größe hat, ein.
Und muss da aber eine neue Hashtabelle wählen, eine neue Hash
-Funktion, weil sich die Größe der Hashtabelle ja geändert hat.
Das Remove funktioniert auch ähnlich.
Ich halbiere die Größe von der Hashtabelle, wenn einfach nur noch ein
Viertel der Elemente in der Hashtabelle sind.
Genau,
das habe ich eben schon erwähnt.
Diese Hash-Funktion, die man dann wählt, die neue, die muss dann zur
entsprechenden Tabelle passen.
Das heißt insbesondere zum Beispiel die Modul-Operation am Ende und
auf den Hashtabellen Slots streuen.
Also wenn ich jetzt einfach die alte Hash-Funktion weiterverwenden
würde, würde ich ja nichts anderes machen, als nur die erste Hälfte
von meiner neuen Hashtabelle verwenden und die ganze Analyse, das
würde alles kaputt gehen.
Also das würde uns gar nichts bringen, die Hashtabelle in der Größe zu
verändern.
Genau, das habe ich ja eben schon gesagt.
Also was man macht, wenn ich die Größe verändert habe, wähle ich
einfach eine neue Hash-Funktion und alle Elemente in der alten
Hashtabelle werden neu in diese neue Hashtabelle eingefügt.
Mithilfe dieser neuen Hash-Funktion.
So, also jetzt wollen wir natürlich uns die Laufzeit nochmal angucken.
Die Operation Insert, Find und Remove ohne das Rehash, also ohne diese
neue Operation, die ich gerade eingefügt habe, die laufen unverändert
in erwartet OV1.
Die Analyse geht komplett genauso, weil solange ich keinen Rehash
ausführe, habe ich einfach eine Hashtabelle der Größe M.
Wenn ich jetzt das Rehash ausführe, dann dauert das für diese eine
Operation erstmal linear, also habe ich eine lineare Laufzeit.
Aber das ist amortisiert genau wieder in konstanter Zeit, weil ich
genauso wie bei den Unbounded Arrays argumentieren kann, dass sich
diese Rehash-Operation amortisiert.
Also bevor ich einen Rehash ausführe, muss ich ja linear viele
Elemente eingefügt haben.
Und dann kann ich einfach wieder pro Operation sparen mit unserer
Bankkonto -Methode und dann kriege ich am Ende einfach wieder
amortisiert konstante Zeit.
Kann man sich mal überlegen, wie das technisch genau geht.
Also ist vielleicht auch eine gute Übungsaufgabe, das mal
durchzurechnen.
Genau, da gibt es noch ein paar technische Details für unser neues
Hashing hier.
Was man ja eigentlich möchte, ist sowas wie unsere Hasht-Funktion,
also ganz triviale Hasht-Funktion.
Ich nehme einfach mein Element X, was eine natürliche Zahl ist, und
rechne die Module der Tabellengröße, sodass ich irgendwo einen Platz
in der Hashtabelle bekomme.
Wenn ich jetzt aber eine Tabellengröße der Größe 2 auf K habe, dann
habe ich das Problem, dass ich immer nur die K-niedrigsten Bits
anschaue.
Und insbesondere heißt das, dass ich wahrscheinlich relativ viele
Kollisionen dann auch bekomme.
Was man lieber machen sollte, ist die Tabellengröße als Primzahl
wählen, und zwar möglichst weit von der Zweierpotenz, und dann sieht
die ganze Sache schon ein bisschen anders aus.
Also bei der Größenänderung selbst wählt man dann einfach anstatt 2
auf K die nächstgrößere Primzahl, die größer als 2 auf K ist, und dann
ist man glücklich.
Die Analyse ist dann ein bisschen... ich glaube nicht, dass das dann
auch stimmt, aber...
So, hier sehen wir mal ein Beispiel.
Also ich habe jetzt Elemente 22, 42, 9, 25, 18 und 96.
Und ich habe jetzt auf der linken Seite die Elemente 25, 42, 22, 18
und 9 in der Reihenfolge hier oben eingefügt.
Und zwar mit der Hash-Funktion h1 von x ist gleich x modulo 5, das ist
nämlich gerade diese Listenlänge hier.
Und jetzt will ich eigentlich ja noch die 96 einfügen, aber in meiner
anbauenden Hashtable passt die nicht mehr rein.
Also ich habe jetzt... die Hashtabelle hier ist voll, die hat genügend
Elemente.
Und jetzt schnappt man sich die nächste, also jetzt vergrößert man
diese Tabelle entsprechend dem Verfahren, was ich gerade vorgestellt
habe, und hasht die mit einer neuen Hash-Funktion in diese neue
Hashtabelle ein.
Und jetzt ist hier wieder schön viel Platz und meine Operation, also
die Analyse, die ich durchgeführt habe, das funktioniert alles wieder
wunderbar.
Okay.
Gibt es Fragen dazu?
Okay.
Gut, das nächste, was wir uns anschauen, ist nochmal Universalität von
Hash -Funktionen.
Genau, also wir hatten in der Vorlesung den Satz, dass für jeden
Schlüssel k die erwartete Anzahl kollidierender Elemente in O von 1,
falls die Anzahl Elemente gleich in O von Anzahl Slots ist.
Also bevor ich jetzt weitermache, ich versuche jetzt nochmal zu
motivieren, wozu wir universelles Hashing überhaupt gebrauchen können,
warum das wichtig ist, und dann schnappe ich mir nochmal eine Familie
von universellen Hash-Funktionen und zeige, dass die universell ist.
Um diesen Satz hier nochmal zu verstehen, muss man als allererstes so
eine Menge M' definieren.
Das ist gerade die Menge der Elemente, die nicht den gleichen
Schlüssel haben wie k, also der Schlüssel, den ich mir gerade
anschaue.
Und dann definiere ich mir eine Zufallsvariable x, und zwar ist das
gerade die Anzahl der Elemente, die auf den gleichen Slot gehashed
werden.
Und warum ist das eine Zufallsvariable?
Naja, diese Hash-Funktion, die ich hier habe, die muss ich zufällig
wählen, und dann ist das genau eine Zufallsvariable.
Und jetzt sind wir genau an dem Erwartungswert für diese
Kollisionslänge interessiert.
Also wir wollen wissen, wie viele Elemente auf den gleichen Slot
gehashed werden.
Der Professor Sanders hat in der Vorlesung nichts anderes gemacht als
eine wunderbare 0,1 Zufallsvariable einzuführen, und zwar für jedes
dieser Elemente in meiner Menge M'.
Und diese Zufallsvariable ist 1, wenn wir eine Kollision haben, also
wenn die Hash-Funktion den gleichen Wert hat für dieses Element, wie
der Hash-Wert von dem Schlüssel, den wir uns gerade anschauen.
Und sonst ist das Ding 0.
Und jetzt wissen wir, der Erwartungswert ist ja nichts anderes als die
Anzahl der Elemente, die auf den gleichen Slot gehashed werden.
Also x ist nichts anderes als die Anzahl der Elemente, die auf den
gleichen Slot gehashed werden.
Und jetzt verwende ich einfach die Linearität von diesem
Erwartungswert hier.
Ich kann also die Summe vor den Erwartungswert ziehen.
Und dadurch, dass das eine 0,1 Zufallsvariable ist, ist dieser
Erwartungswert von meiner 0,1 Zufallsvariable gerade die
Wahrscheinlichkeit, dass die Zufallsvariable gleich 1 ist.
Okay, das ist jetzt aber unabhängig von diesem m', diese Summe.
Und dann kriege ich gerade hier einmal den Betrag von m', mal der
Wahrscheinlichkeit, dass meine 0,1 Zufallsvariable gleich 1 ist.
Okay, also jetzt haben wir hier schon mal ziemlich kompliziert
aussehen, wenn man sich den Verwandten zeigt.
Und sind ein ganzes Stück weiter, weil wir wissen jetzt, dass die
erwartete Anzahl von Kollisionen ist gerade die Anzahl der Elemente,
die einen anderen Schlüssel haben, mal die Wahrscheinlichkeit, dass
diese Zufallsvariable hier 1 ist.
Okay, und jetzt muss man sich fragen, wie viele Hash-Funktionen
liefern das denn eigentlich?
Also wie viele Hash-Funktionen liefern diese Eigenschaft hier, dass
ich eine Kollision habe?
Also erstmal, die Menge der Hash-Funktionen ist nichts anderes als
eine Abbildung von der Anzahl der möglichen Schlüssel auf die Slots.
Und jetzt kann ich mir für eine beliebige Hash-Funktion, also für
einen beliebigen Schlüssel, kann ich mir jetzt beliebig einen Slot
aussuchen.
Und komme dann darauf, dass es insgesamt M hoch Anzahl Schlüssel Hash
-Funktionen insgesamt gibt.
Und auf der anderen Seite, wenn ich jetzt diesen Wert hier schon
festlege, dann gibt es nur noch M hoch Betrag Ki-1 Hash-Funktionen.
Und dann komme ich darauf, dass diese Wahrscheinlichkeit, die ich hier
habe, gerade der Betrag von M' ist, mal 1 durch M.
Und das ist O von 1, weil wir vorher diese Annahme gemacht haben, dass
Betrag M gleich O von M ist.
Der springende Punkt ist, dass diese Hash-Funktion, also der Ki selber
ist fest, aber die Hash-Funktion wurde zufällig aus der Menge von
allen möglichen ausgewählt, also eine ziemlich große Menge, und nicht
die Hash-Funktion selber würfelt den Wert für jeden Schlüssel.
Und jetzt ist die Frage, wo kommt jetzt universelles Hashing ins
Spiel?
Also die einzige Eigenschaft, die wir gebraucht haben in diesem Beweis
hier, ist, dass die Wahrscheinlichkeit von dieser Zufallsvariable
gerade gleich 1 durch M ist.
Die Menge aller möglichen Hash-Funktionen, die ist ziemlich groß.
Das haben wir ja gerade nachgerechnet.
Da sind M hoch Betrag Ki drin.
Und universelles Hashing sagt jetzt, ich brauche gar nicht alle Hash
-Funktionen als mögliche Auswahl zu haben, sondern es reicht mir eine
kleinere, sodass diese Wahrscheinlichkeit hier gerade 1 durch M ist.
Und deswegen definiert man genau diese einfachen Hash-Funktionen so.
Also eine Teilmenge von
x ungleich y und einem zufällig gewählten h in dieser Familie gilt,
dass diese Wahrscheinlichkeit hier h von x gleich h von y, die Klammer
muss ein bisschen weiter nach vorne, ist gleich 1 durch M.
Und jetzt habe ich gerade schon argumentiert, dass dieses Theorem, was
ich hier verwendet habe, genauso für diese universellen Hash
-Funktionen gilt.
Fragen zu dieser Universalität?
Das ist eigentlich ziemlich spannend.
Also hier ein Beispiel für Universalität von Hash-Funktionen.
Das ist jetzt ein Beispiel, was Professor Sanders schon auf seinen
Folien hatte.
Und ich finde das Ding ziemlich interessant, sagen wir es mal so.
Also man hat als allererstes mal eine Matrix M, die nur Werte in 0 und
1 hat und die Dimension hat w mal k.
Und jetzt habe ich eine Schlüsselmenge, die durch k Bits repräsentiert
ist und ich will die mappen auf eine Anzahl Slots, die durch w Bits
repräsentiert ist.
Also die Anzahl Slots in meiner Hash-Tabelle ist gerade m gleich 2 auf
w.
Und die Arithmetik, die ich hier durchführe, das ist nichts anderes
als Matrix mal ein Vektor, die macht man Modulo 2.
Das heißt, man hat im Wesentlichen eine XOR-Berechnung, wenn man
addiert und eine Endberechnung, wenn man multipliziert.
Also hier sieht man mal ein Beispiel.
Ich habe jetzt hier eine Matrix, die in der ersten Zeile 1011 heißt
und in der zweiten Zeile 0111.
Und ein Vektor x, der definiert es als 1,001.
Und jetzt kann man sich anschauen, was ist denn m ausmultipliziert mit
x Modulo 2.
Gucken wir mal, was das für die erste Zeile zumindest ist.
Also ich habe hier 1 mal 1, 0 mal 0, 1 mal 0 und 1 mal 1.
Dann steht hier nichts anderes als 1 plus 1.
Das ist genau diese Zeile hier multipliziert mit diesem Vektor.
Und das ist 2.
Und Modulo 2 ist das aber wieder 0.
Deswegen steht hier an der ersten Stelle ein 0.
Und genauso kann man sich das für diese zweite Stelle überlegen.
So, und jetzt haben wir dieses Beispiel natürlich dabei, weil wir
zeigen wollen, dass diese Familie, also wenn ich jetzt eine zufällige
Matrix hier oben wähle, m, wir wollen zeigen, dass diese Familie
gerade universell ist.
Und das wird jetzt ein bisschen technisch.
Genau, also wir müssen zeigen, dass für alle x ungleich y und hm gilt,
dass die Wahrscheinlichkeit für Kollision gerade gleich 1 durch m ist.
Für ein m beliebig gewählt aus allen möglichen.
So, was man also macht ist, man guckt sich mal an, okay, wann ist denn
h von x gleich h von y für einen x ungleich y?
Naja, das ist genau der Fall, wenn m x ist gleich m y.
Und was hier steht, ist im Wesentlichen w Zeilen, also das sind
Vektoren der Dimension w, und die sind gleich, wenn jede Komponente
von diesen Vektoren gleich ist.
Das heißt, für alle i in diesem 1 bis w muss gelten, dass die linke
Zeile, also der linke Eintrag, gleich der rechte Eintrag ist.
Dieses Plus hier ist unsere x-O-Operation.
So, jetzt sieht das aber immer noch relativ kompliziert aus.
Jetzt müssen wir uns überlegen, wie häufig passiert das, dass diese
Bedingung hier erfüllt ist.
Okay, also wir haben w Gleichungen, das sieht man hier, und wir haben
aber insgesamt wk-Variaben mij.
Diese mij sind genau diese Variaben, die wir jetzt wählen dürfen.
Im Wesentlichen haben wir also ein gleiches System, was unterbestimmt
ist, für x ungleich y.
Wenn x gleich y ist, haben wir ja gar nichts zu zeigen.
So, und das heißt jetzt im Wesentlichen, dass diese wk-w Vektoren
spannen den Lösungsraum auf, und ich kriege dann zwei auch wk-w
Lösungen, bis auf Konstanten.
Also ich habe natürlich viel mehr Lösungen, aber die Konstanten, die
interessieren uns jetzt hier nicht.
Und insgesamt habe ich aber zwei auch wk-mögliche Matrizen, weil ich
einfach jeden Eintrag in dieser Matrix M zufällig wählen kann.
Ich kann ihn ja zufällig als 0 oder 1 wählen, und dann habe ich zwei
auch wk-Möglichkeiten.
Das heißt, die Wahrscheinlichkeit, dass für ein zufällig gewähltes M,
dass diese hier kollidieren, ist nichts anderes als zwei auch wk-w
durch zwei auch wk.
Und das ist jetzt aber einfache Arithmetik, das ist nichts anderes als
zwei auch minus w, das ist eins durch zwei auch w.
Und dieses zwei auch w, das hatten wir, da steht's, hatten wir ja
gesagt, das ist gerade M.
Und damit sind wir fertig.
Ich habe jetzt gezeigt, dass die Wahrscheinlichkeit für eine Kollision
bei zufällig gewähltem M gerade gleich eins durch M ist.
Das heißt, wir haben eine universelle Familie von Hashfunktionen
gefunden, die nicht trivial ist.
Gibt es dazu noch Fragen?
Das ist ganz schön kompliziert, glaube ich, aber wenn man mal drüber
nachdenkt, dann ist das eigentlich schön.
Die nächste Sache, die auch wieder mit Hashing zu tun hat, sind
Blumenfiltern.
Also die Blumenfilter, das hat jetzt nichts mit Blumen zu tun, sondern
das hat der Herr Blum 1970 entwickelt, um Spellchecking zu machen.
Also damals gab es ja noch relativ kleine Maschinen mit wenig Speicher
und man konnte sich das quasi nicht leisten, das ganze Wörterbuch, was
man hat, in den Speicher von so einem Computer zu laden.
Und deswegen braucht man Blumenfilter.
Blumenfilter sind eine Datenstruktur, die folgende Operationen hat.
Also wir haben erstmal eine Insert-Funktion und eine Contains
-Funktion.
Diese Contains-Funktion sagt uns, ob ich das Element vorher schon mal
in unsere Hash-Funktion eingefügt habe.
Das heißt, für ein Element e sagt die Contains-Funktion ja, wenn e in
meiner Datenstruktur enthalten ist, und nein sonst.
Die erste Idee, die man jetzt hat, um diese Datenstruktur also ohne
das dritte Constraint hier zu implementieren, ist, man verwendet
erstmal Hashing.
Dann muss man Hash-Werte speichern oder ganz andere Objekte, aber man
verbraucht relativ viel Speicher.
Und diese Blumenfilter, die haben jetzt folgende Eigenschaft, und zwar
erlauben die einfach einen False Positive.
Das heißt, ich kann jetzt nachschauen, ist dieses Element in meiner
Datenstruktur enthalten?
Und ich kann eine Antwort ja bekommen, obwohl es nicht enthalten ist.
So.
Im Spellchecking heißt das insbesondere, ich kann alle Wörter in meine
Datenstruktur einfügen und kann dann, wenn ich ein Dokument parse,
gucken, okay, ist mein Wort, was ich mir gerade anschaue, in der
Datenstruktur enthalten?
Wenn ja, dann bin ich ja glücklich, weil dann ist es richtig
geschrieben.
Wenn nein, muss ich gucken, ob
ich es im wesentlichen Fehler übersehen könnte.
Das ist jetzt aber auch nicht wieder so tragisch.
Also, wenn die False Positive Rate klein genug ist, kann ich zum einen
das Ganze einfach wiederholt machen mit verschiedenen initialisierten
Datenstrukturen.
Und auf der anderen Seite, wenn ich da mal irgendwo einen kleinen
Fehler drin habe, naja, gut.
Genau, dann hatte ich eben schon gesagt, dass die erste die Hashing
ist, aber wir haben ja gesehen, okay, das Dictionary damals 1970, das
hat nicht in den Speicher gepasst.
Deswegen brauchen wir eine Datenstruktur, die weniger Speicher
verwendet.
Okay, also eine andere Anwendung, die diese Bloom-Filter haben, ist
zum Beispiel Webcalling.
Und dann sieht man, ich meine, das ganze Web passt auch nicht in den
Speicher von einem Computer.
Also da kann man die Dinger auch gebrauchen.
Okay, also wie funktionieren die?
Also erstmal wählen wir kHashFunktion und haben ein Array von mBits.
Also Bits heißt, ich brauche im Wesentlichen einen Bit, um dieses Bit
abzuspeichern.
So, das Insert funktioniert jetzt folgendermaßen, ich setze jetzt
überall, wo meine gewählten Hashing-Funktionen sozusagen hinmappen,
setze ich das Array auf 1.
Und wenn ich eine Container-Frage mache, dann gucke ich, sind die
Stellen, wo das Element hingemappt wird, alle 1?
Und wenn das der Fall ist, dann gebe ich Ja zurück und wenn das nicht
der Fall ist, dann gebe ich Nein zurück.
Okay, hier ist mal ein Beispiel mit 3 Hashing-Funktionen und 13
Elementen in meiner Tabelle.
Jetzt füge ich in diese Tabelle ein Element x ein, das setzt dann die
Werte 7, 9 und 3 auf 1.
Und wenn ich jetzt ein Contains mache, dann komme ich ja wieder an
diese gleichen Stellen und dann kriege ich ein Ja zurück.
Okay, damit bin ich ja erstmal zufrieden.
Und wenn ich jetzt ein Contains z mache, dann schauen die vielleicht
woanders nach, die werden vielleicht woanders hingemappt.
Und dann gebe ich ein Nein zurück.
Also ich habe ein z nicht eingefügt, also bin ich auch da mit einem
Nein zufrieden.
So.
Und jetzt kann das aber passieren, wenn ich genügend Elemente
eingefügt habe, dass wenn ich ein Element y überprüfe, dass das auf
die gleichen Elemente hier gehashed wird und dann kriege ich ein Ja
zurück, obwohl y nicht eingefügt wurde.
Okay.
Und, naja, also diese False Positives, die möchte man ja in der Praxis
eigentlich nicht haben.
Also möchte man diese False Positives nicht haben.
Und deswegen analysieren wir jetzt erstmal, wie viele False Positives
oder wie wahrscheinlich ist denn so ein False Positive überhaupt, in
Abhängigkeit von unseren Parametern k, n und m.
Also k ist die Anzahl der Hash-Funktionen, n die Anzahl der Elemente,
die ich einfüge und m die Größe der Tabelle, die ich angelegt habe.
So.
Also zur Erinnerung, das ist, glaube ich, ziemlich Anfang Analyse 1
aus dem letzten Semester, die Funktion e hoch x ist definiert als,
kann man definieren, als limes n gegen unendlich 1 plus x durch n.
Und jetzt machen wir als erstes mal die Annahme, dass die Hash
-Funktionen alle schön gleichmäßig und unabhängig über dieses Array,
was ich da gegeben habe, streuen.
So.
Dann ist die Wahrscheinlichkeit, dass ein Bit gleich 0 ist nach n
Einfügungen, nichts anderes als 1 minus 1 durch m hoch k mal n.
Also ich habe jetzt k Hash-Funktionen und n Elemente eingefügt und
muss mir überlegen, was ist die Wahrscheinlichkeit, dass ein Element
nicht auf 1 gesetzt wurde.
Mit Wahrscheinlichkeit 1 durch m wurde es auf 1 gesetzt, also muss ich
dieses 1 minus 1 durch m betrachten und mache das gerade k hoch m mal.
So.
Diese Gleichung hier ist jetzt aber nichts anderes als 1 minus 1 durch
m hoch m.
Also, genau, hoch k n durch m.
Und jetzt gucken wir uns nochmal die Gleichung hier oben an, e hoch x
ist der Grenzwert von 1 plus x durch n durch n.
Na ja, jetzt machen wir eine ziemlich starke Vereinfachung.
Wir sagen jetzt einfach, dieses 1 minus 1 durch m hoch m ist nichts
anderes als e hoch minus 1.
Und dann kommen wir auf diese Gleichung hier.
Und jetzt haben wir die Wahrscheinlichkeit für ein Bit gefunden.
Also die Wahrscheinlichkeit, dass ein Bit nach n Einfügungen gleich 0
ist, ist e hoch minus k n durch m.
Und dadurch, dass ich ja k-Bits überprüfen muss, kriege ich dann eine
Gesamtwahrscheinlichkeit von einem false positive von 1 minus p hoch
k.
Und das ist nichts anderes als 1 minus 1 durch k hoch n durch m hoch
k.
So.
Und jetzt bin ich als Algorithmedesigner in der guten Situation, dass
ich mir die Parameter wählen kann.
Also ich kann jetzt das m wählen, das n kann ich nicht wählen, weil,
gut, das ist halt gegeben durch die Anwendung.
Und ich kann das k wählen.
So, für den Moment lassen wir mal n und m einfach als Konstant.
Also wir sagen jetzt mal, wir haben n und m gewählt.
Jetzt ist die Frage, was ist eine gute Anzahl für die Anzahl Hash
-Funktionen?
Ähm, genau.
Also man sieht in dieser Gleichung schon, dass eine Hash-Funktion
irgendwie nicht so sinnvoll ist.
Und auf der anderen Seite jetzt n Hash-Funktionen zu verwenden, ist
auch nicht sinnvoll, weil dann ist das ganze Array nachher voller
Einsen.
Und ich kriege von der Datenstruktur immer eins zurück, also die
Contains -Operation liefert mir immer wahr zurück für jedes Element,
was ich nachfrage.
Also kann k gleich n auch nicht sinnvoll sein.
Weiß jemand, wie man für festes n und m eine gute Wahrscheinlichkeit
oder eine gute Anzahl k finden könnte?
Ivo?
Was willst du umdrehen?
Ja, genau.
Also man kann das nach k auflösen oder man könnte auch einfach
annehmen, dass das k des Kredits und ableiten nach k und dann 0
setzen.
Und dann kriegt man raus, das ist übrigens von Wikipedia hier, dass
ein guter Wert für k m durch n mal Logarithmus 2 ist.
Gut, dann schauen wir uns mal auf ein Beispiel an, wie hoch so eine
False -Positive-Rate sein kann.
Also in meinem Beispiel hier habe ich 100.000 Objekte und sage, ich
will eine Million Bits in meinem Blumenfilter haben.
Und die Gleichung, die ich vorher hatte, nämlich dieses m durch n mal
Logarithmus 2 oder natürlicher Logarithmus 2, liefert mir jetzt k
gleich 7.
Also was dabei rauskommt, ist natürlich eine gebrochene Zahl, aber die
runde ich dann einfach und dann komme ich gerade bei diesem k gleich 7
an.
Und für diesen Fall ist die Wahrscheinlichkeit für ein False-Positive
gerade gleich 1 Prozent, was ziemlich gering ist.
Und auf der anderen Seite, das ist nämlich genau dieses
Verkaufsargument von diesen Blumenfiltern.
Ich habe jetzt hier 1000 Bits und spare mir das Speichern von ganzen
Strings, Webseiten oder Hashwerten oder sonst irgendwas.
Und bin damit viel besser bedient, als wenn ich eine Hash-Tabelle oder
sowas benutzen würde.
Und dann gibt es hier noch einen Tipp.
Also was wir gemacht haben auf der vorherigen Folie, ist, wir haben
angenommen, dass diese ganzen Hash-Funktionen alle unabhängig sind.
Das ist natürlich in der Praxis nicht richtig.
Und deswegen haben Bose et al.
ein Paper daraus gemacht und das genau analysiert.
Also on the False-Positive Rate of Blumenfilters haben die sich sehr,
sehr genau angeschaut, wie hoch diese Wahrscheinlichkeit für einen
False -Positive wirklich ist.
Gut, gibt es dazu Fragen?
Okay.
Gut, das Letzte, was ich jetzt noch vorstelle, bevor der Timo anfängt
zu sortieren, ist De-Amortisierung.
Also nochmal unbounded Arrays.
Wir haben ja gesehen, dass der Zugriff auf so ein unbounded Array in O
von 1 ist.
Pushback geht amortisiert in O von 1, Popback geht amortisiert auch in
O von 1.
Allerdings ist der Worst-Case Omega von N für Pushback und Popback
nämlich genau dann, wenn ich mein Array einkopieren muss.
In der Praxis ist das aber für Echtzeitsysteme ein Problem.
Also Echtzeitsysteme heißt, ich brauche Garantien dafür, wann meine
Operation fertig wird.
Und diese Garantien kriege ich erstmal so einfach nicht aus der
amortisierten Analyse raus.
Das heißt, wenn ich die Operation ausführe, kann es sein, ich bin
entweder in konstanter Zeit fertig oder ich brauche linear viel Zeit.
Und das ist für Echtzeitsysteme nicht vertretbar.
Jetzt ist die Frage, was kann man da machen?
Unser Ziel ist jetzt erstmal, ein richtiges O von 1 für diese
unbounded Arrays zu bekommen.
Und die Hauptidee ist, einfach die Bankkontomethode anzupassen.
Also ich will jetzt statt der Einzahlung, die wir in der letzten Übung
gesehen haben, will ich jetzt wirkliche Arbeit verrichten.
Und das nennt man dann Deamortisierung.
Also das funktioniert nicht immer so einfach wie das, was wir jetzt
sehen, aber das ist sicher eine interessante Sache, wenn man mal bei
Psi zum Beispiel in Berlin arbeitet.
Die machen nämlich gerade so Echtzeitsysteme.
Gut, also ich habe ja schon gesagt, wir wollen Arbeit verrichten statt
einzuzahlen.
Wenn ich mir jetzt das Pushback anschaue, dann mache ich nichts
anderes als schreibe das eigentliche Element, was ich gerade einfüge
und kopiere zwei weitere Elemente.
Das heißt, ich habe jetzt dieses Element hier eingefügt, nachdem mein
erstes Array halb voll war und kopiere dann hier unten die nächsten
beiden Elemente.
Jetzt mache ich das wieder mit dem nächsten Element, kopiere wieder
zwei aus dem ursprünglichen Array, mache das wieder und kopiere wieder
zwei.
Und bei dem letzten Pushback, wo ich eigentlich die Verdoppelung
durchführen würde, bin ich dann an der Position, an der ich sein
möchte.
Und was ganz wichtig ist, wenn man diese Folien hier anschaut, also
wir reden ja hier davon, dass wir wirklich O von 1 haben wollen.
Wenn ich jetzt ein Speichersystem habe, was mir diesen neuen Speicher
in linearer Zeit nur zurückliefert, was den zum Beispiel immer
initialisiert oder so, dann geht das hier nicht.
Also ich gehe in dieser Analyse hier davon aus, oder in diesem
Beispiel davon aus, dass der Speicher, den ich hier...
...in linearer Zeit diese 2n Elemente zugesichert, die sind allerdings
nicht initialisiert.
Okay, aber das stört uns nicht, weil wir können ja einfach diese
Elemente dann drüber kopieren und dann sind wir am Ende, also an der
Stelle, wo wir normalerweise das Array umkopieren würden, genau dort,
wo wir sein möchten.
So, Popback geht dann ebenfalls ähnlich.
Also hier löschen wir das und kopieren das Nächste.
Und das ist auch im Wesentlichen das, was ich noch sagen wollte.
Also wir haben jetzt gesehen, wie das in Worst-Case-Laufzeit in O von
1 geht.
Und ich habe auch schon erwähnt, dass das nicht überall so einfach
ist.
Also amortisierte Analyse ist ja an sich schon schwierig.
Das wird hier nicht einfacher, aber manchmal kann man halt diese
Amortisierung in echte Worst-Case-Komplexität umwandeln.
Gibt es Fragen noch dazu?
Dann war es das von meiner Seite.
Und Timo macht weiter.
So, ja, ich sortiere jetzt.
Warum sortieren wir so viel hier?
Naja, weil das eine einfache Aufgabe ist, die trotzdem sehr, sehr
viele kleine Probleme aufwirft.
Die man dann mit algorithmischen Ansätzen eben tatsächlich greifen
kann.
Jeder versteht, was man bei Sortieren machen muss, aber es gibt eine
irre Anzahl von...
Also ich möchte hier nochmal anfangen, komplett neu mit Sortieren.
In der Vorlesung habt ihr schon drei Verfahren gehabt, es kommen noch
ein viertes.
Was macht man, wenn man intuitiv sortiert?
Ich habe hier meine Spielkarten mitgebracht und wollte euch das
eigentlich vorführen, aber ich glaube, uns reicht die Zeit nicht.
Diese ganzen Techniken sind die, die man anwendet, wenn man quasi
Spielkarten sortiert.
Man nimmt Spielkarten, sucht sich den kleinsten raus, tut nach vorne.
Oder man nimmt einen und tut ihn an die richtige Stelle.
Oder man fängt an zu vertauschen.
Das sind so die intuitiven Ansätze, aber die sind meistens alle
ziemlich schlecht, asymptotisch.
Deswegen machen wir Sortieren in Algorithmen.
Exchange ist quasi das, was Quicksort dann benutzt.
Bei Exchange fange ich an, wahllos auszutauschen, aber eben da gehört
ein System dazu.
Gut, wir fangen an mit dem einfachsten, Selection Sort.
Muss ich hier mal ein bisschen umschalten.
So.
Und zwar habe ich euch hier hoffentlich den Code von Selection Sort
irgendwann mal.
Ja, also die beiden Folien desynchen jetzt, also die beiden
Projektoren desynchen.
Genau, das ist Selection Sort.
Und ich habe euch ein kleines Programm gemacht, was Selection Sort
zeigt.
Wo geht das?
Ich hoffe, man sieht inzwischen schon was.
Wunderbar.
Man sieht eine zufällige Anordnung von Zeichen.
Ich habe mir das nicht nehmen lassen, das zu coden.
Und wir nehmen mal Selection Sort und lassen das mal laufen.
Auf Zufall.
Und das ist ziemlich doof, was das macht.
Es nimmt...
Also, wo ist mein Pointer?
Es nimmt...
Es geht jedes Mal die komplette Liste durch, um die kleinste Karte zu
suchen.
Also die kleinste Karte ist hier immer markiert mit blau.
Und swappt sie an den Anfang.
Mega doof, im Prinzip.
So, dieses Programm zählt, wie viele weiche Zugriffe und wie viele
Comparisons diese Funktion macht.
Wie...
Hier drüben ist der Code.
Jetzt sagt mir mal jemand, jetzt halte ich das an, jetzt sagt mir
jemand, wie viele
Comparisons am Ende rauskommen.
Das ist eine hohe Zahl.
Das sind 100 Elemente.
Jetzt gucken wir uns mal unseren Code an.
Das ist der eine Vergleich, der hier drin steckt.
Wer weiß schon, wie viele es sind?
Könnte eine Klausuraufgabe sein, sowas Einfaches.
Ja?
Genau.
Möchtest du das erklären?
Nee, lieber nicht.
Okay, ich erkläre es.
Also warum?
Natürlich, die äußerste Vorschleife läuft genau n Mal.
Ja?
Da oben.
Also 0 bis n-1, das sind n Stück.
Und die innere Vorschleife läuft immer n-1, also i-1 Mal in dieser
Schleife hier.
Ja?
Da bekomme ich eigentlich genau dieses Gitter, was hier da steht.
Das ist so ein Dreieck.
Und dieser Vergleich wird auch jedes Mal ausgeführt.
So, für 100 Elemente, dann ist n Mal n-1 Halbe.
Für 100 Elemente sind n Mal n-1 Halbe.
100 Mal 99 geteilt durch 2 sind 4.950.
Ja?
Natürlich kommt das hier jetzt raus.
4.950.
Ja?
Die Array-Zugriffszahl ist irgendwie höher.
Die gucken wir uns aber normalerweise beim Sortieren erstmal nicht an.
Gut.
Nächster Algorithmus.
Also der macht, genau, was für eine Laufzeit habt ihr?
Wie viele Vergleiche?
n Mal n-1 Halbe ist natürlich n quadratisch.
Und zwar immer.
Worst Case, Average Case, immer.
Insertion Sort ist der nächste bessere, den ihr kennt.
Gucken wir uns mal an.
Insertion Sort, gucken wir uns erstmal an, was er macht.
Insertion Sort.
Was macht hier Insertion Sort?
Er hat den linken Teil, der linke Teil ist sortiert.
Er nimmt den nächsten, das nächste Element, was noch nicht sortiert
ist.
Noch ein bisschen langsamer.
Nehmt das da und fängt es an.
Er dann endlich die Position gefunden hat, wo es ihn gehört.
Na?
So.
Und dann ist er fertig.
Also jedes, ja, das ist selbst erklärend, jedes dieser roten Dinger
ist ein Zugriff.
Die grünen sind natürlich irgendwelche Zusatzinformationen.
Die
äußerste Schleife läuft natürlich N-1 mal durch diesmal, nicht N mal.
Hier innen drin, was passiert hier?
Hier wird das X, also das J ist der erste nicht sortierte, der wird
rauskopiert.
Und hier am Ende an die richtige Stelle eingefügt.
Und das hier läuft quasi die Zeit nach links.
Währenddessen schiebt er die Elemente hier durch die Gegend.
Gut.
Erstmal die Frage.
Ich brauche irgendwie mal einen anderen.
Ah ja, das war Sentinel-Vermeidung.
Okay, das hat der Professor Sanders auch in seiner Vorlesung gemacht.
Man kann diese Schleife vereinfachen, aber das lassen wir jetzt mal
weg.
Was?
Wie viele Vergleiche in worst case?
Ja?
Umgekehrt?
Dann machen wir das mal.
Okay, umgekehrt.
Ich scanne ihn.
Weißt du es?
Du meintest umgekehrt.
Wie viele Vergleiche?
Ja.
Was macht er denn hier?
Gucken wir uns mal die Schleife an, während das hier läuft.
Die erste läuft N-1 mal.
Und hier innen drin läuft jetzt immer das I mal nach links und macht
eben so viele Swaps.
Also lang und breit muss man sich das schon ziemlich genau überlegen,
was da jetzt rauskommt.
Aber es kommt... ah ja, gut.
Genau, die gleiche Zahl.
N mal N-1 halbe Vergleiche.
Das liegt daran, obwohl die äußere... ja, jetzt kommt es hier gleich.
Kommt gleich wieder unsere 4.950.
Wunderbar.
Gut.
Also ist genauso schlecht im schlimmsten Fall.
War auch irgendwie zu erwarten.
So, was passiert, wenn ich ein Random-Shuffle sortiere mit Insertion
Sort?
Ihr habt es ja schon vorher gesehen.
Lass mal laufen, lass mal bitte langsamer laufen.
Langsamer.
So, was passiert hier?
Jetzt hätte ich gerne eine Average-Case-Analyse.
Wir sortieren hier von Ground ab.
Ihr habt schon eine Average-Case-Analyse von QuickSort gemacht.
Die hier ist viel einfacher.
Was passiert hier eigentlich?
Achso, jetzt können wir dann...
Ich nehme ein zufälliges Element und laufe damit nach links bis zum
richtigen Einfüge-Position.
Das klingt analytisch greifbar.
Es ist irgendwie so ungefähr die Hälfte.
Deswegen gucken wir uns das mal tatsächlich auch an.
Ich muss überlegen, was machen wir jetzt?
Machen wir es da drüben.
Und zwar sinken wir die wieder.
Und um das analytisch greifbar zu machen, gucken wir uns jetzt mal ein
vereinfachteres Insertion Sort an.
Und zwar eins, wo wir jetzt da innen drin swappen.
Das ist tatsächlich das, was hier ausgeführt wurde.
Er swappt dieses Element jedes Mal hier runter.
Und was wir jetzt zählen werden, ist die Anzahl der Swaps.
Das ist ein bisschen einfacher und wir werden davon dann die Anzahl
der Vergleiche ableiten.
Wie viele Male swappe ich das Element nach links?
Und zwar im durchschnittlichen Fall.
Deswegen muss ich davon ausgehen, dass meine Eingabe irgendeine
Permutation von diesen Zahlen ist.
Ich muss den Durchschnitt über alle möglichen Eingabe-Permutationen
machen.
Die Permutation der Zahlen ist die Eingabe.
Und jetzt, was interessiert mich an dieser Permutation eigentlich?
Mich interessiert, wie viele Elemente ich vertauschen muss.
Und das habt ihr schon in lineare Algebra wahrscheinlich schon mal
gehört.
Das sind die Anzahl der Elemente,
die man bestimmt dran, weil man das unbedingt für Determinanten
braucht.
Aber in unserem Zusammenhang ist das quasi das, was wir korrigieren
wollen mit Insertion Sort.
Eine Inversion in einer Permutation ist einfach ein Fehlstand, heißt
es auf Deutsch.
Es ist eine Position, die größer ist, also das ist ein Paar, wo die
größere Zahl vorne steckt.
Die Permutation mit der kleinsten Anzahl von Inversionen ist natürlich
die sortierte Reihenfolge, Wie mit der größten
Zeit werde ich jetzt doch ein bisschen Folien-Karaoke machen, statt
das anzumalen.
Gut, also das habe ich gerade gesagt.
Insertion Sort swappt gerade.
Jedes Swap von Insertion Sort korrigiert genau eins dieser Fehlstände.
Jedes Swap reduziert die Anzahl der Inversionen um genau eins.
Denn Insertion Sort swappt genau dann, wenn sie falschrum stehen.
Vielleicht doch nicht.
Und was wir jetzt definieren, ist eine Zufallsvariable x.
Und wir suchen den Erwartungswert für die Anzahl der Inversionen in
einer Permutation.
Beliebigen Permutation.
Deswegen nehmen wir uns einfach eine beliebige Permutation her.
Also die heißen bei mir Sigma und die sind aus der symmetrischen
Gruppe.
Irgendeine beliebige Permutation.
Man sieht was, wunderbar.
Und x sei die Anzahl der Inversionen.
Und jetzt definiere ich mir so einen Indikator, Zufallsvariable, die
genau dann eins ist, wenn dieses i und j eine Inversion ist.
Und natürlich nur sonst.
Was gewinne ich dadurch erstmal noch nicht so besonders viel.
Mein x ist quasi natürlich die Summe dieser ganzen Zufallsvariable.
Und natürlich möchte ich linear über diese Summe drüber.
Sprich, am Ende interessiert uns dann doch eigentlich nur der
Erwartungswert dafür, dass ein Paar i, j gerade eine Inversion ist,
ein Fehlstand ist.
Ich brauche eine neue Folie.
Was ist dieser Erwartungswert?
Wie können wir den...
diese ganze symmetrische Gruppe an, wo alle Permutationen drin sind?
Und wir müssen da ein bisschen was drüber wissen.
Und zwar gibt es in sn
eine solche, dann gibt es genauso viele Permutationen dieser Art, wie
es gibt, wo die beiden vertauscht sind.
Natürlich an der gleichen Stelle.
Jetzt muss man sich überlegen, dass das genau gleich viele von der
ersten Zeile hat wie die zweite.
Warum ist das so?
Ich kann die einfach vertauschen.
Das ist die Permutation.
Dadurch, dass es hier gleich viele gibt, die erste, also wenn a
kleiner als b ist, dann ist es keine Inversion, dann ist dieses x, y
und j null.
Wenn das a größer ist als das b, dann ist das x, y und j gleich eins.
Dafür, dass mein x, y für egal welches i und j gleich eins ist.
Dadurch, dass es, wenn ich eine beliebige Permutation herauspicke,
dann hat es die Wahrscheinlichkeit genau ein Halb, dass es von der
oberen Hälfte ist oder von der unteren Hälfte.
Das ist genau ein Halb.
Und das ist dieser Erwartungswert von dieser kleinen Zufallsvariable,
die wir uns definiert haben.
So, die restliche Rechnung, jetzt haben wir uns das hier gemerkt.
Ja, genau.
Das ist einfach die Summe, i kleiner j und das ist ein Halb.
So, was ist das hier?
Ich kann kaum lesen.
Das ist die Anzahl der Paare, wo i und j kleiner, also i kleiner als j
ist, aber natürlich in einem gewissen Bereich, sonst macht das nicht
besonders viel Sinn.
Das ist die Anzahl der Paare, wo i kleiner als j ist.
Das ist einfach der Binomialkoeffizient.
Zwei aus n gewählt, mal ein Halb.
Was im Übrigen das gleiche ist als das Halbe, was hier die ganze Zeit
schon auftaucht.
Ich wähle mir ein i und dann habe ich nur noch den oberen Teil, um das
j zu wählen.
Kombinatorik.
Was kommt hier raus?
N mal n-1, Viertel.
Genau die Hälfte.
Der Average Case von Insertion Sort ist genau die Hälfte des Worst
Cases.
Jetzt rechnen wir das kurz für unser Beispiel hier noch irgendwo aus.
Das n von meiner ganzen Animationsgeschichte ist immer 100 gerade.
Deswegen ist das jetzt 100 mal 99 durch 4.
Das ist 2475.
Also die Hälfte von den 4950 da.
Bevor wir das verifizieren, ich sage euch, dass es falsch ist.
Wir haben nämlich was übersehen.
Oder lassen wir es mal kurz laufen und überlegen uns dann.
Achso, ja, ich habe euch natürlich schön aufgeschrieben, könnt ihr
nachgucken.
Bis auf diesen Permutationen.
Den müsst ihr dann auf YouTube nachgucken.
Dann gucken wir uns jetzt erst noch mal an, was hier tatsächlich
gezählt wird in dem Programm.
Dann sage ich euch, dass das nicht ganz richtig ist.
Ich habe vorhin konstatiert, dass es die Hälfte von den 4950.
Das passt gar nicht.
Entschuldigung.
Nein?
Kommt schon.
Dann lasse ich es euch noch mal laufen.
Jetzt ist es da.
Dann lasse ich es euch noch mal laufen.
Die Anzahl der Vergleiche 2400.
So, 2000.
Die Anzahl der Vergleiche, die hier stehen, sind 2475.
Die Anzahl, die ich erhalte, sind nur 2200.
Noch nicht ganz.
Es ist natürlich hier zufällig, was rauskommt.
Wenn ich das noch mal ausführe, kommt was anderes raus.
Diesmal ist es ein bisschen mehr.
Das 2200 war ziemlich wenig.
Ja, genau.
Sehr gut.
Wir haben meiner Meinung nach was vergessen hier.
Wir haben hier was vergessen, und zwar die Anzahl der Swaps hier
drinnen ist nicht ganz die Anzahl der Kompetenzen.
Es ist pro Durchlauf einer mehr.
Ja, der läuft hier hinein, durchläuft die Swaps, macht dann aber noch
einen Vergleich und dieser Vergleich, der nimmt ihn raus aus der
Schleife.
Das heißt, ich habe noch mal plus n dazu.
Allerdings habe ich das hier nicht lang genug laufen lassen, um das zu
verifizieren.
Genau.
2200, okay.
Ja, ist eine Zufallsvariable.
Aber eine doch ganz nette Analyse, weil man hier tatsächlich sieht, wo
der Zufall passiert.
Der Zufall passiert dabei, dass ich hier etwas wähle und es nach links
schiebe.
Hängt natürlich komplett davon ab, wie diese Permutation ist.
Okay, gut.
Kommen wir zum nächsten Sortieralgorithmus.
Der Chris fragt andauernd, haben Leute Fragen.
Ich frage das irgendwie weniger.
Das heißt, ihr müsst laut sein.
Also Fragen sind natürlich jederzeit erlaubt.
Nächster Algorithmus, kommt auf die linke Seite,
ist Merge Sort.
Das ist der Autocode von Merge Sort.
Merge Sort, Merge Sort, fertig.
Es ist natürlich in Realität oder in dem Programm, was ich da gemacht
habe, nicht ganz so einfach.
Da muss man sich schon ziemlich genau überlegen.
Hier ist der Merge Sort Vergleich.
Am Anfang checke ich, dass mein Merge Sort nicht trivial sortiert.
Dann teile ich das Ding durch zwei, mache Merge Sort links und rechts.
Das ist der Divide Teil von diesem Divide & Conquer Algorithmus.
Und jetzt muss ich bei Merge Sort ein externes, also ein temporäres
Array allocieren.
Es gibt tatsächlich eine In-Place Merge Sort Variante, die ist aber
ziemlich ineffizient.
Die meisten Merge Sort Varianten machen irgendwo zusätzlichen
Speicher.
Das ist eine ganz andere Geschichte nochmal, ob ein Sortieralgorithmus
In -Place ist oder Out-of-Place.
Der ist fast immer Out-of-Place.
Deswegen muss ich hier temporären Speicher allocieren und in diesen
Speicher merge ich dann die bereits sortierten Folgen hinein.
Das Mergen ist tatsächlich eine kleine Schleife.
Wenn eins dieser bereits sortierten Folgen leer ist, das ist dann,
wenn es eins dieser Bedingungen greift, dann muss ich den Rest der
anderen rein kopieren.
Das kann ich natürlich auch hier machen.
Und dann kopiere ich die ganze Sache zurück.
Ich wollte euch das nur kurz zeigen, dass das nicht so Haskell-mäßig
einfach programmiert werden kann in Wirklichkeit.
Und dann gucken wir uns natürlich den Algorithmus auch wieder an.
Merge Sort.
Langsamer machen.
Noch langsamer.
Er macht kleine Häppchen, die sortiert sind und sortiert sie dann,
mergt sie dann zusammen.
Und jetzt mergt er die beiden großen und
wird danach wieder rein kopiert.
Deswegen tut er erst hoch ablaufen, das ist dieser Vergleich hier, und
dann wird es zurück kopiert.
Dieser große Merge, das geht in den Hintergrundspeicher und jetzt wird
das Ergebnis rausgeschrieben.
Diese Farben symbolisieren die Grenzen, wo er gerade arbeitet.
Okay, ihr wisst schon eine ganze Menge über Merge Sort, deswegen
reicht das auch für Merge Sort.
Kommen wir zu dem Leap.
Man überlegt sich jetzt natürlich, warum macht man überhaupt weiter?
Jetzt habe ich doch einen optimalen Algorithmus hier gefunden.
Warum weitermachen?
Ja, in der Realität ist Quick Sort schneller.
Jetzt müssen wir da umschalten.
Ach nee, Entschuldigung.
Umschalten da lang.
In der Realität wird meistens Quick Sort eingesetzt, weil der
schneller ist.
Und jetzt wiederholen wir ein bisschen was von der Vorlesung und
machen ein bisschen weiter in Vorlesung.
Das war der Quick Sort der Vorlesung.
Im Prinzip nehme ich mir ein beliebiges Merge Sort,
die größer diesem Pivot sind.
Und danach muss ich nur noch konkatenieren.
Das ist ein umgedrehtes Merge Sort.
Wir gucken uns, ich bin mir nicht ganz sicher, wo Professor Sanders...
...einfache Implementation...
...bisher noch nichts gemacht.
Man teilt Quick Sort sehr gerne in zwei kleine Subroutinen auf.
Nämlich diese rekursive Quick Sort Variante und das Partition.
Partition bedeutet nichts anderes.
Ich nehme mein Array, nehme mein Pivot und am Ende ist das Pivot
irgendwo in der Mitte.
Der linke Teil ist kleiner und der rechte Teil ist größer.
Das ist das Ergebnis von Partition.
Und Partition wird so implementiert.
Gehen wir mal kurz durch, weil das sehr wichtig ist.
Ah, das...
Beispiel.
Quick Sort.
Partition.
Tisch.
Wunderbar.
Beispiel.
Wichtig, ein Beispiel von Partition müsste...
...vorgerechnet werden.
Ah, da habe ich eine Folge.
Die möchte ich partitionen.
Mit dem Algorithmus, der da rechts steht.
Was brauche ich dafür?
Ich brauche ein Pivot.
Ich sage euch, wenn die Zeit reicht, auch noch ein bisschen was über
Pivot -Wahl.
Aber für dieses Beispiel nehmen wir jetzt einfach das erste Ding als
Pivot.
Habt ihr hoffentlich auf dem Übungsblech schon mal gemacht, hier
diesen Algorithmus.
Aber wir machen es trotzdem mal kurz.
Dann brauchen wir, dann tauschen wir das Pivot nach hinten.
Mit der 9.
Das eine ist i, das andere ist j.
Und es gibt eine gewisse Kontroverse.
Der Pointer zeigt eigentlich in den Zwischenraum von diesem Array.
Weil ich möchte eigentlich folgendermaßen Pivot partitionen.
Ich möchte eigentlich so partitionen.
Da drüben steht es, glaube ich, nochmal auf den Vorlesungsfolien.
Ich möchte so partitionen, dass hier kleiner gleich ist, dort größer
ist, dort unbekannt und hier das Pivot am Ende drin steht.
Deswegen will ich eigentlich hier meine Zeiger drin haben.
Das ist zwischen den Bereichen.
In der Realität macht man die entweder links oder rechts davon.
Man muss da nur ein bisschen aufpassen.
Okay, machen wir kurz ein Partition-Schritt.
Die 9 ist größer als mein Pivot.
Deswegen muss ich quasi hier trivial swappen und der i bleibt, der j
geht nach vorne.
Ja, so.
Bisschen trivialer swap?
Ne, doch, genau so.
6 ist kleiner.
Da kann ich nichts machen, kann ich einfach den j weiterschieben.
j ist aktuell noch nicht, dieser Bereich rechts, davon ist der noch
nicht partitioned-Teil.
Der Teil ist der größere und der bislang sehr leere kleine Bereich ist
der, wo es kleiner ist.
Hier passiert jetzt was.
Hier muss ich jetzt diese 1 mit der 9 vertauschen.
9, 7, 2, 4, 5, 3 und advance beide Zeiger.
Hoffentlich sieht man das.
0 muss ich hier wieder nach vorne swappen, das swappe ich mit dem da.
Der Rest bleibt gleich.
Das ist immer noch mein Pivot hier.
Wunderbar.
Das ist so das, was man immer bei Partition im Hinterkopf haben muss.
7 ist gut, 7 ist größer als die 3, deswegen nur j nach vorne.
Weil ich weiß, dass das größer ist.
1, 0, 2 vertauscht mit dem da.
Das bleibt gleich.
Das sollte man ordentlich erschreiben.
4 ist okay und 5 ist auch okay und jetzt ist mein i hier hinten
angekommen.
Das ist die Abbruchbedingung bzw.
die Laufvariable j.
Die Laufvariable endet dann.
Was habe ich jetzt hier gewonnen?
Es fehlt noch ein Schritt.
Das Pivot muss wieder in die Mitte.
Was habe ich hier jetzt gerade?
Ich habe die Invariante, dass alles was hier zwischen den Bereichen
kleiner, gleich dem P ist.
Alles was hier dazwischen ist, größer als P. Und alles was da ist,
gleich P ist.
Kein Fehler gemacht?
Wunderbar.
Deswegen kommt das 3-Element genau an die Stelle von i und teilt damit
dieses R.
Und die 9 swappe ich nach hinten.
Und jetzt mache ich Rekursion.
Mache ich Rekursion auf den Teil und auf den Teil und auf den Teil
nicht.
Weil der ist an der richtigen Stelle.
Gut.
Ich zeige euch jetzt mal Quicksort in live.
Also noch live als das hier.
Ich weiß noch irgendwie nie, wo das da hingeht.
Jetzt.
Genau, das Beispiel kommt auch auf den Vorlesungsfolien.
Das ist genau das, was ich gerechnet habe.
Und in live ausgeführt sieht eure Quicksort-Variante, das ist die LL.
Es gibt eine andere Variante, das ist das Original-Quicksort von
Hoare.
Das benutzt zwei Zeiger links und rechts, nur falls euch das mal im
Internet begegnet.
Das benutzt quasi diese Zeiger auf beiden Seiten nach innen gehend.
Das ist nur eine andere Variante.
Wenn ihr euch das richtig angeguckt habt, wisst ihr auch, wie die
andere Variante funktioniert.
Okay, dann gucken wir uns mal an, wie der das hier macht.
Er wählt sich.
Langsamer, langsamer, langsamer.
Wählt sich ein Pivot.
Wählt sich ein Pivot, dieses grüne, swaps nach hinten, so wie ich das
auch gemacht habe.
Und dann laufen diese beiden Zeiger, die ich vorher mit diesem
Kleberlein gemacht habe, entlang des Arrays.
Er swapt genau an diesen beiden Stellen.
Kleinere nach links, größere oder größer gleich werden übersprungen.
Was man sieht, ist, dass diese Höhe, alles was hier links ist, ist
kleiner als diese Höhe.
Alles was rechts ist, ist größer.
Das ist genau das, was ich gerade gezeigt habe, nur in alten Grafiken.
Jetzt kommt er schneller.
So, und jetzt kommt die Rekursion, die ich natürlich nicht mehr
gezeigt habe.
Hier hat er eine dumme Pivotwahl gerade getroffen.
Nochmal eine dumme, weil irgendwie fast alles kleiner ist.
Äh, okay.
So wird es natürlich schwierig.
Das ist richtig.
Dann erzähle ich ein bisschen was zur Pivotwahl.
Wir nehmen immer das erste Element als Pivot.
Das macht man natürlich nicht in der Realität.
Man nimmt auch nicht das letzte Element als Pivot in der Realität.
Was gibt es denn noch für Möglichkeiten?
Ihr kennt aus der Vorlesung ein zufälliges.
Es hat seine Vorteile, weil es kein allzu schlimm...
sowas würde wahrscheinlich nicht mehr passieren.
Vorteile.
Insbesondere sind meistens Random-Generatoren ziemlich teuer.
Machen irgendwelche Divisionsoperationen.
Die möchte man eigentlich nicht bei jedem dieser Rekursionsschritte
machen.
Achso, dieses Programm könnt ihr auch mal daheim ausprobieren.
Ist zwar faszinierend, aber...
Genau.
Ein...
So.
Yay.
Äh, ja.
Genau, Pivotwahl.
Eine andere Möglichkeit, ein Pivot zu wählen...
ist die, die man auch immer verwendet, ist der Median von 3.
Median, wisst ihr, was es ist?
Man nimmt drei Elemente und das, was sortiert, in der Mitte steht.
Bei dreien ist das mega banal.
Welche drei nimmt man?
Man nimmt das Erste, das Letzte und das in der Mitte.
Und von diesen drei nimmt man das Mittlere.
Das ist die Pivotregel Median of 3.
Die wird meistens verwendet.
Warum ist die gut?
Man braucht keine teuren Divisionsoperationen.
Man macht ein paar mehr Compares.
Und man hat aus dreien...
Man möchte das Pivot ja immer so wählen, dass es ungefähr in der Mitte
landet, damit ich eben das in zwei Parti...
Viel, viel größeren Arrays benutzt man natürlich mehr als Median von
3, dann nimmt man Median von 40.
40, ausgewählt, zufällig ausgewählt.
Oder statisch ausgewählt, nicht zufällig.
Okay.
So.
Da lang.
...Rekursion zu zeigen.
Ich erkläre das nur kurz.
Man partitioniert und irgendwo steht in der Mitte dann das Pivot.
Das Pivot bleibt unverrückbar an dieser Stelle.
Deswegen kann man die restliche Rekursion rechts und links davon
machen.
Das mit der Übung hast du schon gesagt, gell?
Machen wir lieber interessantere Sachen.
Ihr habt gerade in dem Beispiel gesehen, Quicksort tut sich schon
ziemlich schwer am Ende.
Bei kleinen Eingaben ist Quicksort nicht unbedingt das Mittel der
Wahl.
In der Realität bricht man die Rekursion bei relativ kleinen Sachen ab
und macht dann einen in der Asymptote schlechteren Algorithmus,
nämlich beispielsweise Insertion Sort, der aber auf diesem kleinen
Bereich, bei unseren heutigen Prozessorarchitekturen, wo dieser kleine
Bereich im Cache liegt, sehr, sehr viel schneller arbeitet als
Quicksort.
Insertion Sort ist sehr, sehr schnell, wenn du einen kleinen Bereich
hast, weil der macht nur so.
Fertig.
Quicksort hat ein relativ unregelmäßiges Zugriffsmuster und deswegen
ist es relativ langsam.
Und in der Realität macht man dann tatsächlich einen Insertion Sort.
Als Basisfall.
Das macht nichts aus.
Ich kann in jeder Rekursionsstufe einen anderen Algorithmus nehmen,
weil ich muss nur diese Untermenge einfach sortieren.
Mit egal welchem Algorithmus.
Das ist, genau, oh je, das ist ein Professor Sanders Folie.
Ich habe vorhin etwas dazu gesagt, dass es in place ist.
Genau.
Das hat R.A.
vorher erzählt.
Quicksort wird gerne gesagt, dass es in place sei.
Das ist nicht richtig.
Nicht hundertprozentig richtig.
Wir hatten gerade den Worst Case.
Das ist der Worst Case für Quicksort.
Wir hatten gerade ziemlich schlechte Fälle, wo man quasi nur ein Pivot
wählt und der Rest einfach in die nächste Rekursionsebene geht.
Was im Prozessor, im Speicher dann tatsächlich passiert, ist ein
rekursiver Aufruf.
Auf dem Stapel des Speichers, des Prozessors, liegt dann dieses Pivot
trotzdem noch im RAM.
Und wenn ich jetzt jedes Mal nur ein Pivot wähle und der Rest des
Arrays einfach in die nächste Rekursionsstufe geht und wieder nur ein
Pivot, dann habe ich eine Stapelhöhe in des gesamten Arrays.
Ich nehme mir mal ein Pivot, nehme es raus und stecke es eigentlich im
Prinzip in den Stapel.
Damit habe ich das komplette Array kopiert.
Plus zusätzlich diese paar Variablen, die ich hier noch habe.
Deswegen ist es eigentlich nicht in Place.
Mergesort braucht auch nie mehr temporären Platz als N.
Das ist das, was hier dargestellt ist.
Ich nehme ein Pivot und partitioniere und effektiv tue ich nur eins
abspalten.
Jedes Mal.
Deswegen brauche ich mehr Platz.
Im Mittel ist es natürlich O von N, aber im Worst Case ist es
tatsächlich das ganze Array.
Man kann allerdings einen kleinen Trick anwenden, um diese Sache zu
begrenzen.
Und zwar sagt man, ich steige nur in große Bereiche ab.
Nee.
Ah genau, ich steige in den kleineren Teil ab.
Ich partitioniere irgendwo, steige den kleineren Teil komplett ab und
danach mache ich den großen.
Nochmal auf der gleichen Ebene.
So war das.
Dadurch limitiere ich die komplette Rekursionstiefe.
Nochmal.
Dadurch, dass ich einen kleineren Teil von zwei Hälften nehme,
begrenze ich die Rekursionstiefe auf höchstens Log N.
Weil der kleinere Teil immer kleiner ist als die Hälfte.
Deswegen ist der begrenzt.
Wenn ein größeres Stück da ist, partitioniere ich 9.
Nochmal.
Auf der gleichen Ebene, ohne mehr den Rest merken zu müssen.
Ich glaube, wir wiederholen das nochmal.
Genau, Log N.
So, ich möchte euch
noch ein anderes kleines Beispiel zeigen.
Es gibt nämlich einen schlimmen Fall für dieses Quicksort, was ihr
kennt.
Und das tritt dann ein, wenn fast alle Elemente gleich sind.
Bis auf zwei, in diesem Fall.
Was macht das Quicksort dann?
Schiebt es eine nach hinten, schiebt gar nichts.
Durch die Gegend.
Jedes Mal.
Gucken wir uns mal an, wo das passiert.
Das ist der schlimmste Fall von eurem, oder dem normalen Quicksort,
diesem Quicksort, diesem 2-Zeiger-Links-Quicksort.
Der Fall tritt dann auf, wenn das Pivot hier gewählt wird, und er
scannt hier einmal durch und macht dann die Rekursion links.
Das ist gerade dieser Rekursionsstapel, der ewig lang nach unten geht.
Am Ende haben wir fast quadratisch viele Vergleiche.
Mehr als quadratisch viele Vergleiche.
Also quadratisch viele, mehr als Selection Sort.
Das ist schlecht.
Deswegen gibt es eine Variante von Quicksort, die in drei Bereiche
partitioniert.
Und zwar, machen wir erstmal dahin, es partitioniert in drei Bereiche,
nämlich kleiner, größer dem Pivot, gleich dem Pivot hinten und der
übrige Teil.
Wenn ihr das mit den Zeigern, was ich euch da gerade noch mal erzählt
habe, wirklich verstanden habt, dann ist das sehr einfach.
Man fügt nämlich hier noch einen Zeiger hinzu, nämlich K.
Dieses K definiert diesen kleinen Istgleichbereich am Ende.
Und was man dann macht, ist einen ternäheren Vergleich, einen
Dreiwegevergleich mit dem aktuellen Element.
Ich nehme ein aktuelles Element, mache einen Dreiwegevergleich, einen
kleineren Vergleich und einen größeren Ausgang von diesem Vergleich
und je nachdem, wie dieser Ausgang geht, schiebe ich das Element an
die richtige Stelle und inkrementiere den richtigen Zeiger.
Hier kommen die bisher unklassifizierten Elemente raus.
Wenn es gleich dem Pivot ist, schiebe ich es hier hin und
dekrementiere K.
Das ist der erste Fall.
Wenn es kleiner ist als das Pivot, kommt es hier hin und inkrementiere
I und J.
J wird im ersten Fall nicht inkrementiert, weil ich ein neues
Fragezeichen -Element von hier nach dort einswappe.
Und das muss ich nochmal neu prüfen.
Das Ding heißt Ternary Quicksort.
Macht einen Istgleichbereich.
Am Ende bleibt der Istgleichbereich da hinten, da will ich ihn aber
nicht haben, ich will ihn in der Mitte haben.
Weil es kleiner gleich größer sein soll, so wie hier unten.
Deswegen muss ich am Ende diesen Bereich hier dazwischen kopieren.
Es kostet natürlich zusätzliche Operationen und zusätzlicher Platz,
aber keine weiteren Vergleiche.
Das ist der Swap hier.
Und zurückliefern für die Rekursion muss ich dann diese Grenzen.
Ich muss nur noch Rekursionen hier machen und da machen, weil die sind
alle gleich.
Das heißt Ternary Quicksort.
In der Regel wird für diesen Ternären-Vergleich auch nur Kosten 1
genommen.
Dieser Ternäre-Vergleich kostet mich genauso viel wie ein normaler
Vergleich.
Das ist tatsächlich auch im Prozessor so.
Ich habe eine Vergleichsoperation, dann setzt der im Prozessor ein
paar Flecks und danach kann ich mit diesen Flecks jumpen.
Das ist tatsächlich in der Realität auch so.
Deswegen kostet es 1.
Die Funktion Partition liefert deswegen zwei Indizes, die kommen hier
raus und entsprechend muss man diese Funktion hier anpassen.
Aber der ganze Trick besteht darin, hier noch einen Zeiger
hinzuzufügen.
Könnt ihr euch nochmal genauer angucken daheim.
Wir gucken uns das jetzt hier nochmal in live an.
Ternary Quicksort, LL.
Hier passiert natürlich reichlich wenig.
Jetzt mal ein bisschen anderes Beispiel.
Hier sind auch viele gleich.
Die, die gelb markiert sind, ist dieser Istgleich-Bereich.
Die Zeiger laufen genauso wie vorher.
Wenn er eins findet, was genau gleich ist, wird es an diese Stelle
geswappt.
Jetzt muss er es da reinkopieren und dann ist es schon fertig.
Jetzt hat er wieder ein Pivot gefunden, partitioniert.
Die, die größer sind, kommen hier rechts.
Algorithmen in den vorgefertigten Programmiersprachen.
Diese ganze Sortierei, die man hier lernt, ist analytisch unheimlich
cool und wichtig.
Aber ihr sollt keines von diesen Algorithmen implementieren.
Weil jede Programmiersprache bietet schon Sortieren.
Und das, was die gemacht haben, ist garantiert besser als auch nur
dieses Quicksort.
Die benutzen tatsächlich, okay, ich zeige euch gleich, was die 5
verwenden.
Das ist, in Java gibt es und in C++ gibt es, guckt euch nachher an, es
gibt in C++ stdsort und stablesort.
stdsort ist wahrscheinlich die allermeist verwendete Sortierfunktion
überhaupt auf der Welt.
Schauen wir uns das mal an.
Mein Programm hat auch die hier irgendwo unten drin.
Und zwar habe ich tatsächlich diese Funktion genommen und
instrumentiert.
Sagen wir aber wieder RandomShuffle.
Das ist die Funktion, wie sie in C++ tatsächlich gemacht wird.
Und füllen Sie mal aus.
Dieses Muster kennt ihr wahrscheinlich inzwischen.
Das ist Quicksort.
Das ist Quicksort, wie er da mit den Zeigern entlangläuft.
Wenn er in der Mitte ab und zu greift, dann ist das ein Median von 3
Test.
Jetzt macht er die ganzen kleinen Sachen und wenn man sich jetzt ganz
genau hinguckt, die kleinen macht er mit InsertionSort.
Das geht nach links runter.
In diesen kleinen Bereichen.
Wenn ihr C++ verwendet, benutzt ihr das.
Das ist eine Kombination von Quicksort und InsertionSort, wie vorher
auf diesen Folien tatsächlich gezeigt.
Jetzt machen wir ein bisschen schneller.
Mangelt Zeit.
Und StableSort, also ich muss stabil sortieren, wisst ihr
wahrscheinlich, was das ist.
Macht das da.
Kennt ihr auch inzwischen, gell?
Das ist Mergesort.
Und jetzt fängt er an zu mergen.
Es scheint in der Realität ein bisschen schneller zu sein.
So.
Bin ich mal gespannt, ob das auch noch funktioniert.
Es gibt auf YouTube ein ganz nettes Video mit Ton.
Das haben vielleicht einige von euch gesehen.
Ich habe mir das nicht nehmen lassen.
Mal sehen, ob das funktioniert.
Natürlich funktioniert das Audimax nicht.
Ja, das Audimax funktioniert natürlich nicht.
Aber da kann ich jetzt auch nichts machen.
Deswegen müssen wir jetzt Low-Tech anwenden.
Jetzt können wir natürlich nicht gleichzeitig reden.
Also nur Vergleiche.
Also Vergleiche geben hier Töne.
Und zwar genau die Sinus- oder Triangle-Töne, die tatsächlich dann die
Werte sind, die verglichen werden.
So.
Schneller.
Ja, genial.
Hast du nichts gesagt?
Ach so.
...SWIDGET-Programm für Windows und Linux.
Es gibt viel mehr Sortieralgorithmen.
Die meisten sind doof, weil nur die Doofen sind lang genug, um was zu
machen.
Denn Quicksort ist gleich fertig.
Okay, bevor ihr davonlauft, noch ein kleiner Hinweis zu dem
Übungsblatt.
Uns ist da ein kleiner Fehler passiert.
Die meisten werden es gemerkt haben.
Heapsort ist noch nicht in der Vorlesung, ist aber schon auf dem
Übungsblatt drauf.
Heapsort ist das da.
Wenn ihr die Übung macht, wir nehmen das Heapsort aus der Bewertung
raus.
Also es gibt Zusatzpunkte, wenn ihr Heapsort macht, aber es geht aus
dem Gesamtzahl der Aufgabe weg.
Genau ein Punkt.
Okay?
Bis bald.