Video 4-3: Quick Find

0:03 Die erste Implementierung für dieses Union Find, die heißt Quickfind, weil sie das Ziel hat, das Find möglichst einfach zu machen. Wie können wir das tun? Wir haben diese Nobjekte, die sind fest vorgegeben. Wir können die Anzahl von den Objekten nicht ändern. Das heißt, ich speicher mir einfach für jedes Objekt eine ID, welche Zusammenhangskomponente ist dieses Element Teil von und die gebe ich zurück in Feind. Billiger werde ich Feind nicht kriegen. Das ist die Idee. In Java Code. Da die Objekte die ersten Integer sind, kann ich einfach ein Array dafür verwenden. Das heißt, wir haben ein Integer Array ID und das enthält hier ist so ein so ein Schnappschuss. Da ähm sind jetzt aus jeder Zusammenhangskomponente mehr oder minder wahllos ähm ein Objekt ausgewählt als der Repräsentant. Das ist der, der die Standarte hochhält und diese ganze Gruppe repräsentiert. Und die Einträge sind also immer eins dieser drei Repräsentanten und bei der 0 steht die Null selbst, die sind ihr eigener Repräsentant. Bei der 3, die hier in diesem Teil ist, steht die 8, weil die acht der Repräsentant für diese Äquivalenzklasse ist. So ist es zu lesen.

1:19 Und wenn ich jetzt Find aufrufe, dann gebe ich einfach diesen Wert der das Arrays zurück. Das tut dann auch das Richtige, denn ihr so wie jetzt hier zumindest in diesem Schnappschuss die Werte gewählt sind, würde dann Feind von zwei Zahlen genau dann den gleichen Repräsentanten liefern, wenn sie in der gleichen Zusammenhangskomponente sind. Okay, soweit so einfach, denke ich. Jetzt müssen wir das natürlich auch äh aktualisieren, wenn wir einen Union Aufruf hatten. Also hier die Implementierung von Find gibt einfach das die ID zurück und connectet es auch einfach. Das einzige, was wir noch uns Gedanken drüber machen müssen, ist Union. Wenn ich also jetzt zwei Werte P und Q bekomme und ich soll die Zusammenhangskomponente von denen zusammenlegen, vereinigen, dann wähle ich mir eine davon aus. In dem Fall ist äh Q der der gewinnt nicht. Äh die Zusammenhangskomponente von Q liefert jetzt den Repräsentanten für die Zusammenhangskomponente von P. Das heißt, ich iteriere über dieses Array und wo immer vorher die Zusammenhangskomponente von P stand, schreibe ich jetzt die von Q hin. In dem Beispiel haben wir also 6 und 1.

2:34 Die Zusammenhangskomponente von 6 ist die 0. Das ist der äh After Union. Okay, hier ist für sechs war es die 0 und für die ein ist es die ein selber. Jetzt wähle ich hier äh iteriere ich durch meine Array, wo über vor überall wo vorher eine Null stand, schreibe ich jetzt eine einzig. Danach habe ich meine Invariante, also die die Eigenschaft, die hier diese Datenstruktur beschreibt, ist zu jedem Zeitpunkt, steht in dem passenden Array Eintrag die der Repräsentant der Äquivalenzklasse, in der sich dieses Element befindet. Und diese Eigenschaft, die ist, wenn wir einen Union Aufruf bekommen, erstmal verletzt, weil die Zusammenhangskomponenten jetzt zusammengelegt werden. Und mit dem Überschreiben der Werte habe ich die wiederhergestellt.

3:35 Dazu gibt's auch ein kurzes Video, indem man äh das einmal in Aktion sieht. Äh es geht relativ schnell. Also, was Sie sehen können, vielleicht ist äh wie die Kanten eingefügt werden und dann am Anfang geht noch rel passiert relativ wenig. Es wird relativ wenig überschrieben, weil die Zusammenhangskomponenten alle klein sind. Wenn mal eine größere Vereinigung kommt, so wie jetzt, dann wird eine ganze Reihe von Einträgen überschrieben. Das ist das Beispiel, was auf den Folien war.

4:16 Und das Endergebnis äh sieht dann eben so aus. Das ist die abstrakte Beschreibung. Jetzt wollen wir das auch in Java Code umsetzen und der ist dankenswerterweise ziemlich kompakt und und einfach. Wir haben also jetzt eine Klasse, die heißt Quick Find Union Find. äh als Erinnerung, dass wir immer noch dieses Union Find Problem lösen und sie finden da im Wesentlichen die Komponenten, die wir vorher auch schon hatten. Wir haben ein Array, das die IDs speichert. Das müssen wir im Konstruktor einmal initialisieren bzw. das das Array anlegen, allokieren. Das ist initial mit Nullen gefüllt. Das ist aber nicht was wir brauchen. Stattdessen schreiben wir an jeder Stelle in dem Array das Element selbst. Im in der im Ursprungszustand ist jedes Element in seiner eigenen Äquivalenzklasse. Sind alles singelen Mengen und erst über die Zeit werden die zusammen zusammengelegt. Das heißt initial ist jedes Element sein eigener Repräsentant. Bind gibt einfach den Wert des Errays zurück und Union bindet die zwei IDs, die die Repräsentanten der zwei Elemente, die wir vereinigen wollen. Und dann iteriere ich über das Array ID.

5:32 Und wann immer dort aktuell diese alte ID steht, die von P, schreibe ich jetzt die von Q hin. Okay, soweit so gut. Dann schauen wir mal, was sie denken, wie gut das funktioniert.

6:02 Sie können das jetzt nicht so richtig komplett wissen, aber sie können für diese einfache Implementierung vielleicht eine grobe Überschlagsrechnung machen oder zumindest so nach Bauchgefühl ähm überlegen, wie wie lange könnte sowas brauchen. Wir werden gleich sehen. Man kann das an der Stelle tatsächlich ganz gut äh vorhersagen.

6:46 Ja, wenn Sie noch am Tpen sind, zeige ich nur einmal kurz, ich habe das ein bisschen vorbereitet. Also, erstmal das Quick Find sieht so aus. Event im Wesentlichen gleicher Code. Ich habe nur noch eine Funktion hinzugefügt, die Sie ignorieren können, die zählt, wie viele Zusammenhangskomponenten wir haben. Das benutzt aber sortieren, was wir offiziell noch nicht gemacht haben. Also, der eigentliche Code, der uns interessiert, sind nur hier diese dieser Teil bis da.

7:24 hier ist der äh Aufrufcode. Das ist also das die gleiche Mainschleife, die die Mainmthode, die wir vorhin gesehen hatten. Äh ich habe noch eine Ausgabe hinzugefügt, die uns zeigt, wie viele Operationen wir schon ausgeführt haben. Dann können wir ein besseres Gefühl dafür kriegen, wie lange die Dinge so dauern.

7:45 Außerdem gibt's hier noch diese Eingabedatei, die auch auf den Folien war. Von der gibt's auch zwei größere Varianten noch. Es gibt einen Medium union Find, da sieht man schon nichts mehr.

7:58 Ähm, das hat Größe, sehen Sie hier, 625 Sites Objekte und dann eine ganze Reihe von äh Updates und es gibt einen noch größeres mit einer Million und dann 2 Millionen Einträgen. Das ist das Beispiel, auf das sich die Frage bezieht. Werden es also gleich dann auch mal laufen lassen. Mit Word Count minus lines kann ich zählen, wie viele Zeilen diese Datei hat. Das sehen Sie das 2 Millionen 1 eine für oben Sie Angabe 1 Million Objekte und dann 2 Millionen Zeilen mit Union Aufrufen.

8:36 So, dann wollen wir aber erstmal kurz auf die Abstimmung schauen. Breit gestreut. Also sie sind nicht der Meinung, dass das im Mikro oder Nanosekundenbereich gar ist. Äh, das wäre auch wäre schön. Ähm ansonsten ist die Streuung über viele Größenordnungen hinweg. Ich glaube, das kann man sagen. Ja, ich würde sagen, probieren wir es aus, oder? Also erstmal ähm um das zu kompilieren, muss ich wie immer meinen Class Path angeben mit dem Jar. Das kennen Sie schon. Dann würden wir Quick Find kompilieren und Dynamic Connectivity.

9:35 Ich führe das jetzt immer mit Time vorne dran aus. Dann sagt uns Unix auch noch, wie lange das gedauert hat und wir müssen nicht selber stoppen.

9:50 Und hier Dynamic Connectivity und ich pipe rein die ein die Datei, die wir einlesen wollen, z.B. für das Tiny. Da würden wir jetzt als Ausgabe erwarten alle Aufrufe, die nicht redundant waren, vorne dran noch die Operation, wie viele Operationen es waren und am Ende wie viele Zusammenhangskomponenten es gab. Und da wir das Beispiel auf den Folien hatten, können wir das noch mal überprüfen. Äh, das ist nicht das Beispiel, gell?

10:36 Ja, sorry doch, ich habe mich falsch erinnert. Das das Beispiel ist schon das hier. Das heißt, die Anzahl Zusammenhangskomponenten am Ende ist 2. Diese beiden Junk. Also es ging auf jeden Fall schnell 0,1 Sekunden sowas mit den Dreh und der davon ist der Großteil einfach nur Java starten. Also das äh ist so ein bisschen für die kleinen Eingaben kann man nicht sinnvoll messen. Dann sehen Sie, wir haben eine Operation 0 1 2. Okay, ich habe nämlich bei 0 angefangen zu zählen, wie man das so macht und die Anzahl Komponenten am Ende ist 2. Das hat schon mal funktioniert. Jetzt können wir das eins größere machen mit Medium. Das waren ja 625.

11:21 ist ein Ticken langsamer, ne? Hat man gespürt, aber äh auch immer noch nicht gigantisch unterschiedlich. Dann machen wir jetzt noch das large. Dann schauen wir mal.

11:36 Äh was ich hier schon sehen können, man sieht hier unten gerade noch so die Anzahloperationen hochzählen. Der Zähler, der soll bei 2 Millionen ankommen. Ich glaube, wir machen mal nebenher weiter, ne?

11:56 Also, die ersten paar ähm sind schon mal raus. Vielleicht ist es noch das hier oder ist es noch viel viel schlimmer. Dann würde ich vielleicht doch abbrechen, bevor das zu Ende geht. Habe ich schon hier äh nicht aufgepasst. 13 13 Minuten war, was ich daheim gestoppt habe. Aber lassen Sie uns rechnen, warum das ungefähr die richtige Größenordnung sein sollte. Also erstmal ähm macht es hier das Leben bisschen einfacher, nicht zu sagen, ja, ich zähle jetzt exakt die Zyklen, die die CPU macht und so weiter. Das ist dann kompliziert und maschinenabhängig.

12:32 Habe ich sie ganz gut beschalt ohne Mikro. Ging auch so, gell? Was sagt ihr die letzten Reihen schon besser mit oder wurscht? Indifferent. Äh, ich kann es auch dazu halten. Macht macht äh keinen großen Unterschied. Muss man dran denken. Wir zählen hier, wie oft wir auf einen Array zugreifen, lesend oder schreibend. Wenn Sie sich die Implementierung noch mal anschauen, viel mehr passiert da einfach nicht. Äh, Find ist ein Array Zugriff lesend und Union sind ein paar schreibende Zugriffe und noch mal auch lesend. Also, wir lesen alles und schreiben ein paar davon. Wenn wir also die Anzahl der Rate Zugriffe zählen, dann ist es um und bei das, was die Algorithmen hier tun müssen.

13:16 Und wenn man das zählt, einfach im Code initialisieren. Ich schreibe in jedes in jede Zelle I selber rein. Find liest eine Zelle aus, connected liest zwei aus, würde ich mal sagen. hier das ein bisschen geschummelt, aber ähm von der Größenordnung, da steht ja auch Order of Growth, also wenn man konstante Faktoren ignoriert, ist zwei natürlich gleich wie eins. Und das Hauptproblem ist Union. Wir machen ja 2 Millionen Aufrufe von Union und jeder davon liest das Array komplett. N ist auch eine Million. Das heißt, um und bei habe ich 2 Millionen mal 1 Million. Das sind wir in den äh Billionen und ähm das ist schon eine Menge in kompakter Form ausgedrückt. Allgemein brauche ich von der Größenordnung um und bei n Quadrat Zugriffe, wenn ich n Objekte habe und n Union Operationen habe. In unserem Fall ist sogar 2n Union. Wie kann ich das umrechnen in Laufzeit? Klammer auf, wenn Sie dazu sehr viel mehr im Detail wissen wollen. Gibt's ein gab's einen schönen eingeladenen Vortrag im letzten Winter von Orson Peters, den Sie auf YouTube finden. Da hat er alles, was hier steht, sozusagen in in einer halben Stunde sehr viel mehr im Detail ausgebreitet. Wir belassen es mal bei einer ganz ganz groben Rechnung.

14:36 Um und bei brauchen Rechner eine Nanosekunde pro Befehl oder sie schaffen 2 hoch 9 Befehle pro Sekunde. Das ist eine eine Milliarde. Und sie haben auch ungefähr so viel Speicher. Das heißt, witzigerweise über die ganze ähm Zeit, die wir Computer so haben, ist um und bei wahr, dass man den ganzen Speicher einmal anfassen kann in etwa einer Sekunde. Ähm, das ist eine ganz ganz große Lüge, weil es die Speicherhierarchie ignoriert. Wenn wir aber in einem Takt auf einen Wort im Speicher zugreifen könnten, dann wäre das wahr. Und zumindest diese Relation von wie schnell ist die CPU und wie viel Speicher habe ich, die ist relativ konstant geblieben. Wenn man dann so ein bisschen rechnet, ähm 10 noch 9 Union Commands, das ist größer als wir haben. Wir haben 10 noch se nicht. Ey, Millionen ist nicht ganz so brutal. 10 hoch 18 wird nicht fertig, quasi niemals.

15:38 Äh auch unserers mit wir haben etwa 10 hoch 6 ist unser n und wir machen 2 x 10 hoch 6 viele Operationen. Wenn wir das durch 10 noch 9 teilen, für viele Sekunden brauche ich dann Kopfrechen ist natürlich schwierig, aber Gott sei Dank ist es hier 12 - 9 etwa 2000 Sekunden. Ja, das sind so eine Größenordnung von Dutzend Minuten passt ungefähr. Wenn man es genauer wissen will, muss man natürlich auch genauer auf die Hardware schauen, aber so um und bei wird das hinkommen. Und wir können ja mal zwischendrin immer wieder reinschauen. Wir haben noch nicht mal Halbzeit.

16:32 diese Art von Überschlagsrechnungen. Sekunden. Diese Art von Überschlagsrechnungen, die sollten Sie immer wieder auch selbst anstellen, wenn Sie Dinge programmieren, auch ohne dass sie es vorher ausführen. Man kann natürlich jetzt auch Hochrechnung machen von wir lassen es mal eine Weile laufen und gucken, wie weit man kam. Äh, das hier ist aber deutlich robuster.