Video 4-5: Weighted QuickUnion und Pfadkomprimierung

0:03 Aber das Hauptproblem bei Quick Union und bei Quickfind ist schon algorithmischer Natur. Wir werden also weitere Verbesserungen brauchen, um dieses Union Find Problem irgendwie zufriedenstellen zu lösen. Manchmal ist guter Rad teuer. Was könnte man machen? Eine Option, die wir hier haben, ist äh, dass wir versuchen, diese diese beiden Extreme ein bisschen zu kombinieren. Wenn man äh noch mal drauf schaut, was wir da getan haben, dann war Quickfind so, dass wir alle Arbeit, die wir potenziell jemals brauchen, in Union schon erledigt haben. Jedes Element hat seinen Repräsentanten direkt auf dem Silbertablett in dem Array präsentiert bekommen, so dass Feind es nur noch auslesen muss. Und das komplette Gegenteil bei Quick Union, da war in Union gar nichts, haben wir versucht gar nichts zu tun und alle Arbeit auf Feind zu delegieren. Da aber Union Feind aufruft, hat das überhaupt nicht gut funktioniert. Vielleicht ist es aber möglich irgendwie ein Mittelweg zwischen diesen beiden Dingern zu finden, bei denen ich ein bisschen Arbeit mache in Union, aber eben nicht linear viel und hoffentlich dann in Feind auch ein bisschen mehr als nur auslesen habe, aber auch wiederum nicht so viel wie diesen ganzen Farter verfolgen.

1:19 Das wäre ja mal eine eine ein Gedanke. Ähm, anderer Ansatz ist so ein bisschen konkreter zu gucken, was hat uns bei Quick Union den Ärger eingebrockt und das war die Höhe dieser Bäume. Vielleicht kann man ja andere Bäume bauen als diese linearen Ketten, die im Wesentlichen ein langer Pfad sind. Ähm, grundsätzlich gibt's natürlich Bäume, die deutlich weniger hoch sind. Insbesondere sind das ja keine, die sind nicht beschränkt in den Anzahl Kindern. Wir könnten theoretisch einen Baum haben, der eine Wurzel hat und alle anderen hängen direkt drunter. Das wäre super. Da ist aber nicht ganz klar, wie wir den mit Union herstellen. Wir haben aber doch einige Freiheit, wie wir die Bäume verschmelzen. Also auch das wäre eine Option. Das ist so ein bisschen die Brainstorm Folie. Ich dachte an der Stelle mal, bevor ich Ihnen jetzt immer die Lösung fertig präsentiere, frage ich Sie mal, was Sie denn denken. Das ist wieder so eine ähm so eine Bauchgefühlge, auf die Sie die Antwort nur kennen, wenn sie äh schon vorgeblättert haben oder sehr sehr schnell sind oder ähm für den letzten Fall sollten wir dann noch mal über Abschlussarbeiten reden.

2:32 Äh wenn sie auch jetzt einfach nur in irgendwas in die Richtung raten, ist auch okay. dann ist es mehr so, um das, was folgt, ein bisschen besser im Gedächtnis zu verankern.

3:01 Ja, Fehler meinerseits war keine Option eh mit irgendwas völlig anderes. Die Option was völlig anderes, die gibt's natürlich immer, wenn man Algorithmen designt. kommt immer wieder vor, auch bei so elementaren Problemen, die schon seit Jahrzehnten äh unterrichtet werden und gelöst als als gelöst angesehen werden, dass jemand mit einer neuen Idee um die Ecke kommt, die plötzlich neue Möglichkeiten eröffnet.

3:47 Na gut, ich kann es den jetzt äh nicht ändern, ohne es zu stoppen, dann lassen wir es dabei. Also äh ein paar mehr Leute sind dafür, die Bäume zu begrenzen, aber ist halbwegs gemischt und es gibt auch ein paar Pessimisten. Ähm schauen wir mal.

4:18 Also, ich sper sie mal jetzt hier ein. Wir werden sehen, dass beides funktioniert. Und es ist sogar so, dass beides separat ganz gut funktioniert und beides zusammen noch viel besser. Äh, was ich damit meine, sehen Sie gleich. Das ist hier ein tatsächlich schöner schönes Beispiel, wo das super funktioniert. Wie könnten wir dieses Problem mit der Höhe der Bäume angehen? Man kann natürlich versuchen, die Bäume irgendwie total clever zu restrukturieren, aber das ist vielleicht dann mehr Aufwand. Äh was wir bei ähm was wir direkt in der Hand haben, ist bei Union zu wählen, wie wir diese Bäume zu einem machen. Bisher nehmen wir ein Baum und hängen ihn ein Baum und hängen ihn als neues Kind an die Wurzel des anderen Baumes. Und da kann es uns passieren, dass der größere Baum als Kind unter den kleinen gehangt wird oder umgekehrt. Wir haben darauf äh nicht geachtet.

5:17 Und man könnte ja intuitiv sagen, es macht dem kleinen Baum weniger aus, ein Level nach unten zu rutschen, indem er hier Kind von der anderen Wurzel wird, als diesem großen Baum, ähm, der ja eh schon groß ist und eh schon hoch ist. Ich habe jetzt hier nur allgemein groß gesagt, wir werden tatsächlich groß hier instanzieren mit Anzahl Knoten, Anzahlobjekte in diesem Baum. Man könnte auch direkt damit der Höhe arbeiten. Funktioniert im Wesentlichen genauso. Der Trick ist ein bisschen oder die die Analyse ist ein bisschen sauberer mit der Größe, deswegen machen wir das da. Ähm funktioniert ansonsten aber gleich.

6:02 Auch dazu gibt's ähm eine Animation, die das zeigt. Äh, das sieht fast genauso aus wie das Quick Union, nur dass manchmal der eine Baum unter den anderen gehängt wird, wo es vorher umgekehrt war. Ähm, hier z.B. die neun wurde Teil von der vier, weil sie kleiner ist. Hier ebenso fünf ist der kleinere Baum.

6:32 Hier ebenso jetzt kommt noch mal der spannende Teil hier. hätte man auch eventuell war gleich groß, ne? Kein Unterschied. Hier war wieder ähm ein Baum kleiner als der andere. In diesem kleinen Beispiel sieht man den Unterschied nicht so krass. Wenn man ein größeres zufällig gewähltes Beispiel baut, dann ist bei diesem ursprünglichen Quick Union durchaus mal sowas dabei. Das ist nicht der Worst Case, dass das alles in einer langen Kette ist. Das ist aber auch nicht schrecklich weit davon weg, weil ich doch relativ viele Stufen nach unten habe. Und allein optisch ist in diesem gewichteten Teil, wo ich immer den kleineren Baum Kind vom größeren werden lasse, die Höhe der Bäume deutlich besser. Okay, das wäre die empirische Variante. Wir werden uns auch gleich noch anschauen, dass man da was beweisen kann. Erstmal aber der Code dazu.

7:27 Die Implementierung ist im Wesentlichen die gleiche wie bei Quick Union, aber mit einer Verfeinerung, dass wir die Größe der Teilbäume uns merken. Das heißt, gibt es es gibt ein zweites Array Seze und das ist ein bisschen ähm trickreich. Das zählt die Anzahl Objekte in der Äquivalenzklasse, aber nur die ist diese Anzahl ist nur korrekt, wenn dieser Index die Wurzel von einem Baum ist. Das spart uns ein bisschen Arbeit bei der Aktualisierung. Wir können sozusagen ignorieren, dass andere Elemente weiter unten im Baum nicht die korrekte Größe kennen. Wir brauchen die Größe immer nur von der Wurzel. Das so eine eine kleine Optimierung an der Stelle. Äh, Feind ist genauso wie vorher, das äh ändert sich nicht. Und bei Union nehme ich eben den kleineren Baum. Das heißt, ich habe hier einen Vergleich. Nachdem ich die Wurzeln gefunden habe mit Feind, vergleiche ich, welcher der Bäume ist denn der kleinere? Weil es I der kleinere ist, dann wird I das Kind zu J.

8:31 Das heißt, I zeigt jetzt auf J. Und ich muss natürlich die Größe von J aktualisieren, indem ich die Größe von I dazu zähle. Und an der Stelle ist jetzt die Größe von I nicht mehr aktuell. Es ist nicht mehr die ganze Zusammenhangskomponente, sondern nur der Teilbaum. Aber das ignorieren wir in Zukunft. Deswegen können wir uns sparen, das zu berechnen. Und der andere Fall ist symmetrisch. Wir machen jem Teil von I, zu einem Teilbaum von I.

9:08 auch da noch mal die Frage an Sie, ohne dass ich Ihnen dazu was gesagt habe. Wenn wir das immer so machen, also in Union ein bisschen mehr Arbeit machen, nämlich eine cleverere Art der Reihenfolge wählen, welcher Baumteil von welchem wird, was bedeutet das dann für Feind oder die Höhe der Bäume anders ausgedrückt?

10:07 Auch hier hätte ich noch ein paar mehr Antworten einstreuen müssen. Damit das irgendwie Sinn ergibt, muss es ja besser als linear sein. Das heißt, dass das Feind jetzt langsamer wird, dann wäre das Ganze irgendwie widersinnig und schneller gibt's ja nur diese drei Optionen. Welche könnte es sein?

10:41 noch jemand aktiv beim Denken und Tippen oder sollen wir erstmal auflösen? Also, es gibt äh geteilte Meinung, aber tatsächlich ist die die mittlere Lösung richtig logarithmisch, was exponentiell besser ist als vorher, wenn Sie wollen. Ist also eine dramatische Änderung von dieser kleinen Verfeinerung, wie wir dieses Union Find äh wie wir das das Union implementieren.

11:11 Und das wollen wir uns kurz überlegen, warum ist das so? Also noch mal die Analyse. Äh Feind ist im wesentlichen die Tiefe des Baumes oder die Tiefe von dem konkreten Knoten, bei dem ich loslaufe, aber im schlimmsten Fall bin ich am am tiefsten Blatt. Äh und Union hat immer noch konstante Zeit. Ich habe zwar ein bisschen mehr Aufwand mit den Größenberechnung und dieser Fallunterscheidung, aber immer noch konstante Zeit.

11:36 Also die Höhe der Bäume ist das Spannende. Die Behauptung ist in diesem, wenn ich äh beliebige Operation Union Find ausführe, habe ich immer Bäume der Höhe höchstens Logarithmus zur Basis 2 von n. Warum ist das so? Na ja, wann kann denn überhaupt nur die Tiefe von dem Objekt oder die Höhe von dem Baum steigen? Nur bei Union. Das ist der einzige Teil, wo dieser rechte Teilbaum, der jetzt ein Kind wird, ein +1 in der Höhe bekommt.

12:13 Damit das passiert, muss aber das hier der kleinere von den beiden Teilbäumen gewesen sein, Logo, sonst hätten wir den anderen runtergehängt. Das bedeutet aber für den Gesamtbaum, den wir hier gebaut haben, dass dessen Größe größer ist als dieser hier. Okay, sonst wären wir wieder in dem anderen Fall. Wie oft kann ich also für einen bestimmten Knoten X die Höhe vergrößern?

12:39 Dafür müssen wir uns anschauen, was ist die Größe von der Zusammenhangskomponente zu der x gehört, wenn diese Höhe um 1 größer wird. Und die war vorher hier t1, bevor dieser gesamte Teilbaum dann in einem anderen Schritt noch mal Teil von was wird. Dafür muss dann ja dieser Teil hier noch größer sein als das, was wir gerade gebaut haben. Das was wir gerade gebaut haben, ist aber mindestens doppelt so groß wie das hier, denn das ist die Vereinigung von diesem und diesem Teil und der linke war ja noch größer als T1. Also nach einem Höhen äh Zuwachs für diesen Knoten X muss sich die Größe seiner Zusammenhangskomponente verdoppeln. Und das gilt für jeden Höhenzuwachs. Bevor X noch mal in der Höhe äh oder in so sagen Baum nach unten rutschen kann, dass der ganze Baum noch mal nach unten rutscht, muss ich jeweils die Größe verdoppeln. Und die Größe der Zusammenhangskomponente kann sich aber nur so oft verdoppeln, wie wir Platz haben für Elemente.

13:43 Das heißt, nach äh 2 hoch k Verdopplungen muss ich immer noch kleiner sein als mein groß n. Das bedeutet kie mehr sein als zweier Logarithmus von n.

14:02 Das ist alles, das ist der Beweis. Und das bedeutet, die Bäume sind nie höher als log n. Das bedeutet, die Laufzeit von Feind ist nie mehr als logarithmisch in der Anzahl Objekte.

14:11 Das ist an der Stelle ein einfaches Argument. Rein lokal ist aber was, was man in Datenstrukturen immer und immer wieder verwendet. Dadurch, dass man erzwingt, dass was schlechtes nur passiert, wenn ich es in der kleineren von zwei Dingen äh passieren lasse, kann ich erzwingen, dass es nicht allzu oft passieren kann.

14:36 Damit haben wir ähm für unsere Tabelle mit den Operationen überall, wo Feind verwendet wird, logarithmisch für die schlechteste mögliche Höhe in von so einem Baum. Also alles, was hier auch Lock hat, verwendet im wesentlichen Feind. Union ansonst, abgesehen von den Feindrufen, die es macht, hat immer noch konstanten Aufwand.

14:57 Das war die erste Optimierung. Sie erinnern sich, wir haben die Höhe der Bäume jetzt begrenzt. Ich hatte auch noch was erzählt von diesem Mittelwert zwischen ähm Arbeit immer verlagern und Arbeit immer sofort machen. Wir machen immer noch die Arbeit im Wesentlichen in Feind. Wir haben immer noch ähm möglichst viel Arbeit delegiert. Wir haben nur das bisschen Arbeit, das wir in Union machen, ein bisschen cleverer gewählt. An der Stelle könnte man aufhören. Ähm habe ich ähm aber die Implementierung nicht dabei. Ich glaube, aus Zeitgründen machen wir ähm zweite Optimierung gleich mit, aber das hier wäre schon für unsere Eingabegröße mit dem Large schnell genug, dass es in einer Minute oder vielleicht wenigen Sekunden fertig wird.

15:48 Der zweite Teil ist eine clevere Idee, die daher kommt, dass wenn ich ein Objekt habe hier unten X und auf dem Feind aufrufe, dann laufe ich diesen Pfad nach oben bis zur Wurzel sowieso ab, um dann festzustellen, aha, der Repräsentant für die neuen ist null. Wenn ich diesen Aufwand eh schon mache in Feind hier hochzulaufen, dann kann dich doch für die Nachwelt, für zukünftige Aufrufe die Welt ein bisschen verbessern, indem ich alle Knoten, die ich dazwischen auf dem Pfad finde, direkt zu Kindern der Wurzel mache. Oder anders ausgedrückt, ich aktualisiere für all diese Knoten auf dem Fad nach oben, da aktualisiere ich dieses ID Array einfach auf null und dann sind die direkt oben. Wenn also das nächste Mal jemand z.B. nach der sech fragt, steht da direkt drin null und ich muss nicht noch mal diesen Pfad wieder ablaufen. Das heißt, ähm, wenn man das explizit so macht, das habe ich ähm auch dann in meinem Code so gebaut, kann ich an der Stelle vielleicht zeigen die Lösung.

16:54 Ja, der ist immer noch fleißig dabei. Ich denke, wir brechen es mal ab. Wir haben die Hälfte geschafft jetzt, aber sie erinnern sich, das wird immer langsamer. Das wird wieder nichts.

17:11 Also hier ist Code, der das ähm diese beiden Tricks implementiert. Einerseits gibt's hier jetzt ein Size Array. Das wird am Anfang auf eins gesetzt, solange jedes Element seine einzelne Zusammenhangskomponente ist. Und in Union habe ich jetzt hier diese diesen diese Fallunterscheidung nach der Größe, genau wie es auf den Folien war. Ansonsten ändert sich nichts. Ähm es gibt hier so ein ein Sonderfall. Wir müssen jetzt anders als vorher tatsächlich aufpassen, dass wir dieses Update hier nicht machen, wenn Union gar keinen Effekt hat. Wenn die beiden schon verbunden sind, dann sollte ich nicht noch mal die Größe aktualisieren.

17:53 In Feind mache ich jetzt einmal den alten Aufruf, also diese Schleife, die mit meinem Wert bis zur Wurzel hochläuft. Das ist der Code, den Find in Quick Union vorher schon hatte. Den habe ich ausgelagert in eine neue Methode, damit wir den hier aufrufen können. Und dann muss ich noch mal die gleiche Schleife durchlaufen. Jetzt wo ich die Wurzel kenne, kann ich nämlich dann alle Einträge direkt auf R setzen.

18:19 Also, ich muss diesen Pfad zweimal ablaufen. Ich laufe einmal hoch, um die Wurzel zu finden und ich laufe noch mal hoch, um die das Update zu machen, alle auf direkt die Wurzel zeigen zu lassen. kann ich an der Stelle äh nicht direkt in einem Durchgang machen. Und um zumindest das noch zu demonstrieren, wir müssen natürlich den auch verwenden.

18:48 Also auch hier ähm jetzt haben wir weited Quick Union Find statt dem bisherigen Waited eben wegen dem Gewichte wählen in Union. Dann kompilieren wir das und machen wir direkt das große. Was soll's? Und sie sehen schon direkt, dass es viel viel schneller läuft.

19:20 Auch das wird mit der Zeit ein bisschen langsamer, weil auch da die Bäume über die Zeit etwas höher werden, aber eben nur logarithmisch. Und jetzt am Ende wird's schnell, weil dieses Pfadkomprimieren natürlich gegen Ende. Irgendwann habe ich die meisten Pfade schon kurz gemacht. Das heißt jetzt hier, okay, 17 Sekunden, das war auch doppelt so schnell ohne die ähm extra Last hier mit äh Livestream und Co. Also, ich habe das so implementiert, wie es hier auf den Folien ist. Ähm, es gibt eine clevere Variante, die Satwick und Rain da verwenden, statt dass man, das hier war mein Code, diese zweimal über den Pfad laufen. Man kann noch ein Quännchen schneller sein, zumindest ähm für diese konkreten Beispiele, indem man nicht wirklich zweimal drüber läuft, sondern immer nur ähm einen Pointer auf den Großvater zeigen lässt und das für alle macht, dann halbiert man die Tiefe für alle, dass man die Tiefe auf eins setzt. Das ist theoretisch ein bisschen schlechter, aber dafür habe ich eben nur eine Weil Schleife, nicht zwei. Das ist aber so ein bisschen ähm extra Tricks für äh für die für die Profis, die das vielleicht spannend finden. Das würde ich nicht als so essentiell ansehen.

20:39 Jetzt kann man analysieren, wie lange das dauert, wenn man diese da zwei Dinge zusammenbringt, denn diese äh worst case Tiefe von den Bäumen, das logarithmisch, was wir uns überlegt hatten, das war ja bevor wir diese Pfadkomprimierung hinzugefügt haben. Jetzt ist es so, wenn ich viele Feindaufrufe mache, dann werden die über die Zeit billiger, hat man in der Ausführung auch gesehen. Gegen Ende wurde das rasend schnell, weil fast alle Pfade ganz kurz sind. Das heißt, diese diese logarithmische Oberschranke, die gilt, wenn ich nur Union Aufrufe mache, aber selbst Union macht ja zwischendrin Feind und die komprimieren die Pfade. Also vielleicht erwartbar, dass man da auch eine bessere theoretische obere Schranke finden kann. Und an der Stelle, da geht die Analyse und die Mathematik weit über das hinaus, was wir im ersten Jahr je machen wollen. Aber als Ergebnis will ich zitieren, was dabei rauskommt. Äh man kann eben jetzt zeigen, dass wenn man äh eine Folge von solchen Union oder Feindoperationen ermcht, die diese Pfadkomprimierung vornehmen und dazu das Weited Union verwendet, dann ist die Gesamtzeit ähm m mal also für m Operation und eine Operation kostet log n. Was ist das denn? Was ist logstern? Logstern ist die Funktion, die angibt, wie oft muss ich den Logarithmus auf eine Zahl anwenden, bevor ich kleiner als 1 bin. Und hier ist eine Tabelle, wo aufgezählt ist, wie was die Werte von log Stern von den paar Zahlen sind.

22:13 ähm am Anfang hier ein paar zweier Potenzen, da wächst das relativ schnell, aber die nächste ist dann schon deutlich größer. Und dann habe ich als nächstes, also ich muss immer ähm die letzte Zahl nehmen und zwei hoch diese Zahl nehmen, um eins größer zu werden, den Logstern. Unfassbar langsam, wie dieses Logstern wächst. Und dann kann man noch einen drauf setzen. Sie werden wahrscheinlich von der Ackermannfunktion in der theoretischen Informatik noch hören. Das ist eine Funktion, die wächst so unfassbar schnell, dass man sie gar nicht hinschreiben kann, sondern nur rekursiv. Und Alpha ist die inverse Funktion davon. Die wächst noch langsamer als dieses Logstern. Ähm, ich belasse es bei diesem Ausdruck faszinierende Mathematik, die da dahinter steckt, die Sie natürlich nicht verstehen müssen, um dieses Union Feind zu verwenden. Ähm, aber es ist spannend zu sehen, dass man tatsächlich diese durch diese Pfadkomprimierung unfassbar starke Garantien bekommt, wie lange eine Folge von Operationen brauchen kann. auch da wieder einzelne Feindoperationen am Anfang könnten teurer sein. Die müssen vielleicht dieses Logen, aber dann, wenn ich viele von denen hintereinander mache, dann sind in Summe die meisten günstig.

23:27 Das ist so die Message. Ähm spannende weitere Theorie, wo dann so ein bisschen die reinenfall Algorithmthorie reinkommt. Man kann beweisen, dass es auch für dieses Problem keinen Algorithmus gibt, der dieses Logstern durch eine Konstante ersetzt. Das ist noch viel weiter weg von dem, was ich Ihnen erklären kann, was dahinter steckt. Da braucht man viel viel mehr Vorarbeit, aber das Ergebnis können wir auch wieder mitnehmen. Das heißt, dieses Fahkomprimieren ist in gewisser Sinn, in gewissem Sinne ein bestmöglicher Algorithmus für dieses Union Find Problem. Wir können da für konkrete Implementierung in der Praxis kann man immer ein bisschen äh noch clevere Tricks in den Details rausholen, aber für das Wachstum, wenn ich die Eingabe größer mache, bin ich im Wesentlichen damit beim Optimum. Ich weiß, es geht nicht wirklich besser und ich erreiche diese absurd langsam wachsenden Funktionen.

24:33 das ist noch mal die Zusammenfassung. Ähm, damit kann man eben auch diese großen Instanzen, die vorher irgendwie 30.000 1000 Jahre oder was absurd lang gebracht haben.