Video 4-4: Quick Union

0:03 Quickfind war nicht schnell genug. Braucht quadratische Zeit, läuft noch im Hintergrund. Wird ungefähr 13 Minuten dauern, wenn na ja, ich habe es getestet, ohne dass hier die ganze Livestream Geschichte noch nebenher läuft. Wahrscheinlich eher länger. Mal schauen, ob wir es fertig äh werden sehen. Wir müssen es irgendwie schneller hinkriegen. Das Hauptproblem, der Bottleneck für die Performance war eindeutig Union.

0:26 Da hat wir immer die Iteration über das ganze Array. Also klarer Fall, wir müssen Union schneller machen. Was können wir da besser machen? Wir könnten z.B. versuchen, diesen irren Aufwand über die ganze über das ganze Array zu iterieren, nur um einige wenige Zellen zu aktualisieren anzugehen. Das ist nämlich was der Code hier tut. Quick Union hat ähm diese Iteration.

0:53 Dann mache ich überall diesen Vergleich, aber eigentlich aktualisiere ich nur die, die tatsächlich diese Komponente von P vorher hatten. Das ist eigentlich ein bisschen verschwenderisch.

1:08 Leider hilft das nicht wirklich. Man könnte das versuchen und dann bräuchten wir eine Datenstruktur, um es irgendwie nur die Elemente zu merken, die in unserer Zusammenhangskomponente sind. Aber ich spare mir das hier, denn dieser Ansatz ist im Wesentlichen nicht eine richtige Lösung. Äh, das funktioniert am Anfang, solange diese Komponenten klein sind. Wenn ich das aber lange betreibe und die Komponenten groß sind, dann hilft es nicht, [räuspern] denn ich muss ja alle IDs aktualisieren, die zu dieser Komponente gehören. Sonst kann ich meine Invariante vergessen mit dem Find liest einfach die ID aus. Und ich kann das auch relativ schnell provozieren mit einem Worst case input. Äh, wenn ich immer mit dem ersten Element Union aufrufe, dann wächst mit jedem Union Aufruf diese erste Komponente um ein Element. Dann kriege ich relativ schnell große Komponenten und benutze die immer wieder. Eventuell muss ich ähm wir hatten ja eine Asymmetrie im Code, welche welcher iteriert wird. Eventuell muss ich eins und vier hier tauschen. Äh, aber das es diesen Westcase gibt, können wir nicht ähm loswerden.

2:10 Also, der Ansatz funktioniert nicht. Wir brauchen was radikal anderes. Sprich, unsere Invariante ist tot, dass wir in einem Array fest speeichern, die diesen Repräsentanten für die Zusammenhangskomponente. Das tut nicht. Stattdessen machen wir was anderes. Wir äh sind mal möglichst möglichst faul. Wir haben immer noch ein Array mit diesen ähm IDs äh auch wenn der Name vielleicht jetzt nicht mehr so gut passt. Äh, stattdessen ist die ID jetzt ein Vater in einer Baumstruktur und die eigentliche ID ist die Wurzel von diesem Baum. Wenn ich also den Feind für drei aufrufe, dann laufe ich hier nach oben, bis ich bei der eindeutigen Wurzel angekommen bin. Und das ist mein echter Repräsentant. Die anderen dazwischen, das sind sozusagen nur Vorgesetzte irgendwo im mittleren Management.

3:06 Feind ist also jetzt solange ID von sich selbst aufrufen, das Ergebnis von ID wieder als Index in ID stecken, bis es nicht mehr geht, bis ich an der Wurzel angekommen bin. Und wir werden das dann so initialisieren, dass sozusagen die neuen ihr eigener ihre eigenes ihr eigener Elternteil ist. Singular von Eltern ohne Gendern geht nicht. Ähm das heißt hier terminiert diese Schleife, weil neuen auf sich selbst wieder zeigt. Das ist die Idee. Ähm hier ist das Array, was diese ähm Zwischendarstellung hier repräsentiert. Sie sehen die die 7 und die 8, die zeigen auf sich selbst und die neun und auch die 0 und die 1. Dagegen ähm zeigt die 2 auf die 9, das ist diese Kante. Und die vier zeig die vier zeigt auf die neun und die drei zeigt auf die vier. äh müsste ich vielleicht mit Pfeilen malen, sonst ist nicht klar, welche Richtung gemeint ist. Das heißt, die Repräsentanten sind hier die auf sich selbst zeigen, bzw. der nicht die Wurzeln von diesen Baumstrukturen hier. Feind ist also jetzt ein bisschen teurer potenziell. Ich muss da ähm bis zur Wurzel hochlaufen. Dafür ist Union jetzt ganz einfach. Wie kann ich denn Union machen?

4:23 Union mache ich einfach eine bisherige Wurzel zu einem neuen Kind. Und dann führt jeder Pfad, der vorher bei dieser Wurzel endete, jetzt weiter zur neuen Wurzel. Deswegen heißt es hier auch der äh der faule Ansatz für Union Find. Ich mache so wenig Arbeit wie möglich bei dem Union Aufruf und verlagere all die Arbeit auf später, wenn Feind kommt.

4:54 Kleines Detail hier, wie könnte man das mit den Bäumen machen? Da hat man ziemlich viel Freiheit. Wir könnten hier diesen Baum mit der neuen auch unter die fünf hängen. Das wäre auch korrekt. Ist aber irgendwie bescheuert, denn ich will ja möglichst schnell zu der Wurzel. Das heißt, ich werde tunlich versuchen, die Wurzel von dem einen Baum, von der neuen, die ich hier vereinige, zur zu einem neuen Kind von der Wurzel des anderen Baums zu machen. Das heißt, die neu zeigt auf den Repräsentanten von der anderen Gruppe statt irgendwo weiter unten in den Baum. Auch wenn das andere auch korrekt wäre, ist immer langsamer.

5:38 Okay, auch das sehen wir erstmal noch in Aktion, bevor wir zum Code kommen. Also, hier ist wieder ein Aufruf. Ähm, es wären immer alte Bäume an die neuen Bäume als Kinder der Wurzel angehängt. Am Anfang sieht man das nicht so gut, weil die Bäume alle sehr klein sind. Wenn dann mal was spannendes passiert, dann sehen wir immer noch nicht so wirklich spannend hier. Die sieben hätte auch unter die zwei gekonnt, aber das machen wir nicht. Und hier entsprechend auch wir machen immer den Aufruf den einen Baum zum neuen Kind der Wurzel des anderen Baums.

6:31 Okay, das war am Ende der Baum. Das heißt natürlich auch, wenn ich jetzt Feind von sechs aufrufe, muss ich eine Weile Berg auflaufen, bis ich den Repräsentanten gefunden habe.

6:43 In Codes sieht das so aus, wir haben immer noch ein Array für jedes Element, aber die Bedeutung von diesem Array ist jetzt sehr anders. Beind muss das Array iterieren, bis der Index und der Eintrag da das gleiche sind, also bis ich auf mich selbst zeige. Das ist die Erkennung von der Schleife, die ich vorhin gemalt hatte. Solange das noch nicht der Fall ist, setze ich i auf den B, die Mutter von I selbst und am Ende gebe ich das I, was ich so gefunden habe, zurück. Dafür ist Union jetzt deutlich einfacher. Die Initialisierung ist genau wie vorher, hat sich nicht geändert. Äh, Union ist deutlich einfacher. Ich finde die beiden Repräsentanten und mach den einen zum Kind des anderen.

7:31 Hatten wir im Beispiel auch schon gesehen. Jetzt aber ist das jetzt besser. Also, wie lange dauert einzelner Feindaufruf in dieser neuen Implementierung? Union ist jetzt definitiv Konstantzeit, wenn wir dann den Aufruf an Feind ignorieren. Also Union bemüht natürlich Feind, um zu arbeiten, aber der Rest, der echte Unionteil ist sozusagen konstante Zeit. Aber wie lange dauert Feind?

8:22 Hier unser Quickfind ist übrigens immer noch fleißig am machen. Ähm das mit den 13 Minuten wird glaube ich nichts. Das liegt dann doch daran, dass der Laptop mit anderen Dingen nebenher beschäftigt ist.

9:05 soll auch keine eine Gedächtnisübung sein. Ich zeige Ihnen lieber den Code. die Frage haben sie auch auf ihren Geräten. Paar mehr Antworten hatten wir vorhin. Machen Sie ihr Kreuzchen, wenn Sie nicht sich festlegen können. Ich hätte vielleicht noch eine Antwortmöglichkeit ähm dafür vorsehen können.

9:52 Ansonsten schlage ich vor, wir lösen mal auf. Also eine deutliche nicht absolute Mehrheit, aber deutliche Mehrheit spricht sich für Linearzeit aus. äh ungefähr so lang wie die Anzahl Objekte ist, ne? Falscher Knopf, den hier wollte ich und das ist auch korrekt. Im schlimmsten Fall muss ich eben damit rechnen, dass so ein äh Feindbaum eine komplette lange Liste von solchen Kindbeziehung ist. Um den zu bauen, kann man so ein bisschen überlegen, ob das wirklich äh tatsächlich passieren kann. Äh aber kann es schon. Also äh kann man basteln und wenn nicht der ganz schlimmste Worstcase, dann reicht ja auch, wenn es etwa in die Nähe kommt. Definitiv ist also auch unser ähm unser Quick Union noch nicht die äh die endgültige Lösung. Wenn man auf diese Tabelle hier schaut, ist es in gewissem Sinne sogar schlimmer, weil auch Feind ja einen Aufru auch Union einen Aufruf von Feind macht. Wir haben zwar Union eigentlich beschleunigt in dem, was es tut an Änderungen, aber um zu bestimmen, welche Änderung wir machen, rufen wir Feind auf. Und da ist das äh da ist das malur schon passiert.

11:15 Das hier läuft immer noch. Wir waren jetzt etwa halb durch. Ich denke, wir belassen es mal dabei. In der Hälfte, für die Hälfte haben wir schon 16 Minuten gebraucht. Das zeigt ihnen, dass ähm Laufzeitmessungen auf Laptops so eine Sache sind, je nachdem welches Energiesparprofil aktiv ist und ich muss den Energiespar setzen, damit mir der nicht zu heiß läuft hier. So ein bisschen äh je nachdem, was man da einstellt und was noch nebenher läuft, unterscheidet sich die Laufzeit teilweise schon dramatisch. Ich habe der Vollständigkeit halber auch das Quick Union hier noch äh dabei. Also auch hier der Code. Im Wesentlichen sollten Sie nur den ersten Teil sich anschauen. Das Count ist genauso wie vorher. Das zählt die Zusammenhangskomponenten äh können Sie erstmal ignorieren und wir müssen unsere ähm unseren Aufruf hier nur an einer Stelle ändern. Und das ist auch noch mal so eine Illustration. Ich hätte jetzt da noch ein Interface haben können. Das ist nur eine Änderung. Tatsächlich sind aber diese zwei Klassen vom Interface identisch. Das heißt, wenn ich hier aus Quick Find ein Quick Union mache und hier entsprechend auch, dann funktioniert der gleiche Code nach wie vor und verwendet jetzt diese andere Klasse.

12:38 Heiß, wir kompilieren noch mal und wir können ja noch mal mit dem kleinen anfangen. Das sollte jetzt hoffentlich das Ergebnis das gleiche sein. Die Laufzeit ist ähnlich. Dann noch mal hier mit dem mittelgroßen. Laufzeit ist auch ähnlich. Und mit dem ganz großen äh sehen Sie schon anfänglich geht das super schnell, das ist klar, weil am Anfang auch die Bäume niedrig sind. Am Anfang ist Feind echt richtig günstig. Man sollte vielleicht auch dazu sagen, wir haben uns den Worst Case von Feind angeschaut. Wenn die Dinge gut laufen, dann sind die Bäume vielleicht nicht so hoch. Ähm, ich kann es ja auch im Hintergrund noch laufen lassen. In meinem Test vorab war das noch langsamer. Das sieht am Anfang nicht so aus und es ist wahrscheinlich die Eingabe ist nicht gezielt ein worst case, aber sie ist halt doch äh groß genug, dass über die Zeit diese Bäume so tief werden, dass das Feind unfassbar langsam wird. Und hier ist es irre führend zu sagen, ah, wir haben ja jetzt schon 600.000 Queries verarbeitet. Das heißt, ich extrapoliere linear, wie lange das am Ende dauert.

13:46 Mm. Die einzelnen Queries werden immer langsamer. Das heißt, da ist es gar nicht so leicht vorherzusagen, wie lange es dauern würde von diesem Schnappschuss aus.

13:57 Ja, lass wir die Kiste rauchen nebenher. Ähm kostet ja nichts. Äh mal schauen, wie weit wir da kommen. Das ist also auch noch nicht die Lösung.

14:09 Wir können noch kurz analysieren, woher das Problem jeweils kam. Das steht hier noch mal, hatten wir schon besprochen. Im Prinzip haben wir jetzt zwei Extremlösungen gebaut. Und äh keine von den beiden ist noch in in ihrer Reihenform zufriedenstellend.