WEBVTT 00:04.960 --> 00:05.920 Guten Morgen. 00:06.100 --> 00:08.940 Mir fällt heute erst auf, dass wir hier zwei verschiedene Funkuhren 00:08.940 --> 00:10.300 haben mit verschiedenen Zeiten. 00:10.580 --> 00:14.080 Das ist etwas verstörend, aber ich glaube, die da stimmt. 00:15.500 --> 00:20.380 Lassen Sie mich beginnen mit einer kurzen Rekapitulation der letzten 00:20.380 --> 00:21.100 Vorlesung. 00:21.980 --> 00:32.060 Da hatten wir uns mit fortgeschrittenen Hashtabellen beschäftigt, die 00:32.060 --> 00:38.060 insbesondere gemeinsam haben, dass die Suchoperation in Worst-Case 00:38.060 --> 00:39.300 konstanter Zeit läuft. 00:39.400 --> 00:42.100 Das ist ja ein Unterschied zu dem, was wir in Algorithmen 1 00:42.100 --> 00:43.140 kennengelernt haben. 00:44.520 --> 00:50.380 Da hatten wir erwartet lineare Zeit für die Suchoperationen, aber es 00:50.380 --> 00:54.280 konnte halt passieren, dass viele Elemente kollidieren und man dann 00:54.280 --> 00:57.520 für einige Elemente auch mal länger suchen muss. 00:57.520 --> 01:03.440 Das ist zum Beispiel in Echtzeitsystemen nicht so schön und kann auch 01:03.440 --> 01:05.740 bei parallelen Algorithmen ein Problem sein. 01:06.320 --> 01:11.820 Wir hatten uns dann Cuckoo-Hashing angeschaut, ein besonders elegantes 01:11.820 --> 01:17.460 Verfahren, bei dem man eigentlich eine normale Hashtabelle hat und 01:17.460 --> 01:21.660 zwei Hashfunktionen und einfach die Invariante aufrechterhält. 01:23.220 --> 01:29.420 Jedes Element ist entweder an der Stelle abgespeichert, wo die eine 01:29.420 --> 01:33.300 Hashfunktion bestimmt oder an der die andere Hashfunktion bestimmt. 01:34.720 --> 01:39.480 Und der Trick war dann halt, dass eine Einfügeoperation etwas 01:39.480 --> 01:40.280 komplexer ist. 01:41.060 --> 01:44.780 Die muss dann Elemente durch die Gegend schieben, um diese Invariante 01:44.780 --> 01:45.660 aufrechtzuerhalten. 01:51.320 --> 02:00.350 Wir haben dann Varianten nicht kennengelernt, aber ich habe sie 02:00.350 --> 02:04.030 erwähnt, die das Ganze dann auch noch platzeffizient machen, wo man 02:04.030 --> 02:11.750 dann 90, 99 Prozent des Platzes der Tabelle ausnutzen kann, wenn man 02:11.750 --> 02:14.850 eine oder beide von zwei Tricks verwendet. 02:14.890 --> 02:19.490 Das eine ist, dass man sagt, die Hashfunktionen adressieren nicht 02:19.490 --> 02:27.030 einzelne Elemente der Tabelle, sondern Blöcke, sodass man daneben 02:27.030 --> 02:29.570 mehrere Elemente in einem Block unterbringen kann. 02:29.650 --> 02:30.790 Das hat zwei Vorteile. 02:34.310 --> 02:38.570 Erstens kann man halt einige Kollisionen direkt tolerieren und 02:38.570 --> 02:42.890 zweitens kann man beim Einfügen sich dann aussuchen, welches Element 02:42.890 --> 02:43.930 man rausschmeißt. 02:44.050 --> 02:47.410 Man kann sich vorstellen, dass das einen dramatischen Effekt hat, weil 02:47.410 --> 02:53.750 dann habe ich, wenn ich mehrere Sachen rausschmeiße, sondern sich 02:53.750 --> 02:55.850 schnell verzweigenden Baum von Möglichkeiten. 02:56.830 --> 02:59.750 Und das führt deshalb auch dazu, dass man selbst, wenn man kleine 02:59.750 --> 03:06.110 Blöcke hat, bereits dramatisch sich verbessernde Platzeffizienz hat. 03:07.050 --> 03:12.110 Und einen ähnlichen Effekt erreicht man dadurch, dass man mehr als 03:12.110 --> 03:13.270 zwei Hashfunktionen hat. 03:13.610 --> 03:16.310 Bei zwei Hashfunktionen habe ich immer nur eine Alternative. 03:17.450 --> 03:21.890 Bei mehr habe ich auch wieder so einen verzweigenden Baum von 03:21.890 --> 03:22.610 Alternativen. 03:23.230 --> 03:24.910 Man kann das Ganze auch kombinieren. 03:26.330 --> 03:29.210 Vielleicht schaffen wir es, dass in der Übung der Tobias Meier mal 03:29.210 --> 03:33.370 seine Variante vorstellt, die das nicht nur kombiniert, sondern auch 03:33.370 --> 03:38.530 mit einem zusätzlichen Trick dafür sorgt, dass man sehr feinkörnig 03:38.530 --> 03:40.850 dynamisch die Tabelle wachsen lassen kann. 03:43.050 --> 03:48.030 Dann hatten wir uns Zufallsgrafen angeguckt, die eigentlich eine 03:48.030 --> 03:50.530 ziemlich esoterische mathematische Geschichte sind. 03:51.130 --> 03:53.970 Vor allem, wenn man deren Eigenschaften analysiert, die aber 03:53.970 --> 03:57.270 tatsächlich genau das beschreiben, was für Cuckoo-Helgen gebraucht 03:57.270 --> 03:57.530 wird. 03:58.130 --> 04:01.950 Und diese mathematischen Techniken, die man da verwendet, verwendet 04:01.950 --> 04:04.050 man dann auch für diese Verallgemeinerungen. 04:04.470 --> 04:07.030 Da muss man natürlich auch ein bisschen mehr rechnen. 04:08.130 --> 04:12.710 In diesem Umfeld gibt es auch noch andere Varianten, dass man nämlich 04:12.710 --> 04:17.430 tatsächlich perfekte Hash-Funktionen baut, die man dann aber auf die 04:17.430 --> 04:19.090 Elementmenge zuschneiden muss. 04:19.410 --> 04:23.790 Oder eben bei diesem Dynamic Perfect Hashing, wo man so zweistufige 04:23.790 --> 04:31.370 Hashtabellen verwendet, wo man die Elementmenge dann dynamisch 04:31.370 --> 04:32.830 festlegen kann. 04:33.450 --> 04:38.730 Vielleicht noch mal zu diesen perfekten Hashtabellen, Hash-Funktionen, 04:39.030 --> 04:42.230 die die Hash-Funktionen auf die Elementmenge zuschneiden. 04:42.430 --> 04:45.370 Da brauche ich halt dann wenige Bits pro Element. 04:46.970 --> 04:52.230 Und das ist insbesondere dann spannend, wenn ich die Elemente selber 04:52.230 --> 04:53.630 gar nicht abspeichern muss. 04:54.370 --> 04:59.090 Zum Beispiel hat man manchmal Anwendungen, wo man eine Funktion 04:59.090 --> 05:01.370 abspeichern will oder sagen wir mal eine Wertetabelle. 05:01.650 --> 05:04.890 Sie haben eine Elemente und für jedes Element möchte man einen Wert 05:04.890 --> 05:05.390 haben. 05:06.390 --> 05:08.590 Die Elemente selber interessieren sie gar nicht. 05:09.370 --> 05:12.350 Aber sie wollen halt diese Wertetabelle für die Funktion abspeichern 05:12.350 --> 05:15.490 und sie wollen diese Funktion auswerten können in konstanter Zeit. 05:16.210 --> 05:19.370 Und dann kann ich eben tatsächlich... genau und dann ist es vielleicht 05:19.370 --> 05:22.190 noch so, dieser Funktionswert, das ist vielleicht auch wenig, nur ein 05:22.190 --> 05:23.270 paar Bits oder so. 05:24.010 --> 05:27.770 Dann können sie so eine perfekte Hash-Funktion nehmen, die irgendwie 05:27.770 --> 05:31.850 ein paar Bits pro Element braucht und die adressiert dann eine 05:31.850 --> 05:32.590 Wertetabelle. 05:33.370 --> 05:36.150 Und dann haben sie eine extrem kompakte Datenstruktur, wo sie die 05:36.150 --> 05:37.630 Schlüssel gar nicht mehr speichern müssen. 05:39.290 --> 05:44.670 Und da gibt es eine ganze Reihe Anwendungen von dieser Sichtweise. 05:45.330 --> 05:49.790 So, gibt es noch Fragen zu sehr platzeffizienten oder sehr schnellen 05:49.790 --> 05:50.290 Hash -Tabellen? 05:52.430 --> 05:56.430 Dann kommen wir jetzt dem nächsten Kapitel externe Algorithmen. 05:58.430 --> 06:02.710 Wir werden uns das vor allem anschauen in einem sehr einfachen Modell 06:02.710 --> 06:08.310 von Speicherhierarchien, das ich in der Einführungsvorlesung über 06:08.310 --> 06:11.530 Algorithmen Engineering auch schon vorgestellt habe. 06:12.510 --> 06:17.330 Wenn wir uns hier das obere anschauen, dann ist das im Prinzip das von 06:17.330 --> 06:19.350 Neumann - Modell für sequentielles Rechnen. 06:19.470 --> 06:24.850 Also wir haben einen frei programmierbaren Speicher, der von einer 06:24.850 --> 06:29.990 sequentiellen CPU zugegriffen wird, die halt immer beliebige Wörter 06:29.990 --> 06:33.470 aus dem Speicher liest, in konstanter Zeit Operationen darauf 06:33.470 --> 06:36.270 ausführt, auch wieder abspeichert. 06:37.610 --> 06:43.370 Das Neue ist jetzt, dass wir sagen, dieser frei zugreifbare Speicher, 06:43.430 --> 06:46.610 der hat begrenzte Größe und zwar M Maschinenworte. 06:47.970 --> 06:52.970 M ist ein Parameter dieses Modells und es gibt aber auch noch einen 06:52.970 --> 06:56.890 großen Speicher, den man aber nur blockweise zugreifen kann. 06:57.010 --> 07:01.390 Also immer Blöcke von B Maschinenwörtern und dann ist B halt der 07:01.390 --> 07:02.690 andere Parameter. 07:03.830 --> 07:10.990 Und viele Algorithmen, jetzt sage ich erstmal vielleicht, was man da 07:10.990 --> 07:11.710 modelliert. 07:11.790 --> 07:13.750 Das Schöne ist, damit kann man ganz viel modellieren. 07:15.250 --> 07:22.310 Die ursprüngliche Sichtweise war, das ist eine Festplatte, deshalb 07:22.310 --> 07:23.850 habe ich das so ein bisschen rund gemalt. 07:25.030 --> 07:26.170 Das ist der Hauptspeicher. 07:26.490 --> 07:30.550 Das ist auch immer noch relevant, aber das könnte zum Beispiel auch, 07:30.610 --> 07:34.390 das hier könnte auch der Hauptspeicher sein und das ist dann einer der 07:34.390 --> 07:38.210 drei Cache-Levels, die aktuelle Mikroprozessoren haben. 07:38.910 --> 07:42.910 Oder das könnte auch der L1-Cache sein und das ist der L3-Cache. 07:43.530 --> 07:46.450 Oder das könnte eine SSD sein und das ist der Hauptspeicher. 07:47.970 --> 07:51.790 Das kommt eben wirklich darauf an, wo jetzt in ihrer Anwendung der 07:51.790 --> 07:52.910 Flaschenhals liegt. 07:54.470 --> 08:01.650 Je nachdem guckt man sich halt die beiden Ebenen der 08:01.650 --> 08:04.430 Speicherhierarchie an, die gerade für die Performance wichtig sind. 08:04.950 --> 08:06.670 Und das ist jetzt ganz wichtig. 08:07.190 --> 08:11.270 Wir haben in realen Architekturen viel komplexere Speicherhierarchie. 08:12.490 --> 08:15.630 Ich habe aber in der Einführungsvorlesung schon gesagt, es hat 08:15.630 --> 08:21.010 eigentlich keinen Sinn, Algorithmen zu entwerfen oder zu analysieren 08:21.010 --> 08:28.190 in solchen sehr detaillierten Modellen, weil die Komplexität viel zu 08:28.190 --> 08:28.810 groß ist. 08:30.090 --> 08:33.870 Sie kriegen keine portablen Algorithmen hin, sie verstehen die Analyse 08:33.870 --> 08:36.350 nicht oder sie kriegen sie erst gar nicht hin. 08:38.030 --> 08:40.850 Das heißt, es ist wichtig eigentlich mit einfachen Modellen zu 08:40.850 --> 08:42.930 arbeiten und das ist ein sehr gutes Beispiel dafür. 08:43.490 --> 08:45.330 Und das möchte ich jetzt so ein bisschen mit Leben füllen. 08:45.670 --> 08:49.650 Ich werde Ihnen ein paar Algorithmen vorführen, die tatsächlich in der 08:49.650 --> 08:51.270 Praxis dann auch gut funktionieren. 08:52.150 --> 08:56.370 Und dann kann man eben sich später noch überlegen, wie genau 08:56.370 --> 09:00.130 implementiere ich die, damit ich das auf einer bestimmten Auswahl der 09:00.130 --> 09:03.830 Speicherhierarchie eben habe oder wie gehe ich jetzt damit um, dass 09:03.830 --> 09:05.930 ich in Wirklichkeit mehrere Prozessoren habe. 09:07.050 --> 09:09.190 Trotzdem sind die Grundalgorithmen dann die gleichen. 09:10.550 --> 09:11.650 Fragen zu dem Modell? 09:13.330 --> 09:13.730 Genau. 09:14.110 --> 09:17.290 Bei der Algorithmenanalyse ist es jetzt so, dass wir Blockzugriffe 09:17.290 --> 09:17.810 zählen. 09:19.190 --> 09:25.350 Das heißt, im Extremfall wird die Rechenoperation, die die CPU hier 09:25.350 --> 09:26.650 durchführt, zählen wir gar nicht mehr. 09:27.690 --> 09:29.210 Das ist auch eine Vereinfachung. 09:30.230 --> 09:35.750 Aber natürlich sollte man den Algorithmus dann sozusagen auch auf 09:35.750 --> 09:38.650 verschiedene Arten und Weisen analysieren, dass man nämlich zusätzlich 09:38.650 --> 09:42.550 vielleicht noch den internen Rechenaufwand zählt. 09:42.970 --> 09:46.030 Oder vielleicht auch noch andere Operationen, die mit anderen 09:46.030 --> 09:49.070 einfachen Modellen dann... 09:50.920 --> 09:51.680 Okay. 09:52.520 --> 09:56.240 Schauen wir uns mal einen ganz einfachen External-Memory-Algorithmus 09:56.240 --> 10:00.220 an, der aber schon eine dramatische Leistungsverbesserung bringt 10:00.220 --> 10:03.000 gegenüber einer naiven Implementierung. 10:06.080 --> 10:08.600 Wir wollen einfach einen Stapel implementieren. 10:08.720 --> 10:16.240 Also die Operationen PUSH und POP wird jetzt implementiert als eine 10:16.240 --> 10:16.700 Datei. 10:16.800 --> 10:23.320 Das sind diese blauen Dinger hier und zwei Pufferblöcke, die im 10:23.320 --> 10:24.220 Hauptspeicher sind. 10:24.840 --> 10:28.240 Man kann sich überlegen, dass zwei wichtig sind. 10:28.480 --> 10:32.840 Einer könnte in der Praxis funktionieren, aber es gibt 10:32.840 --> 10:34.860 Operationenfolgen, wo das nicht funktioniert. 10:34.860 --> 10:37.380 Können Sie sich mal überlegen, woran das liegt. 10:38.200 --> 10:42.960 Aber ich sage jetzt lieber, wie ich die Operationen implementieren 10:42.960 --> 10:43.320 möchte. 10:45.340 --> 10:53.220 Also die PUSH-Operation macht PUSH so lange in diesem Puffer, wie das 10:53.220 --> 10:53.500 geht. 10:54.440 --> 10:55.700 Also hier ist so ein Bild. 10:55.800 --> 11:00.000 In dem Fall ist jetzt die Pufferblock 1 voll, Pufferblock 2 ist halb 11:00.000 --> 11:02.920 voll und dann kann ich da halt ein weiteres Element reinschreiben. 11:03.020 --> 11:03.480 Alles gut. 11:04.020 --> 11:04.720 Keine IOs. 11:06.300 --> 11:08.620 Aber es könnte natürlich sein, dass beide Puffer voll sind. 11:10.000 --> 11:15.060 Dann wird der Puffer 1, also der, der hier weit weg von dem Top-of 11:15.060 --> 11:20.640 -Stack -Pointer ist, der wird auf die Platte geschoben und die beiden 11:20.640 --> 11:23.940 Puffer wechseln ihre Rolle. 11:24.420 --> 11:26.320 Also danach sieht es dann eigentlich so aus wie hier. 11:26.480 --> 11:33.060 Also ich habe, der Puffer 2 ist leer und der Puffer 1 ist halt in dem 11:33.060 --> 11:40.960 Fall dann voll, weil er ja gerade der zweite Block auch voll war. 11:41.060 --> 11:43.960 Das wird jetzt der erste Block und damit ist sozusagen mein Gesamt 11:43.960 --> 11:44.800 -Puffer halb voll. 11:49.000 --> 11:50.400 POP funktioniert so ähnlich. 11:50.540 --> 11:52.920 Das mache ich aus dem Puffer, so weit es möglich ist. 11:52.920 --> 11:59.300 Wenn beide Puffer leer sind, lese ich halt Puffer 1 aus der Datei und 11:59.300 --> 12:00.600 dann ist das Ganze wieder halb voll. 12:03.220 --> 12:03.460 So. 12:03.580 --> 12:05.980 Hat jetzt jemand eine Idee, warum man mit einem Puffer hier nicht 12:05.980 --> 12:06.540 auskommt? 12:07.660 --> 12:11.220 Also das ist so ein bisschen so ähnlich wie die amortisierte Analyse 12:11.220 --> 12:14.460 von wachsenden Arrays. 12:15.200 --> 12:18.480 Man könnte ja irgendwie die Situation haben, dass man immer 12:18.480 --> 12:27.600 abwechselnd Push- und Pop-Operationen machen, die dann jedes Mal eine 12:27.600 --> 12:29.080 IO -Operation erfordern. 12:30.100 --> 12:31.640 Also machen wir mal ein Beispiel. 12:35.260 --> 12:37.860 Also wir haben jetzt die Situation, wir haben nur einen Puffer-Block 12:37.860 --> 12:40.260 und der ist komplett voll. 12:42.300 --> 12:45.520 Und jetzt mache ich einen Push. 12:48.660 --> 12:49.620 Was passiert dann? 12:51.060 --> 12:55.020 Dann habe ich gesagt, ich schreibe das hier in den Hauptspeicher. 12:57.460 --> 12:59.160 Also kommt der hier auf die Platte. 13:00.280 --> 13:04.960 Und dann habe ich hier einen leeren Puffer und ein Element. 13:06.880 --> 13:07.700 Dann mache ich einen Pop. 13:09.340 --> 13:10.780 Dann habe ich einen leeren Puffer. 13:13.040 --> 13:14.260 Dann mache ich noch einen Pop. 13:16.700 --> 13:23.100 Dann muss er den vollen Block hier wieder reinlesen. 13:24.060 --> 13:25.880 Ich kann ein Element rausholen. 13:26.100 --> 13:26.920 Das sieht so aus. 13:30.060 --> 13:31.160 Dann mache ich einen Push. 13:34.580 --> 13:35.720 Dann ist er wieder voll. 13:37.220 --> 13:38.600 Und ich bin auch in der Situation. 13:41.580 --> 13:43.440 Und das immer abwechselnd. 13:43.720 --> 13:46.560 Also Push, Pop, Pop, Push, Push, Pop, Pop. 13:46.960 --> 13:51.380 Und ich habe jeweils für zwei Operationen eine IO-Operation. 13:52.380 --> 13:53.240 Das ist zu teuer. 13:54.120 --> 13:57.520 Und das kann man eben leicht umgehen, wenn man diese zwei Puffer 13:57.520 --> 13:57.980 verwendet. 13:58.040 --> 14:00.280 Die Details des Beweises möchte ich nicht vorführen. 14:02.300 --> 14:05.240 Aber das ist eine amortisierte Analyse, die eigentlich ganz analog 14:05.240 --> 14:12.960 funktioniert, wie wir das für dynamisch wachsende Arrays gesehen haben 14:12.960 --> 14:13.800 in Algorithmen 1. 14:14.160 --> 14:17.280 Sogar noch einfach, weil diese Datenstrukturen immer gleich groß sind. 14:18.780 --> 14:24.100 Was man dann im Endeffekt hat, ist, dass man amortisiert 1 durch B IO 14:24.100 --> 14:27.180 -Operationen pro Stack-Operation hat. 14:28.240 --> 14:31.480 Das ist also dann um den Faktor B effizienter als eine naive 14:31.480 --> 14:38.000 Implementierung, die einfach immer einen zufälligen IO auf die Platte 14:38.000 --> 14:38.220 macht. 14:38.880 --> 14:39.940 Fragen dazu? 14:43.220 --> 14:46.420 Man kann sich das jetzt auch überlegen, wie man das dann erweitert. 14:46.500 --> 14:50.580 Für zum Beispiel FIFO-Queues oder Double-Ended-Queues. 14:51.480 --> 14:55.460 Die kann man dann alle mit einer konstanten Anzahl Pufferblöcke so 14:55.460 --> 15:00.240 implementieren, dass man von 1 durch B IOs pro Operation hat. 15:00.540 --> 15:05.500 Dann möchte ich mal was vielleicht etwas komplexeres vorstellen. 15:05.620 --> 15:06.720 Externes Sortieren. 15:07.360 --> 15:09.280 Da jetzt n unsere Eingabegröße. 15:10.480 --> 15:14.340 Wie lange brauchen wir, um große Datenmengen zu sortieren, die am 15:14.340 --> 15:17.320 Anfang auf der Platte liegen oder in dem externen Speicher halt. 15:18.020 --> 15:22.080 Und dann soll die sortierte Ausgabe auch im externen Speicher liegen. 15:25.280 --> 15:31.780 Dafür schauen wir uns erst mal eine einfache Basis-Operation an. 15:32.840 --> 15:35.240 Mission zweier sortierter Folgen. 15:36.040 --> 15:43.240 Als Repräsentation wähle ich jetzt eine Datei und ich mache hier 15:43.240 --> 15:46.520 Annahmen darüber, wie das Betriebssystem eine Datei implementiert. 15:46.580 --> 15:48.080 Nämlich auch wieder mit Pufferblöcken. 15:48.920 --> 15:51.400 Ganz ähnlich, wie das eben bei den Stacks war. 15:56.020 --> 16:00.620 Und zeige aber bei der Analyse, was da dann passieren müsste. 16:02.080 --> 16:06.900 Also wir haben zwei sortierte Folgen A und B, die als Datei 16:06.900 --> 16:07.800 repräsentiert sind. 16:08.200 --> 16:16.720 Und wir wollen bei Mission, das heißt eine Folge C erzeugen, die auch 16:16.720 --> 16:19.380 wieder sortiert ist und die Elemente aus A und B enthält. 16:23.920 --> 16:29.280 Und was wir jetzt immer machen, wir haben eine interne gespeicherte 16:29.280 --> 16:34.500 Variable x und y, die jeweils das kleinste noch nicht verarbeitete 16:34.500 --> 16:36.380 Element von A und B darstellen. 16:40.160 --> 16:43.800 Haben eine Schleife, die A-Betrag plus B-Betrag laufen wird. 16:44.540 --> 16:48.240 Wenn x kleiner y ist, ist x offenbar das kleinste noch nicht 16:48.240 --> 16:49.280 verarbeitete Element. 16:49.800 --> 16:55.040 Dann schreibe ich das in die sortierte Folge C und muss dann, da das 16:55.040 --> 16:59.860 ja das kleinste Element von A war, das nächste Element aus A lesen. 17:01.660 --> 17:03.540 Das ist jetzt hier so ein bisschen dargestellt. 17:03.840 --> 17:07.200 Ich nehme jetzt im Prinzip an, dass ich dieses schwarz umrandete Ding, 17:07.280 --> 17:12.020 ist so ein Pufferblock, den mein Dateisystem im Hauptspeicher hält. 17:12.920 --> 17:14.860 x ist das aktuelle Element. 17:15.100 --> 17:17.780 Wenn das jetzt verarbeitet ist, lese ich das nächste Element. 17:18.040 --> 17:22.900 Dann würde das hier weiß werden und das hier ist dann fett gesetzt. 17:23.760 --> 17:29.180 Wenn ich das letzte Element aus dem Pufferblock gelesen habe, wird das 17:29.180 --> 17:34.600 Betriebssystem den nächsten Block von A aus der Datei lesen. 17:35.760 --> 17:38.900 Und um die Details muss ich mich dann angenehmerweise auch nicht 17:38.900 --> 17:39.240 kümmern. 17:39.700 --> 17:43.860 Das ist nämlich dann vielleicht sogar so, dass das Betriebssystem da 17:43.860 --> 17:47.800 auch wieder so eine Doppelpufferung vornimmt, also im Hintergrund 17:47.800 --> 17:51.280 bereits den nächsten Block liest, während der aktuelle Block 17:51.280 --> 17:54.800 verarbeitet wird und ich damit dann noch höhere Bandbreiten erreichen 17:54.800 --> 17:55.160 kann. 17:56.520 --> 18:01.900 Aber da wir hier nur IO-Operationen zählen, interessiert uns das an 18:01.900 --> 18:02.720 dieser Stelle nicht. 18:03.940 --> 18:07.240 Aber wenn ich das so implementiere, profitiere ich dann trotzdem von 18:07.240 --> 18:10.820 fortgeschritteneren Implementierungen, die weiter unten passieren. 18:12.020 --> 18:14.000 Fragen zu dieser Merge-Operation? 18:16.060 --> 18:17.960 Vielleicht nochmal auf der Schreibseite. 18:18.560 --> 18:21.220 Habe ich hier auch diesen Pufferblock, da wird halt nur ein Element 18:21.220 --> 18:22.520 nach dem anderen reingeschrieben. 18:23.040 --> 18:26.860 Wenn der Pufferblock voll ist, schreibt er das auf die Datei und hat 18:26.860 --> 18:29.520 dann einen leeren Pufferblock im Hauptspeicher wieder. 18:30.300 --> 18:30.780 Frage? 18:31.960 --> 18:32.280 Genau. 18:32.980 --> 18:33.920 Das kommt jetzt. 18:34.280 --> 18:34.840 Analyse. 18:36.480 --> 18:42.640 Also ist da nicht die Laufzeit, sondern die Anzahl IO-Operationen? 18:43.540 --> 18:44.180 Genau. 18:46.040 --> 18:49.640 Also wie viele IOs brauche ich für das Lesen der Datei A? 18:50.740 --> 18:55.880 Naja, das ist A-Betrag durch B aufgerundet, also kleiner gleich A 18:55.880 --> 18:57.340 -Betrag durch B plus 1. 18:57.620 --> 19:02.040 Für das Lesen von B brauche ich kleiner gleich B-Betrag durch B plus 19:02.040 --> 19:02.520 1. 19:02.980 --> 19:08.920 Für das Schreiben von C A-Betrag plus B-Betrag durch B aufgerundet. 19:09.200 --> 19:17.600 Also insgesamt ist das kleiner gleich 3 plus 2 mal die Summe der 19:17.600 --> 19:18.500 Längen der Eingaben. 19:19.240 --> 19:23.540 Weil das Schreiben von C ist natürlich dann genau die Summe davon. 19:24.340 --> 19:29.600 Und dieses plus 3 spare ich mir und schreibe das ist ungefähr zweimal 19:29.600 --> 19:30.840 die Summe der Eingabelängen. 19:33.940 --> 19:36.920 Was ich dann an Ressourcen brauche, sind drei Pufferblöcke. 19:37.180 --> 19:39.100 Einen für A, einen für B, einen für C. 19:39.740 --> 19:44.140 Das klingt jetzt nach einer trivialen Einschränkung, aber wir werden 19:44.140 --> 19:48.500 halt dann externe Algorithmen kennen lernen, bei denen man dann eine 19:48.500 --> 19:52.360 recht große Anzahl Pufferblöcke braucht und die beschränken dann 19:52.360 --> 19:56.960 sozusagen die Auslegung des Algorithmus. 19:57.480 --> 20:01.760 Da kommt man dann doch irgendwann an die interne Speichergröße dran 20:01.760 --> 20:06.320 und das ist dann für die Analyse wichtig, genau zu gucken, was brauche 20:06.320 --> 20:06.460 ich. 20:08.320 --> 20:11.160 Was vielleicht auch noch ganz interessant ist, ich zähle jetzt hier 20:11.160 --> 20:13.100 die IO-Operationen. 20:14.780 --> 20:18.660 Man kann aber genauso gut auch über das Ein-Ausgabe-Volumen reden. 20:18.880 --> 20:21.640 Also wenn man jetzt tatsächlich einen Algorithmus hat, bei dem man 20:21.640 --> 20:27.280 sichergestellt hat, dass sämtliche IO-Operationen irgendwie einen 20:27.280 --> 20:32.580 kompletten Block nützlicher Daten ranschaffen, dann kann man auch 20:32.580 --> 20:36.900 einfach analysieren, was ist das gesamte Ein-Ausgabe-Volumen und das 20:36.900 --> 20:42.400 sind dann oft Zahlen, die nur noch von der Eingabegröße abhängen und 20:42.400 --> 20:47.640 gar nicht mehr von diesen Parametern m und b. 20:48.960 --> 20:54.700 Das ist irgendwie praktisch, weil man eigentlich jetzt ein sehr 20:54.700 --> 20:59.700 maschinenunabhängiges Komplexitätsmaß hat. 21:01.200 --> 21:04.980 Insbesondere macht es bei der Analyse von IO-Volumen dann auch 21:04.980 --> 21:07.940 durchaus Sinn, sich genau die konstanten Faktoren anzuschauen. 21:08.260 --> 21:11.660 Wir hatten bisher bei der Algorithmenanalyse immer gesagt, naja, das 21:11.660 --> 21:16.300 theoretische Modell zählt Maschinenbefehle, aber eigentlich müsste ich 21:16.300 --> 21:19.920 für jeden Maschinenbefehl dann ja noch zählen, wie viele Taktzyklen 21:19.920 --> 21:20.460 braucht er. 21:20.960 --> 21:24.060 Das hängt aber bei modernen Architekturen wieder von tausend anderen 21:24.060 --> 21:25.220 Hardware -Aspekten ab. 21:26.460 --> 21:31.840 Das heißt, konstante Faktoren in der Laufzeitanalyse sind irgendwie 21:31.840 --> 21:38.620 hoffnungslos, die wirklich komplett maschinenunabhängig zu erfassen. 21:39.680 --> 21:43.760 Aber bei External-Memory-Algorithmen kann ich das plötzlich tun. 21:44.700 --> 21:50.240 Das Ein-Ausgabe-Volumen ist etwas, das sehr greifbar ist und wie sich 21:50.240 --> 21:53.660 das dann in Laufzeit umsetzt, hängt halt dann von irgendwelchen 21:53.660 --> 22:00.280 technologischen Parametern der I.O.-Geräte ab oder vielleicht auch von 22:00.280 --> 22:02.560 Details des Betriebssystems. 22:02.940 --> 22:07.740 Aber man kann dann doch sehr oft sagen, aha, wenn ich hier das I 22:07.740 --> 22:11.280 .O.-Volumen um Faktor 2 senke, dann wird tatsächlich der Algorithmus 22:11.280 --> 22:11.760 auch schneller. 22:13.880 --> 22:19.560 Während ich bei Operationen zähle, ist das oft viel schwieriger. 22:19.720 --> 22:23.480 Wenn ich sage, ich spare hier so und so viele Multiplikationen, muss 22:23.480 --> 22:28.640 dafür aber so und so viele zusätzliche Speicherzugriffe investieren, 22:28.740 --> 22:30.460 dann ist völlig unklar, was das bedeutet. 22:31.440 --> 22:34.660 Aber hier kann ich alles in die gemeinsame Währung Ein-Ausgabe-Volumen 22:34.660 --> 22:39.580 übersetzen und hier wird es dann also viel spannender, auch konstante 22:39.580 --> 22:40.860 Faktoren mehr anzuschauen. 22:42.940 --> 22:46.980 Und Mischen ist offenbar eine ziemlich effiziente Operation. 22:47.280 --> 22:51.500 Ich muss die Eingabe lesen, das Ergebnis schreiben, das klingt 22:51.500 --> 22:52.720 irgendwie kaum zu verbessern. 22:53.080 --> 22:56.280 Also es ist vielleicht auch ein guter Building-Block für komplexere 22:56.280 --> 22:58.760 externe Algorithmen. 22:59.220 --> 23:01.960 Jetzt schauen wir uns mal an, wie man daraus einen Sortieralgorithmus 23:01.960 --> 23:02.320 baut. 23:03.160 --> 23:07.220 Könnte jetzt auf den ersten Blick versucht sein, den Binary-Merge-Sort 23:07.220 --> 23:11.060 -Algorithmus aus Algorithmen 1 direkt einzusetzen. 23:11.180 --> 23:16.860 Das war ein rekursiver Algorithmus, der so top-down arbeitet, aber da 23:16.860 --> 23:20.180 kommt man dann auf den untersten Rekursionsebenen 23:24.200 --> 23:28.120 zu super kleinen Eingabefolgen, die aus einzelnen Elementen bestehen, 23:28.160 --> 23:30.200 und die möchte man nicht irgendwie extern bearbeiten. 23:30.320 --> 23:34.460 Muss man auch nicht, weil man da ganze Teilbäume der Rekursionen dann 23:34.460 --> 23:36.560 im Hauptspeicher abarbeiten könnte. 23:37.100 --> 23:39.980 Aber trotzdem macht es irgendwie nicht so viel Sinn, das rekursiv 23:39.980 --> 23:43.700 darzustellen, sondern wir bauen jetzt einen nicht-rekursiven Merge 23:43.700 --> 23:46.540 -Sort -Algorithmus, der bottom-up vorgeht. 23:47.540 --> 23:50.960 Und dann macht es Sinn zu sagen, ja dann gehen wir doch mal... unser 23:50.960 --> 23:55.760 Base -Case ist jetzt nicht irgendwie ein Element lesen und sich zu 23:55.760 --> 24:00.000 freuen, dass das dann sortiert ist, sondern der Base-Case ist, wir 24:00.000 --> 24:02.540 laden den ganzen internen Speicher mit Daten voll. 24:03.560 --> 24:04.560 Man nennt das einen Run. 24:05.720 --> 24:12.720 Hier habe ich zum Beispiel den Run, lade ich in den Hauptspeicher, 24:12.860 --> 24:16.100 sortiere das mit einem internen Algorithmus und schreibe es wieder 24:16.100 --> 24:16.460 raus. 24:18.480 --> 24:25.600 Das mache ich mit jeweils Groß-M-Elementen und brauche dann also N 24:25.600 --> 24:30.060 durch M Runs, aber im Endeffekt mache ich ja nichts anderes als alle 24:30.060 --> 24:33.900 Elemente einmal lesen, dieser internen Sortier-Operation zu schreiben 24:33.900 --> 24:36.420 und als so einen Run der Größe M wieder rausschreiben. 24:36.720 --> 24:40.020 Wir müssen uns jetzt nicht wundern, dass das eben zwei N durch B IOs 24:40.020 --> 24:40.500 braucht. 24:41.320 --> 24:42.800 Oder von mir aus wieder plus eins. 24:43.300 --> 24:46.800 Und ich habe hier jetzt so einen Fall, wo tatsächlich die interne 24:46.800 --> 24:52.900 Speichergröße wichtig ist, die begrenzt sozusagen mit wie vielen Runs 24:52.900 --> 24:53.920 wir hier arbeiten müssen. 24:56.960 --> 25:03.860 Ich mache also erstmal diese Run-Formation und dann bottom-up gehe ich 25:03.860 --> 25:07.380 immer vor und nehme Paare von Runs und mische die mit meiner Binary 25:07.380 --> 25:11.700 Merge Operation zu einem doppelt so großen sortierten Run zusammen. 25:12.220 --> 25:13.960 Das habe ich hier mal in dem Bild dargestellt. 25:22.480 --> 25:30.040 Ich habe hier A und B gar nicht festgelegt. 25:30.960 --> 25:36.320 Jedenfalls habe ich hier so eine Eingabe der Größe 48, also vier Runs 25:36.320 --> 25:37.380 der Größe 12. 25:38.400 --> 25:40.160 Hier werde ich die Buchstaben sortieren. 25:40.280 --> 25:42.000 Das habe ich jetzt für diesen Run gemacht. 25:44.940 --> 25:50.240 Dann nehme ich zwei Runs, mische sie zusammen zum sortierten Run und 25:50.240 --> 25:53.200 dann die beiden entstehenden großen Runs zu einem. 25:54.940 --> 25:58.020 Fragen zu dem Algorithmus? 25:59.380 --> 26:01.260 Dann analysieren wir den mal. 26:01.680 --> 26:04.660 Run-Formation haben wir gesagt, 2n durch b IOs. 26:06.380 --> 26:11.260 Das Mischen der Paare braucht halt auch 2n durch b. 26:11.660 --> 26:13.700 Wird alles einmal gelesen, alles einmal geschrieben. 26:15.440 --> 26:19.300 Jetzt muss man sich noch überlegen, wie viele Iterationen brauche ich? 26:19.580 --> 26:24.100 Na ja, ich halbiere jedes Mal die Anzahl Runs. 26:24.520 --> 26:27.440 Ich habe am Anfang n durch M. 26:28.920 --> 26:33.640 Dann brauche ich also log zur Basis 2 von n durch M und das noch 26:33.640 --> 26:34.360 aufgerundet. 26:36.760 --> 26:46.260 Also insgesamt 2n durch b mal 1 für die Run-Formation plus log n durch 26:46.260 --> 26:47.400 M aufgerundet. 26:48.620 --> 26:49.880 Fragen zu der Analyse? 26:50.860 --> 26:53.640 Also hier haben wir jetzt tatsächlich den ersten Algorithmus, wo dann 26:53.640 --> 26:57.480 beide Parameter b und M eine Rolle spielen. 26:59.400 --> 27:02.440 Und wir sehen jetzt halt auch, dass je größer der interne Speicher 27:02.440 --> 27:05.220 ist, desto schneller geht es das externe Sortieren. 27:06.500 --> 27:07.440 Fragen dazu? 27:08.500 --> 27:10.500 Gucken wir uns mal konkrete Zahlen an. 27:13.480 --> 27:17.840 Ich habe jetzt mal so einen, ich sag mal gut ausgestatteten PC mir 27:17.840 --> 27:18.500 angeschaut. 27:18.660 --> 27:23.180 Ich gehe dann bei Alternate.de oder sowas auf die Webseite und gucke, 27:24.060 --> 27:30.260 was sind da gut ausgestattete PCs und was sind aktuelle Festplatten. 27:30.360 --> 27:31.160 Wie groß sind die? 27:31.300 --> 27:36.200 Also die, die das beste Preis-Performance irgendwie oder also Preis 27:36.200 --> 27:37.500 pro Byte haben. 27:39.360 --> 27:44.920 Da sind dann irgendwie 3TB Platten sind im Moment so Standard und 27:44.920 --> 27:45.480 günstig. 27:46.220 --> 27:50.380 Damit kann man relativ problemlos 1TB Daten sortieren. 27:50.660 --> 27:54.360 Also dieser Algorithmus oder die meisten der externen 27:54.360 --> 27:58.000 Sortieralgorithmen, die man so sieht, sind nicht in place. 27:58.180 --> 28:02.360 Das heißt, ich brauche doppelt so viel Platz auf der Platte, wie ich 28:02.360 --> 28:03.440 Eingabegröße habe. 28:04.180 --> 28:06.660 Und vielleicht ist auf der Platte auch noch was anderes drauf. 28:06.800 --> 28:10.220 Also sage ich mal, ich will 1TB sortieren, brauche dann 2TB 28:10.220 --> 28:11.340 Plattenkapazität. 28:12.180 --> 28:14.460 Ich habe sagen wir mal 16GB RAM. 28:16.940 --> 28:19.820 Und die Blockgröße ist jetzt ein bisschen spannender. 28:20.400 --> 28:27.280 Wenn Sie da ältere Arbeiten oder Arbeiten von Theoretikern über 28:28.480 --> 28:32.020 External Memory lesen, dann sind sie ein bisschen verwirrt, weil die 28:32.020 --> 28:36.920 sagen dann ja, Festplatten haben irgendwie eine inhärente technisch 28:36.920 --> 28:38.680 bestimmte Blockgröße. 28:40.020 --> 28:42.700 Das stimmt bis zu einem gewissen Grade auch. 28:43.320 --> 28:48.160 Es gibt zum Beispiel so Einheiten von, ich weiß nicht, 512 oder 1024 28:48.160 --> 28:53.600 Byte, die gemeinsam gelesen werden und an einem fehlerkorrigierenden 28:53.600 --> 28:55.520 Code unterworfen werden oder sowas. 28:56.000 --> 28:58.700 Wenn Sie das aber als Ihre Blockgröße verwenden, kriegen Sie völligen 28:58.700 --> 28:59.520 Quatsch raus. 29:00.940 --> 29:04.280 Dann ist Ihr Algorithmus mehrere Größenordnungen langsamer, als Sie es 29:04.280 --> 29:04.740 haben wollen. 29:05.500 --> 29:08.680 Sondern die Blockgröße ist bei einer Festplatte tatsächlich irgendwas 29:08.680 --> 29:13.340 von Designparameter, den Sie sich überlegen können für Ihren 29:13.340 --> 29:14.020 Algorithmus. 29:14.540 --> 29:20.020 Aber eine gute Faustregel ist zu sagen, ich gucke mir die Latenz an, 29:20.060 --> 29:23.900 die ich habe, um eine beliebige Stelle meiner Festplatte zugreifen zu 29:23.900 --> 29:24.160 können. 29:25.540 --> 29:30.040 Das ist seit Jahrzehnten irgendwie in Größenordnung 10 Millisekunden. 29:31.220 --> 29:37.240 Je nachdem ob es teure oder billige Hardware ist, dann Faktor 2, give 29:37.240 --> 29:37.740 or take. 29:39.200 --> 29:42.880 Und dann nehmen Sie eine Blockgröße, die dafür sorgt, dass dieser 29:42.880 --> 29:48.500 Overhead für den Zugriff, Sie müssen ja da diesen mechanischen 29:48.500 --> 29:52.760 Schreiblesekopf irgendwie bewegen, dass der amortisiert wird über eine 29:52.760 --> 29:56.180 Datenmenge, die so groß ist, dass die Ein-Ausgabe-Bandbreite irgendwie 29:56.180 --> 30:02.040 in der Nähe der Peak-Bandbreite ist, die Sie hätten, wenn Sie wirklich 30:02.040 --> 30:06.520 nur sequenziell große Dateien legen und schreiben. 30:07.400 --> 30:12.660 Und dann kommt man auf, also wenn Sie sich mal Bandbreiten heutiger 30:12.660 --> 30:15.780 Festplatten angucken, die sind so in der Größenordnung 100 Megabyte 30:15.780 --> 30:22.040 pro Sekunde, dann ist irgendwie ein ganz guter Kompromiss, 4 Megabyte 30:22.040 --> 30:23.340 große Blöcke zu wählen. 30:24.080 --> 30:31.400 Dann braucht ein IO sowas wie eine sechzehnte Sekunde. 30:33.380 --> 30:37.760 Also dann hätten Sie, also ich habe hier Zweierpotenzen gewählt, damit 30:37.760 --> 30:41.600 man gut rechnen kann, das kann auch ein Faktor 2 mehr oder weniger 30:41.600 --> 30:41.960 sein. 30:42.820 --> 30:46.060 Mit diesen Parametern würden Sie dann annehmen, dass Ihre Festplatte 30:46.060 --> 30:49.960 64 Megabyte pro Sekunde IO-Bandbreite erreicht. 30:50.400 --> 30:54.220 Jetzt setzen wir hier die Anzahl IO-Operationen ein. 30:58.900 --> 31:04.880 Also N durch M ist dann 64 RANs. 31:07.780 --> 31:10.320 Dann ist Log N durch M 6. 31:11.020 --> 31:12.380 1 plus 6 ist 7. 31:12.380 --> 31:15.640 Also Sie haben sieben Durchläufe durch die Daten. 31:17.320 --> 31:19.880 Sie müssen jeweils hier lesen und schreiben. 31:23.380 --> 31:27.260 Wenn Sie das alles ausrechnen, kommen Sie auf 2 hoch 16 Sekunden. 31:27.860 --> 31:29.460 Das sind ungefähr 32 Stunden. 31:30.060 --> 31:36.400 Also Sie können den Inhalt Ihrer Festplatte in eineinhalb Tagen 31:36.400 --> 31:38.280 sortieren mit diesem Algorithmus. 31:39.720 --> 31:45.140 Ich sage mal, das ist machbar, aber ich sage mal auch ziemlich bitter. 31:45.760 --> 31:48.300 Da müssen Sie schon lange warten. 31:49.360 --> 31:53.100 Wir wollen uns jetzt anschauen, wie man das Ganze von sieben 31:53.100 --> 31:56.260 Durchläufen durch die Daten auf zwei Durchläufe reduzieren kann. 31:57.600 --> 31:59.580 Und was man da macht, ist mehr Wege mischen. 32:03.240 --> 32:05.160 RAN-Formation bleibt die gleiche. 32:05.740 --> 32:11.580 Vielleicht kann man da hier den Algorithmus sich auch schon anschauen. 32:12.220 --> 32:13.980 RAN-Formation bleibt die gleiche. 32:14.220 --> 32:17.560 Aber was ich jetzt mache, ich mische so viele RANs zusammen, wie ich 32:17.560 --> 32:18.580 es mir leisten kann. 32:18.980 --> 32:23.920 In einem Rutsch nutze auch wieder meine Speicherkapazität voll aus. 32:24.020 --> 32:28.460 Und wir werden sehen, ich kann dann sowas wie M durch B RANs in einem 32:28.460 --> 32:29.620 Rutsch zusammensortieren. 32:30.440 --> 32:33.060 Und das Ganze wird dann effizienter. 32:33.160 --> 32:35.180 Die Zahlen gucken wir uns später an. 32:35.620 --> 32:39.560 Schauen wir uns erst mal an, wie geht überhaupt das Mehr-Wege-Mischen. 32:42.770 --> 32:47.310 Das ist eigentlich eine relativ simple Verallgemeinerung des Zwei-Wege 32:47.310 --> 32:47.770 -Mischens. 32:48.450 --> 32:52.810 Ich habe jetzt nicht mehr zwei Zahlen x und y, die das jeweils 32:52.810 --> 32:56.710 kleinste Element der Eingabefolgen angeben, sondern ich habe k 32:56.710 --> 32:57.630 Eingabefolgen. 32:58.050 --> 33:00.450 k ist ein Tuning-Parameter, über den wir noch reden. 33:01.270 --> 33:03.050 Und eine Ausgabefolge c. 33:05.130 --> 33:09.070 x i ist jeweils das kleinste, noch nicht verarbeitete Element der 33:09.070 --> 33:10.190 Eingabefolge a i. 33:12.510 --> 33:15.970 Und ja, jetzt muss ich die ganzen Eingabe-Elemente verarbeiten. 33:16.130 --> 33:18.250 Das sind Summe i gleich 1 bis k mal a i. 33:18.310 --> 33:19.090 Betrag viele. 33:20.110 --> 33:25.450 So, und jetzt muss ich jeweils das kleinste Element, das kleinste der 33:25.450 --> 33:27.230 kleinsten Elemente sozusagen finden. 33:27.290 --> 33:32.530 Das ist das kleinste, insgesamt noch nicht verarbeitete Element. 33:32.850 --> 33:37.290 Also das kann ich jetzt hier... also finde i aus 1 bis k, so dass x i 33:37.290 --> 33:38.290 minimal wird. 33:38.730 --> 33:41.890 Auf den ersten Blick klingt das so, als bräuchte man dafür Zeit o von 33:41.890 --> 33:42.250 k. 33:43.510 --> 33:45.690 Theoretiker würde sagen, interessiert mich doch nicht. 33:45.850 --> 33:48.190 Das sind ja keine IOO-Operationen. 33:48.370 --> 33:51.930 Also ich gehe natürlich davon aus, dass diese x i im Hauptspeicher 33:51.930 --> 33:52.210 sind. 33:52.890 --> 33:58.650 Ich gehe außerdem davon aus, dass ich für jede Eingabefolge so einen 33:58.650 --> 34:00.470 Puffer -Block im Hauptspeicher habe. 34:00.670 --> 34:06.290 Also ich brauche k mal b Blocks, bloß ein bisschen für Programme und x 34:06.290 --> 34:06.990 i usw. 34:08.250 --> 34:13.730 Aber tatsächlich ist es so, wir reden ja auch über interne Arbeit, man 34:13.730 --> 34:16.930 kann das im Endeffekt in einer Prioritätsliste speichern, das x i. 34:17.330 --> 34:19.510 Und dann brauche ich nur o von log k Zeit. 34:19.650 --> 34:23.090 Das wird später bei der Analyse der internen Arbeit eine Rolle 34:23.090 --> 34:23.450 spielen. 34:24.570 --> 34:29.150 Genau, also jetzt habe ich halt... ich brauche mehr Speicher für diese 34:29.150 --> 34:32.010 Puffer -Blocks und ich muss ein bisschen mehr Arbeit leisten, aber das 34:32.010 --> 34:36.010 ist interne Arbeit, um das wirklich kleinste verbleibende Element 34:36.010 --> 34:36.870 auszuwählen. 34:37.210 --> 34:40.890 Aber das dann in die Ausgabedatei c schreiben ist das gleiche wie 34:40.890 --> 34:46.190 vorher und ich muss halt dann das x i als nächstes Element aus dem a i 34:46.190 --> 34:46.630 lesen. 34:47.090 --> 34:49.790 Gibt es Fragen zu dieser Mehr-Wege-Misch-Operation? 34:50.630 --> 34:51.810 Analysieren wir das mal. 34:55.290 --> 35:02.730 Anzahl IOs-Operationen, naja man muss Datei a i lesen, das kostet a i 35:02.730 --> 35:05.750 durch b aufgerundet viele IOs. 35:06.710 --> 35:08.610 Diese Rundung schenken wir uns jetzt mal. 35:09.890 --> 35:15.450 Datei c schreiben, wie gehabt, Summe der Eingabelängen durch b. 35:17.070 --> 35:23.710 Also insgesamt zweimal Summe der Eingabelängen durch b IO-Operationen. 35:24.450 --> 35:27.690 So, das klingt jetzt auf den ersten Blick so. 35:27.970 --> 35:31.210 Prima, dann wählen wir k als n durch b. 35:32.230 --> 35:35.390 Das heißt, wir können alle Runs in einem Rutsch zusammen mischen und 35:35.390 --> 35:36.030 alles ist gut. 35:37.210 --> 35:42.090 Wir werden später auch sehen, dass das in der Praxis tatsächlich Sinn 35:42.090 --> 35:42.430 macht. 35:44.110 --> 35:48.670 Aber für die Theorie und auch für die breitere Anwendbarkeit des 35:48.670 --> 35:52.450 Ergebnisses wollen wir diese Annahme mal nicht machen und überlegen 35:52.450 --> 35:55.110 uns, naja, wie groß kann ich k denn maximal wählen? 35:57.090 --> 36:02.950 Naja, diese k plus 1 Pufferblöcke müssen ja in den Hauptspeicher der 36:02.950 --> 36:04.510 Größe m passen. 36:05.230 --> 36:09.630 Wir haben jeweils Größe b, deshalb gilt sicherlich k plus 1 kleiner m 36:09.630 --> 36:10.230 durch b. 36:11.010 --> 36:15.070 Jetzt schenke ich mir dieses plus 1 und schreibe sowas wie k kleiner m 36:15.070 --> 36:15.610 durch b. 36:16.550 --> 36:20.250 Da bin ich ein bisschen zu optimistisch, aber die Asymptotik stimmt 36:20.250 --> 36:20.890 dann am Ende. 36:23.450 --> 36:28.930 Für die interne Arbeit später halten wir auch fest, dass der Aufwand 36:28.930 --> 36:32.890 Summe der Eingabelängen mal locker ist. 36:35.850 --> 36:37.190 Fragen zur Analyse? 36:40.740 --> 36:48.200 Dann können wir jetzt den Sortieralgorithmus analysieren, der dadurch 36:48.200 --> 36:48.820 entsteht. 36:49.200 --> 36:50.020 Hier ist so ein Beispiel. 36:50.280 --> 36:54.700 Ich habe jetzt vier, das ist die gleiche Eingabe, vier Runs und die 36:54.700 --> 36:56.500 kann ich jetzt in einem Rutsch zusammenmischen. 36:58.260 --> 37:05.240 In dem Fall Spielzeugbeispiel halbiere ich, verringere ich dann die 37:05.240 --> 37:08.580 Anzahl Durchläufe durch die Daten von 3 auf 2. 37:11.440 --> 37:15.300 Allgemeiner analysiert, die Anzahl IOs für die Randformation bleibt 37:15.300 --> 37:20.580 die gleiche, die Anzahl IOs für eine Mischoperation bleibt auch die 37:20.580 --> 37:25.620 gleiche, nur dass ich jetzt die Anzahl Rands um den Faktor m durch b 37:25.620 --> 37:30.780 reduziere, der findet sich dann hinterher in der Basis des Logarithmus 37:30.780 --> 37:31.080 wieder. 37:31.300 --> 37:36.440 Also die Anzahl Mischdurchläufe, die ich brauche, ist jetzt log n 37:36.440 --> 37:38.340 durch m zur Basis m durch b. 37:40.660 --> 37:44.920 Insgesamt kriege ich dann 2n durch b mal 1 plus log m durch b, m durch 37:44.920 --> 37:45.220 m. 37:45.220 --> 37:54.540 Und das ist eine, ich sag mal, für den Nicht-Algorithmiker schon eine 37:54.540 --> 37:57.040 relativ komplexe Formel. 37:58.260 --> 38:03.000 Es sind vor allem drei Parameter drin, Logarithmusbasis, blablabla. 38:03.640 --> 38:08.200 Trotzdem taucht genau diese Formel in ganz vielen externen Memory 38:08.200 --> 38:09.060 -Algorithmen auf. 38:10.000 --> 38:13.700 Selbst wenn da gar nicht sortiert wird, kommt am Ende wieder die 38:13.700 --> 38:15.120 gleiche Komplexität raus. 38:16.480 --> 38:21.160 Also diese Sortierkomplexität ist was sehr Fundamentales für externe 38:21.160 --> 38:22.100 Memory -Algorithmen. 38:22.740 --> 38:26.980 Deshalb haben die Algorithmiker da dann auch diese Funktion sort von n 38:26.980 --> 38:30.380 definiert, die dann ganz oft in den Papers auftaucht. 38:30.880 --> 38:33.000 Damit man diese lange Formel nicht mehr schreiben muss, schreibt man 38:33.000 --> 38:34.100 einfach nur noch sort von n. 38:34.820 --> 38:39.180 Fragen zu der Analyse des Multi-Way Merging Algorithmus? 38:41.400 --> 38:48.810 Jetzt können wir... genau, jetzt habe ich gesagt... 38:52.580 --> 38:55.160 Gucken wir uns erstmal die interne Arbeit an. 38:58.480 --> 39:01.800 Da steht jetzt die Asymptotik, aber ich will vielleicht an der Tafel 39:01.800 --> 39:03.940 mal Vergleiche zählen. 39:04.220 --> 39:08.080 Das macht man oft bei Sortieralgorithmen, dass man sagt, was ich da 39:08.080 --> 39:08.780 genau mache. 39:09.000 --> 39:12.100 Das ist komplex, da sind viele Speicherzugriffe dabei. 39:14.620 --> 39:18.900 Aber informationstheoretisch, was dahinter steht, ist, ich vergleiche 39:18.900 --> 39:21.380 Elemente und nutze die Informationen, die ich dabei gewinne. 39:22.280 --> 39:25.220 Vor allem haben wir ja auch diese untere Schranke, die zeigt, dass man 39:25.220 --> 39:31.080 sowas wie nLogN-Vergleiche auf jeden Fall braucht, um n Elemente zu 39:31.080 --> 39:31.540 sortieren. 39:33.020 --> 39:37.400 Wir gucken jetzt mal, wie effizient dieser Mehr-Wege-Misch-Algorithmus 39:37.400 --> 39:39.180 ist bezüglich der Anzahl Vergleiche. 39:39.840 --> 39:43.780 Das ist auf den ersten Blick irgendwie eine ziemlich komplexe Formel, 39:43.920 --> 39:46.100 wie viele Elementvergleiche habe ich. 39:48.160 --> 39:51.160 Bei der Run-Formation nehme ich mal an, dass ich da einen 39:51.160 --> 39:54.760 informationstheoretisch optimalen Algorithmus verwende. 39:54.860 --> 39:59.240 Dann brauche ich sowas wie LogM-Vergleiche pro Element. 40:03.380 --> 40:10.620 Dann habe ich Multi-Way-Merging, wo ich jedes Mal m durch b Rands mir 40:10.620 --> 40:15.840 anschaue, also dann auch LogM durch b vergleiche. 40:16.500 --> 40:20.180 Man kann hier tatsächlich auch den konstanten Faktor auf 1 drücken mit 40:20.180 --> 40:22.140 einer passenden Priority Key. 40:22.700 --> 40:25.220 Das sind so Turnierbaum-Datenstrukturen. 40:25.660 --> 40:28.540 Details machen wir in Algorithm Engineering in der Vorlesung. 40:30.760 --> 40:33.280 Und die Anzahl Phasen ist diese komplizierte Sache. 40:34.340 --> 40:37.060 Aber jetzt lassen Sie mich mal auswerten, was dabei rauskommt. 40:37.180 --> 40:38.880 Und Sie werden sich vielleicht ein bisschen wundern. 40:39.840 --> 40:43.200 Die Aufrundung lasse ich weg und ich schreibe jetzt nur pro Element, 40:43.440 --> 40:44.980 wie viele Vergleiche da stehen. 40:47.300 --> 40:48.820 Was haben wir gesagt? 40:50.740 --> 41:03.460 LogM plus LogM durch b plus Log zur Basis m durch b n durch m. 41:04.760 --> 41:08.600 Das kann man aber schreiben, also Logarithmusgesetze braucht man hier 41:08.600 --> 41:10.540 natürlich rauf und runter. 41:12.000 --> 41:17.020 Log n durch m geteilt durch Log der Basis. 41:18.000 --> 41:21.400 Log m durch b. 41:23.080 --> 41:23.180 Ja, 41:27.500 --> 41:29.500 das da ist ein Plus. 41:32.880 --> 41:36.620 Sie haben recht, Entschuldigung, das muss ein Mal sein. 41:37.980 --> 41:43.580 Und das ist praktisch, weil jetzt können wir das und das wegkürzen. 41:45.880 --> 41:49.340 Und außerdem steht da jetzt Log m mal Log n durch m. 41:49.700 --> 41:56.800 Nach Logarithmengesetzen kann man aber ein Produkt, ne, eine Summe von 41:56.800 --> 42:02.080 Logarithmen als Logarithmus des Produkts der Werte machen. 42:02.200 --> 42:11.060 Das ist also gleich Log m mal n durch m. 42:12.340 --> 42:17.020 Dann kürze ich das auch noch weg und es steht einfach nur noch Log n 42:17.020 --> 42:17.200 da. 42:21.490 --> 42:25.050 Und jetzt kommt davor, das mache ich für jedes Element. 42:25.810 --> 42:28.390 Also ich habe genau n Log n Vergleiche. 42:28.450 --> 42:31.510 Das Einzige, was ich hier ignoriert habe, ist das Aufrunden. 42:31.510 --> 42:35.410 Das heißt, ich habe jetzt informationstheoretisch nen sehr effizienten 42:35.410 --> 42:39.690 Algorithmus, obwohl ich irgendwie an drei Stellen hier Dinge tue. 42:39.850 --> 42:45.010 Ich mache internes Sortieren, ich mache Multi-Way Merging und ich 42:45.010 --> 42:48.470 iteriere mehrere solche Multi-Way Merging-Iterationen. 42:48.990 --> 42:52.650 Aber informationstheoretisch gesehen, weil ich immer gleich große Runs 42:52.650 --> 42:58.530 mische, ist das ein sehr effizientes Verfahren bezüglich der Anzahl 42:58.530 --> 43:02.970 Und das ist jetzt auch schon ein Hinweis, dass das bezüglich der 43:02.970 --> 43:05.450 internen Arbeit eigentlich auch recht effizient ist. 43:05.610 --> 43:10.790 Also ich mache nicht viel mehr interne Arbeit als bei normalen 43:10.790 --> 43:12.150 internen Sortier-Algorithmen. 43:13.130 --> 43:17.950 Das stimmt nicht ganz, weil insbesondere dieser Multi-Way Merging 43:17.950 --> 43:22.570 -Prozess, wenn Sie da genauer hingucken, ist der ein bisschen weniger 43:22.570 --> 43:28.370 effizient als das, was zum Beispiel bei Quicksort oder Samplesort und 43:28.370 --> 43:34.250 solchen Dingen passiert, wo wir dann, glaube ich, bei dem parallelen 43:34.250 --> 43:35.710 Algorithmen auch nochmal dazu kommen. 43:36.750 --> 43:38.890 Aber insgesamt schon eigentlich ganz brauchbar. 43:40.390 --> 43:42.870 Fragen zu der Analyse der internen Arbeit? 43:43.790 --> 43:47.130 Ein anderer Aspekt, den man sich jetzt anschauen kann, wenn wir hier 43:47.130 --> 43:52.610 wirklich über Festplatten reden, ist es tatsächlich so, dass dieser 43:52.610 --> 43:58.330 komplizierte Ausdruck, Log Basis m durch b, n durch m, der ist 43:58.330 --> 43:59.230 eigentlich immer 1. 44:01.650 --> 44:09.170 Das liegt einfach daran, also diese Dinge, das war ja hier Log n durch 44:09.170 --> 44:12.990 m durch Log m durch b, ich will, dass das kleiner gleich 1 ist. 44:12.990 --> 44:18.970 Das ist dann der Fall, wenn n durch m kleiner m durch b ist. 44:23.080 --> 44:25.360 Aber jetzt gucken wir uns mal an, wie ist das? 44:25.640 --> 44:30.980 m durch b, wir hatten in unserem Beispiel, was war das? 44:31.100 --> 44:35.520 16 Gigabyte RAM und 4 Megabyte Blöcke. 44:36.140 --> 44:40.580 Das heißt, ich kann sowas wie 4000 RAMs zusammenmischen in diesem PC 44:40.580 --> 44:41.760 -Beispiel, den wir hatten. 44:41.760 --> 44:47.080 Vielleicht gibt es auch schlechter ausgestattete PCs, aber wenn man 44:47.080 --> 44:53.060 sagt so, naja, 1000 ist sicherlich bei halbwegs vernünftigen Maschinen 44:53.060 --> 44:54.980 irgendwie immer drin. 44:57.840 --> 45:00.860 Aber wie groß ist n durch m? 45:01.680 --> 45:06.540 Nein, das ist jetzt, klingt jetzt so, ja, Eingabegröße kann ja 45:06.540 --> 45:07.340 irgendwas sein. 45:07.800 --> 45:12.180 Aber man muss sich ja vielleicht überlegen, ich muss meine Eingabe 45:12.180 --> 45:13.120 irgendwo speichern. 45:14.100 --> 45:15.300 Auf den Festplatten. 45:15.880 --> 45:16.800 Das kostet Geld. 45:19.020 --> 45:24.200 Ich werde aber sicherlich keinen Rechner kaufen, bei dem ich 1 Million 45:24.200 --> 45:27.700 Euro in Festplatten investiere und dann nur 100 Euro in RAM. 45:28.960 --> 45:32.940 Das ist irgendwie nicht sinnvoll, sondern man wird, wenn man eine 45:32.940 --> 45:36.760 Architektur hat, auf der man große Datenmengen verarbeitet, dafür 45:36.760 --> 45:40.480 sorgen, dass man eine halbwegs vernünftige Balance hat zwischen dem, 45:40.580 --> 45:44.320 was man in den Hintergrundspeicher investiert und dem, was man in den 45:44.320 --> 45:45.780 Hauptspeicher investiert. 45:47.900 --> 45:50.680 Also jetzt grob gesagt gleich viel oder von der gleichen 45:50.680 --> 45:51.340 Größenordnung. 45:51.920 --> 45:55.880 Und dann ist es eigentlich nur noch wichtig, wie viel teurer ist denn 45:55.880 --> 45:57.400 RAM als Platte. 45:58.060 --> 46:00.140 Und das ist im Moment, glaube ich, Faktor 300. 46:00.780 --> 46:07.580 Das liegt auch ein bisschen daran, dass RAM im Moment sehr teuer ist, 46:07.620 --> 46:08.680 schon lange sehr teuer ist. 46:08.760 --> 46:11.060 Ich habe jetzt gerade auch gelesen, dass das möglicherweise 46:11.060 --> 46:15.600 tatsächlich ein Kartell ist, das die RAM-Preise so hoch hält. 46:17.100 --> 46:20.060 Trotzdem ist das der gleiche Wert, wie wir den eigentlich seit 46:20.060 --> 46:22.200 Jahrzehnten haben, dieses Verhältnis. 46:23.720 --> 46:26.980 Meine Hypothese ist sogar, dass bei Festplatten der langfristig 46:26.980 --> 46:31.560 nochmal sinken wird, weil Festplatten eigentlich am Ende ihrer 46:31.560 --> 46:33.640 Lebenszeit angekommen sind. 46:33.640 --> 46:36.860 Die entwickeln sich nicht mehr so schnell, die werden auch nicht mehr 46:36.860 --> 46:41.540 in so vielen Anwendungen gebraucht, weil man eigentlich mit 46:41.540 --> 46:48.260 Halbleiterspeicher, also SSDs, heute die meisten Anwendungen viel 46:48.260 --> 46:49.300 besser bedienen kann. 46:50.480 --> 46:55.780 Und was wir da dann haben ist, dass die Blockgröße viel kleiner ist. 46:55.780 --> 47:02.840 Also dieser Faktor steigt massiv, während der Preis pro Bit, da ist 47:02.840 --> 47:06.260 der Faktor nicht 300, sondern im Moment sowas wie 20. 47:07.980 --> 47:09.720 Das heißt, da gilt es erst recht. 47:13.760 --> 47:20.420 Hat jemand eine Idee für irgendwie eine sinnvolle Zwei-Speicher 47:20.420 --> 47:22.740 -Hierarchie -Ebene, wo das vielleicht nicht gilt? 47:22.740 --> 47:27.280 Also das extreme Ding im Moment wäre, wenn ich einerseits den L1-Cache 47:27.280 --> 47:29.680 nehme und andererseits den Hauptspeicher zum Beispiel. 47:31.360 --> 47:41.380 Einen L1-Cache bei Intel-Architekturen, ich weiß nicht genau, 32, 64 47:41.380 --> 47:43.080 Kilobyte für den Datencache. 47:44.920 --> 47:49.340 Und dann ist der Hauptspeicher aber locker mal 64 Gigabyte. 47:50.160 --> 47:52.640 Das sind dann sechs Größenordnungen dazwischen. 47:53.760 --> 47:55.500 Das ist also eine ganz andere Hausnummer. 47:57.040 --> 48:01.780 Da braucht man dann tatsächlich Algorithmen, wo man mehrere Durchläufe 48:01.780 --> 48:07.820 hat, wenn man da cache-effiziente Sortieralgorithmen zum Beispiel 48:07.820 --> 48:08.680 analysieren will. 48:11.400 --> 48:17.080 Da ist der Faktor so viel größer, weil es nicht nur um die Kosten 48:17.080 --> 48:26.500 geht, sondern auch darum, dass wenn ich einen Cache größer mache, dann 48:26.500 --> 48:28.640 wird er nicht unbedingt teurer, aber er wird langsamer. 48:28.760 --> 48:32.540 Einfach weil die Leitungen länger werden und die Anzahl Adress-Bits, 48:32.740 --> 48:36.460 mit denen ich irgendwelche Operationen durchführen muss, werden größer 48:36.460 --> 48:36.940 und so weiter. 48:37.820 --> 48:41.140 Fragen zu dieser Argumentation? 48:42.660 --> 48:48.140 Um das kurz zu sagen ist, wir können eigentlich das Sort N, wenn wir 48:48.140 --> 48:53.660 wirklich über Festplatten oder Flash-Memory reden, das hier auf 1 48:53.660 --> 48:56.500 setzen und dann steht hier einfach nur 4N durch B. 48:57.120 --> 49:00.540 Also sortieren ist nicht viel teurer als Daten einfach nur lesen. 49:01.620 --> 49:04.880 Sortieren ist ungefähr so teuer wie die Daten zweimal lesen und 49:04.880 --> 49:05.640 zweimal schreiben. 49:07.100 --> 49:12.480 Und wenn man noch genauer hinguckt, wenn man einen External-Memory 49:12.480 --> 49:16.900 -Algorithmus, der Sortieren als Teilproblem hat, genau analysiert, ist 49:16.900 --> 49:23.480 es oft so, dass man sich das Lesen der Eingabe und das Schreiben des 49:23.480 --> 49:25.660 Ergebnisses, das kann man oft wegdiskutieren. 49:25.660 --> 49:29.500 Wenn man hat dann so Pipeline-Verarbeitungen, wo man dann verschiedene 49:29.500 --> 49:34.860 Phasen des Algorithmus direkt hintereinander stöpselt, dann kriegt man 49:34.860 --> 49:36.700 2N durch B für Sortieren. 49:37.280 --> 49:41.500 Also ist dann nur noch ein Faktor 2 teurer als die Daten einfach nur 49:41.500 --> 49:42.520 einmal anzuschauen. 49:43.820 --> 49:48.140 Das ist ganz wichtig, weil wir können also sozusagen Sortieren als 49:48.140 --> 49:53.100 einen Building-Block von External-Memory-Algorithmen verwenden und es 49:53.100 --> 49:55.400 kostet was, aber es kostet nicht richtig viel. 49:56.560 --> 50:00.520 Und das heißt, alles was ich mit Sortieren irgendwie mir erleichtern 50:00.520 --> 50:03.940 kann bei der Verarbeitung großer Datenmengen, kann ich mir meistens 50:03.940 --> 50:04.460 auch leisten. 50:06.180 --> 50:08.540 Und das ist eine wichtige Einsicht. 50:08.660 --> 50:13.700 Wir werden da auch gleich eine Beispielanwendung sofort uns anschauen. 50:14.760 --> 50:17.640 Jetzt gucken wir uns mal eine Verallgemeinerung von Sortieren an. 50:19.060 --> 50:21.500 Das habe ich in Algorithmen 1 auch so gemacht. 50:24.960 --> 50:27.560 Sortieren dynamisch ist im Prinzip eine Prioritätsliste. 50:27.560 --> 50:30.780 Ich kann zum Beispiel auch sortieren, indem ich alle Elemente in eine 50:30.780 --> 50:34.240 Prioritätsliste einfüge und sie dann mit Deletement wieder raushole. 50:34.700 --> 50:36.120 Aber ich kann eben mehr Dinge tun. 50:37.060 --> 50:42.680 Man kann sich jetzt fragen, kann ich diesen flexibleren Umgang mit den 50:42.680 --> 50:45.140 Daten auch im External-Memory effizient machen? 50:46.060 --> 50:48.640 Und das war erstaunlicherweise so, dass das... 50:49.160 --> 50:53.320 Genau, also externes Sortieren, das gibt es seit immer. 50:54.220 --> 50:58.280 Das war vielleicht in den 50er Jahren sogar noch wichtiger als heute, 50:58.380 --> 51:00.600 weil man winzige Hauptspeicher hatte. 51:01.540 --> 51:04.220 Da hat man dann Sortieren durch Mischen gemacht. 51:04.880 --> 51:09.580 Und der begrenzende Faktor war dann nicht die Hauptspeichergröße, 51:09.720 --> 51:13.720 sondern die Anzahl Bandlaufwerke, die man gleichzeitig betreiben 51:13.720 --> 51:14.120 konnte. 51:14.260 --> 51:16.860 Und dann hat man eben tatsächlich diese Bandinhalte gemischt. 51:17.740 --> 51:20.120 Das war nochmal ein bisschen ein anderes Spiel, aber im Endeffekt die 51:20.120 --> 51:21.520 gleichen Algorithmen. 51:21.520 --> 51:25.180 Das heißt, effizientes externes Sortieren, auch mit Multi-Way Merging, 51:25.260 --> 51:25.980 gibt es seit immer. 51:27.980 --> 51:31.880 Externe Prioritätslisten hat spannenderweise ziemlich lange gedauert. 51:34.860 --> 51:36.800 Bis da mal jemand was gemacht hat. 51:38.800 --> 51:41.600 Und was irgendwie ganz witzig ist, dass dann... 51:43.760 --> 51:47.680 Ende der 90er Jahre war ich damals am Max-Planck-Institut für 51:47.680 --> 51:52.480 Informatik und dann haben, glaube ich, in dieser Arbeitsgruppe für 51:52.480 --> 51:58.380 Algorithmen drei Leute mehr oder weniger unabhängig gleichzeitig 51:58.380 --> 52:03.080 effiziente Priority Queues entworfen für externe Demografie. 52:05.420 --> 52:08.420 Das war der Andreas Krauser in seiner Doktorarbeit, der Gerd Broder 52:08.420 --> 52:14.260 als Post-Doc, zusammen mit einem Kollegen aus Dänemark und ich hatte 52:14.260 --> 52:19.820 eigentlich vor, überhaupt mal auch praktisch das Ganze zu machen. 52:19.940 --> 52:22.980 Also die beiden anderen hatten das ein bisschen theoretischer und ich 52:22.980 --> 52:26.040 habe mir aber die praktischen Sachen angeschaut und auch eine 52:26.040 --> 52:30.960 Datenstruktur dann gefunden, die heute auch noch eingesetzt wird und 52:30.960 --> 52:34.800 die ich jetzt so mal vorführen möchte, beziehungsweise die Grundidee 52:34.800 --> 52:35.000 davon. 52:38.120 --> 52:40.220 Also was wir eigentlich wollen, ist 52:45.680 --> 52:50.420 pro Operation 1 durch B mal Log-Basis M durch B, N durch M IOs 52:50.420 --> 52:51.200 amortisiert. 52:52.680 --> 52:57.060 Und wenn wir aber naiv vorgehen, zum Beispiel sagen, ja, wir haben in 52:57.060 --> 52:59.960 Algo 1 einen Binary Heap kennengelernt, den legen wir einfach auf die 52:59.960 --> 53:05.680 Platte und arbeiten darauf, dann kriegt man sowas wie, na ja, ganz 53:05.680 --> 53:08.360 naiv sagen, Log-N IOs pro Delimit. 53:10.440 --> 53:14.600 Aber man kann sich überlegen, dass man die obersten Levels dieses 53:14.600 --> 53:20.460 Binary Heaps im Hauptspeicher hält und dann spart man sich sozusagen 53:20.460 --> 53:25.340 Log -M IOs pro Operation und kriegt dann Log-N durch M. 53:25.820 --> 53:28.420 Aber was wir wollen, ist viel weniger. 53:28.900 --> 53:31.960 Wir wollen diesen Faktor 1 durch B und das haben wir ja gesehen, das 53:31.960 --> 53:36.480 kann eine Million sein oder sowas und außerdem noch diese Basis M 53:36.480 --> 53:41.600 durch B haben und haben dadurch um mehrere Größenordnungen schnellere 53:41.600 --> 53:43.540 Operationen als wenn wir es naiv machen. 53:44.240 --> 53:49.600 Da ist auch die Fallhöhe viel höher eigentlich als beim Sortieren. 53:51.160 --> 53:57.640 Weil da haben wir ja jetzt gerade mal diesen naiven Binary Merge Sort 53:57.640 --> 54:00.760 ersetzt durch Multiway Merge Sort und haben dann durch den Faktor Log 54:00.760 --> 54:01.900 -M durch B gespart. 54:02.020 --> 54:06.000 Das war dann in der Beispielrechnung ein Faktor dreieinhalb. 54:07.580 --> 54:10.620 Hier sparen wir jetzt potenziell einen Faktor eine Million. 54:12.140 --> 54:14.020 Und das ist ja eigentlich sogar noch viel spannender. 54:15.320 --> 54:16.260 Also wie geht das? 54:19.020 --> 54:23.620 Ich führe das jetzt erstmal vor für, ich nenne das mittelgroße 54:23.620 --> 54:26.240 Priority Queues, die also schon viel größer sind als die 54:26.240 --> 54:30.780 Hauptspeichergröße aber durchaus beschränkt in ihrer Größe. 54:30.860 --> 54:32.440 Nämlich sowas wie M² durch B. 54:33.680 --> 54:38.300 Genauer gesagt k mal m Elemente. 54:40.240 --> 54:43.960 Also k und klein m, das sind Tuning-Parameter, aber am Ende wird dann 54:43.960 --> 54:49.840 k gleich m durch b sein und klein m gleich Theta-Große. 54:53.360 --> 54:55.480 Und außerdem mache ich noch was komisches. 54:55.480 --> 54:58.700 Ich beschränke nicht die Größe der Datenstruktur, sondern die Anzahl 54:58.700 --> 55:04.220 der Einfügeoperationen, weil das die Darstellung massiv vereinfacht 55:04.220 --> 55:10.460 und weil die meisten Algorithmen ohnehin so sind, dass es keinen 55:10.460 --> 55:14.340 großen Unterschied macht, ob ich mir die Maximalgröße der 55:14.340 --> 55:18.520 Datenstruktur anschaue oder die Anzahl Operationen, weil der typische 55:18.520 --> 55:22.020 Ablauf ist ohnehin, dass die Datenstruktur erstmal wächst, eine 55:22.020 --> 55:24.140 Maximalgröße erreicht und dann wieder schrumpft. 55:25.420 --> 55:29.580 Und die Gesamtzahl Einfügungen ist dann bis auf den konstanten Faktor 55:29.580 --> 55:32.600 das gleiche wie die Maximalgröße. 55:34.580 --> 55:37.180 Die Datenstruktur kann man am besten an diesem Bild verstehen. 55:37.700 --> 55:41.680 Die hat drei Komponenten im Endeffekt. 55:41.800 --> 55:45.220 Ich habe eine klassische Internal-Memory-Priority-Queue. 55:46.260 --> 55:48.360 Das ist ein Einfügepuffer, der große klein m. 55:48.900 --> 55:50.360 Die muss in den Hauptspeicher passen. 55:50.840 --> 55:53.160 In dem Bild, alles was rot ist, ist im Hauptspeicher. 55:56.380 --> 56:01.920 Und dann überlege ich mir jetzt vielleicht erstmal wie arbeite ich mit 56:01.920 --> 56:02.540 diesem Puffer. 56:03.780 --> 56:05.860 Ich habe gesagt, es ist ein Einfügepuffer. 56:06.460 --> 56:08.360 Am Anfang ist meine Priority-Queue leer. 56:08.460 --> 56:09.560 Der Puffer ist auch leer. 56:10.180 --> 56:12.360 Also gehen Einfügungen einfach in den Puffer. 56:13.040 --> 56:13.940 Also keine IOs. 56:15.460 --> 56:16.960 Natürlich geht das irgendwann schief. 56:17.180 --> 56:19.300 Dann ist der Puffer voll. 56:22.020 --> 56:25.800 Was ich jetzt mache ist, ich sortiere den Puffer. 56:27.880 --> 56:29.260 Kostet auch keine IOs. 56:29.360 --> 56:30.460 Ist ja alles im Hauptspeicher. 56:31.880 --> 56:38.120 Und dann schreibe ich diese sortierte Folge der Länge klein m auf die 56:38.120 --> 56:39.660 Platte in den externen Speicher. 56:39.760 --> 56:40.980 Und das sind diese Dinger hier. 56:41.080 --> 56:42.320 Das Blaue ist extern. 56:43.340 --> 56:45.760 Also ich habe bis zu K sortierte Folgen. 56:47.040 --> 56:50.280 Und das einzige davon, was ich mir im Hauptspeicher habe, ist jeweils 56:50.280 --> 56:54.360 ein Pufferblock mit den kleinsten, noch nicht entfernten Elementen. 56:56.620 --> 57:01.240 Dann habe ich noch eine KW-Gemisch-Datenstruktur. 57:01.620 --> 57:06.940 Die enthält im Endeffekt eine Priority-Queue, wo jeweils für jede 57:06.940 --> 57:08.980 dieser Folgen das kleinste Element drin ist. 57:09.640 --> 57:12.760 Und wenn Sie so wollen, sind diese Pufferblöcke auch Teile dieser KW 57:12.760 --> 57:13.800 -Gemisch -Datenstruktur. 57:16.580 --> 57:18.640 Dann ist irgendwie klar, was passiert. 57:18.640 --> 57:20.800 Einfügen, sortieren. 57:21.020 --> 57:23.940 Wenn der Puffer voll ist, sortieren und rausschreiben. 57:24.620 --> 57:26.500 Und ich merke mir den kleinsten Block. 57:26.600 --> 57:27.620 Den lasse ich im Hauptspeicher. 57:28.600 --> 57:31.440 Und Delete-Min ist jetzt eigentlich auch einfach. 57:31.560 --> 57:36.060 Es gibt zwei Möglichkeiten, wo das global kleinste Element stehen 57:36.060 --> 57:36.360 kann. 57:36.820 --> 57:37.860 Nämlich entweder im Puffer. 57:38.720 --> 57:40.780 Dann kann ich es direkt aus dem Puffer rausholen. 57:41.660 --> 57:45.460 Das kann mir nur helfen, weil ein Element, das ich da raushole, muss 57:45.460 --> 57:47.500 ich niemals sortieren und rausschreiben. 57:49.120 --> 57:50.760 Oder es ist halt irgendwo hier. 57:51.100 --> 57:54.860 Aber es muss eines der kleinsten Elemente dieser Folgen sein. 57:55.320 --> 57:57.040 Das heißt, in dieser Priority-Q sein. 57:57.460 --> 58:00.200 Das heißt, ich muss nur ein Delete-Min aus dieser Priority-Q machen. 58:00.640 --> 58:04.560 Beziehungsweise ich vergleiche das Minimum dieser Priority-Q mit dem 58:04.560 --> 58:06.100 Minimum dieser Priority-Q. 58:06.600 --> 58:10.640 Und je nachdem, welches da kleiner ist, wird dann aus der Q gelöscht 58:10.640 --> 58:11.500 oder aus der. 58:11.940 --> 58:17.140 Und natürlich, wenn ich hier lösche, muss ich dann das nächste Element 58:17.140 --> 58:18.320 aus dem Pufferblock nehmen. 58:18.320 --> 58:23.140 Oder wenn der Pufferblock leer ist, den nächsten Block von der Platte 58:23.140 --> 58:23.560 lesen. 58:24.700 --> 58:26.320 Fragen zu der Datenstruktur? 58:27.320 --> 58:28.460 Analysieren wir das mal. 58:30.420 --> 58:33.580 Das ist wieder eine amortisierte Analyse, aber ich fange jetzt nicht 58:33.580 --> 58:37.080 an, detailliert mit irgendwelchen Tokens um mich zu werfen. 58:38.140 --> 58:39.340 Es ist auch eigentlich ganz einfach. 58:39.460 --> 58:41.200 Jedes Element wird einmal gelesen. 58:43.140 --> 58:45.980 Und zwar zusammen mit B anderen. 58:46.920 --> 58:54.880 Das heißt, für dieses Lesen habe ich einen Penalty von 1 durch B, den 58:54.880 --> 58:58.180 ich auch der Insert-Operation schon zuschlagen kann. 58:58.580 --> 59:02.700 Also ich habe so einen Token im Wert von 1 durch B IOs. 59:03.240 --> 59:05.120 Das muss ich bei jedem Insert bezahlen. 59:06.280 --> 59:10.060 Und das reicht dann aber, um, wenn ich hier so einen Pufferblock, 59:11.060 --> 59:14.760 einen neuen zu lesen, für diese IO-Operation zu bezahlen. 59:16.460 --> 59:21.720 Ansonsten wird jedes Element maximal einmal so einer internen Sortier 59:21.720 --> 59:22.940 -Operation unterworfen. 59:23.040 --> 59:24.260 Das kostet auch keine IOs. 59:24.720 --> 59:25.720 Und dann rausgeschrieben. 59:25.860 --> 59:32.160 Also jedes Element wird maximal einmal geschrieben und maximal einmal 59:32.160 --> 59:32.820 gelesen. 59:35.180 --> 59:39.080 Also ich habe für N Operationen 2 N durch B IOs. 59:42.220 --> 59:46.020 Genauer gesagt sogar für N Einfüge-Operationen und so wie ich das 59:46.020 --> 59:49.600 jetzt amortisiere, sind die Delete-Mins sozusagen umsonst. 59:51.880 --> 59:52.900 Fragen dazu? 59:55.240 --> 59:57.520 Also die Kosten sind tatsächlich amortisiert. 59:58.780 --> 01:00:04.420 2 durch B IO-Operationen pro Insert-Operation und Delete-Mins sind 01:00:04.420 --> 01:00:06.860 amortisiert gesehen umsonst. 01:00:08.060 --> 01:00:10.820 Genau, und wenn ich jetzt über external... 01:00:11.600 --> 01:00:14.640 wenn ich jetzt tatsächlich über Festplatten rede, dann wäre es das 01:00:14.640 --> 01:00:15.580 jetzt auch schon fast. 01:00:16.120 --> 01:00:21.720 Also ich kann jetzt meine Priority Queue so machen, dass ich... 01:00:22.380 --> 01:00:27.220 Also wir haben ja gesagt K darf dann ruhig auch 1000 oder 4000 sein. 01:00:28.540 --> 01:00:33.520 Ich kann dann eine Terabyte große Priority Queue maintainen. 01:00:35.400 --> 01:00:37.660 Allerdings mit einem ziemlich großen Puffer, der dann den 01:00:37.660 --> 01:00:39.060 Hauptspeicher ziemlich voll macht. 01:00:40.960 --> 01:00:48.880 Und ich habe auch schon gesagt, wenn ich über die Cache-Levels der 01:00:48.880 --> 01:00:52.120 Prozessoren rede, funktioniert das vielleicht nicht. 01:00:52.940 --> 01:00:57.780 Und es war tatsächlich dann mein Anliegen damals, eine cache 01:00:57.780 --> 01:00:59.520 -effiziente Priority Queue zu haben. 01:01:01.680 --> 01:01:04.360 Also insbesondere, wie schlage ich Binary Heaps? 01:01:05.680 --> 01:01:07.420 Das hatte bis dahin noch keiner gemacht. 01:01:07.420 --> 01:01:11.200 Also es gab diese theoretischen Ergebnisse, die aber sehr große 01:01:11.200 --> 01:01:13.120 konstante Faktoren da reinbauen. 01:01:14.020 --> 01:01:18.220 Und ich habe gesagt, ich will mir das jetzt genau angucken, kann man 01:01:18.220 --> 01:01:20.540 eine cache-effiziente Priority Queue machen. 01:01:20.660 --> 01:01:25.060 Aber so, dass die theoretisch auch hier das Optimum erreicht. 01:01:26.720 --> 01:01:28.260 Da kommt die Verallgemeinerung. 01:01:28.380 --> 01:01:30.520 Aber hier habe ich noch eine Folie, die ich vergessen habe. 01:01:33.400 --> 01:01:34.320 Interne Arbeit... 01:01:34.320 --> 01:01:35.960 Ist aber nicht so spannend. 01:01:41.240 --> 01:01:45.960 Für Delete-Min habe ich einen Vergleich, um die beiden Dinger zu 01:01:45.960 --> 01:01:47.400 vergleichen. 01:01:48.540 --> 01:01:51.860 Und Log-K-Vergleiche, um Delete-Min hier zu machen. 01:01:52.280 --> 01:01:57.680 Oder Log-M 01:02:01.250 --> 01:02:02.210 hier. 01:02:03.110 --> 01:02:04.730 Oder Log-K hier. 01:02:06.210 --> 01:02:07.830 Aber insgesamt auch von Log-M. 01:02:14.590 --> 01:02:23.830 Und das Insert hat hier M mal Log-M-Operationen pro... 01:02:23.830 --> 01:02:28.930 Einmal das Löschen amortisiert, Log-M pro Operationen. 01:02:29.570 --> 01:02:32.850 Also das ist sehr effizient, was hier passiert. 01:02:35.030 --> 01:02:36.670 Aber wie mache ich die großen Queues? 01:02:36.750 --> 01:02:43.150 Das ist jetzt ein Zusatz, was man eigentlich gerne möchte ist, oder 01:02:43.150 --> 01:02:47.950 das Beste, was man hier erreichen kann, ist, dass es genauso viele IOs 01:02:47.950 --> 01:02:49.590 sind, wie für Sortieren. 01:02:50.450 --> 01:02:54.550 Ich habe ja gesagt, wenn man eine Priority Queue hat, kann man damit 01:02:54.550 --> 01:02:55.130 auch sortieren. 01:02:55.250 --> 01:02:58.570 Ich kann erst alle Elemente einfügen in eine Priority Queue und dann 01:02:58.570 --> 01:02:59.890 mache ich ganz viele Delete-Mins. 01:02:59.890 --> 01:03:06.350 Also besser als dieses 2N durch B 1 plus Log-Basis M durch B N durch M 01:03:06.350 --> 01:03:12.990 kann man nicht werden in der Anzahl IO-Operationen für N-Einfügungen. 01:03:17.870 --> 01:03:22.130 Und das Überraschende war, da habe ich dann ziemlich lange gebastelt, 01:03:22.850 --> 01:03:25.910 dass man das tatsächlich einschließlich des konstanten Faktors 01:03:25.910 --> 01:03:26.690 erreichen kann. 01:03:26.690 --> 01:03:32.250 Es gab wie gesagt mehrere andere Lösungen, auch eine nicht von der 01:03:32.250 --> 01:03:38.790 Arbeitsgruppe, die alle asymptotisch diese Schranke erreicht haben. 01:03:39.010 --> 01:03:42.370 Aber ich war der Erste, der diesen Faktor 2 erreicht hat damals. 01:03:42.690 --> 01:03:47.350 Und das ist eben nicht nur wichtig, wenn man sagt, ich finde jetzt 01:03:47.350 --> 01:03:50.750 konstante Faktoren wichtig, sondern das war eben auch wichtig, um in 01:03:50.750 --> 01:03:53.810 der Praxis tatsächlich eine Verbesserung zu erzielen. 01:03:53.810 --> 01:03:57.830 Und zwar nicht nur, wenn die Daten auf der Festplatte liegen, weil da 01:03:57.830 --> 01:04:01.070 habe ich ja gesagt, da ist sozusagen die naive Implementierung eine 01:04:01.070 --> 01:04:02.230 Million mal schlechter. 01:04:03.370 --> 01:04:06.490 Da kann man sich einen Faktor 3, den man irgendwo wegwirft, leisten. 01:04:06.710 --> 01:04:12.690 Aber wenn ich das auf der Hauptspeicher-Cache-Hierarchie habe, da kann 01:04:12.690 --> 01:04:15.510 man irgendwie einen Faktor 3 oder 4 gewinnen, wie wir sehen werden. 01:04:15.870 --> 01:04:17.410 Und dann darf ich den nicht wegwerfen. 01:04:18.170 --> 01:04:19.470 Deshalb war das ganz wichtig. 01:04:23.580 --> 01:04:27.160 Das ist jetzt auch tatsächlich so, also diese Konkurrenzergebnisse 01:04:27.160 --> 01:04:31.880 sind theoretisch gesehen stärker, weil bei denen dieses N nicht die 01:04:31.880 --> 01:04:35.060 Anzahl Einflüge Operationen ist, sondern die Maximalgröße der Q. 01:04:35.600 --> 01:04:41.080 Das heißt, man kann dann Operationenfolgen definieren, wo diese Q 01:04:43.380 --> 01:04:47.440 schlechter ist als diese Theorie-Datenstruktur. 01:04:49.340 --> 01:04:52.340 Aber eine Anwendung zu finden, bei der das passiert, dürfte einem 01:04:52.340 --> 01:04:53.060 recht schwer fallen. 01:04:54.820 --> 01:04:59.380 Und man zahlt dann immer mit konstanten Faktoren, anderswo, die viel 01:04:59.380 --> 01:05:00.520 schlimmer sind. 01:05:01.460 --> 01:05:03.080 Wie sieht diese Datenstruktur aus? 01:05:04.600 --> 01:05:07.160 Die ist eigentlich sehr ähnlich zu dieser mittelgroßen Q 01:05:07.160 --> 01:05:08.000 -Datenstruktur. 01:05:08.740 --> 01:05:10.200 Ich habe wieder einen Einfügepuffer. 01:05:11.300 --> 01:05:14.220 Wenn der Einfügepuffer voll ist, schreibe ich die Sachen wieder raus 01:05:14.220 --> 01:05:16.720 in sortierte Folgen der Länge M. 01:05:18.100 --> 01:05:19.720 Das neue ist jetzt... 01:05:21.340 --> 01:05:25.000 Also das Problem war ja, ich kann das K hier nicht beliebig groß 01:05:25.000 --> 01:05:25.280 machen. 01:05:26.040 --> 01:05:28.540 Ich kann also nicht beliebig viele von diesen sortierten Folgen 01:05:28.540 --> 01:05:29.700 nebeneinander packen. 01:05:30.500 --> 01:05:31.860 Deshalb mache ich folgendes. 01:05:31.940 --> 01:05:38.240 Wenn ich mehr als K sortierter Folgen habe, nehme ich die Dinger und 01:05:38.240 --> 01:05:42.240 mische sie zusammen zu einer sortierten Folge der Länge K mal M und 01:05:42.240 --> 01:05:46.700 schreibe die in so eine weitere Gruppe von sortierten Folgen. 01:05:46.780 --> 01:05:49.420 Und das kann ich wie oft wiederholen? 01:05:49.480 --> 01:05:51.840 Genau Log Basis M durch B, N durch M. 01:05:52.780 --> 01:05:54.720 Und dann kriege ich mehrere solcher Gruppen. 01:05:55.180 --> 01:05:57.800 In meiner Implementierung habe ich tatsächlich so drei bis vier 01:05:57.800 --> 01:05:59.620 Gruppen, die dann in der Praxis auftreten. 01:06:01.480 --> 01:06:05.940 Und dann ist die Frage, wie man das so macht, dass diese zusätzliche 01:06:08.120 --> 01:06:10.720 Hierarchie -Ebene einem nicht zu viel kostet. 01:06:10.720 --> 01:06:13.260 Und das funktioniert dann so. 01:06:14.600 --> 01:06:17.800 Vor allem, ich habe drei Gruppen, kann mir aber immer nur K-Elemente 01:06:17.800 --> 01:06:19.440 leisten, die ich zusammenmischen kann. 01:06:19.780 --> 01:06:21.340 Deshalb habe ich hier noch so Gruppenpuffer. 01:06:21.760 --> 01:06:23.360 Die haben auch Größe klein m. 01:06:25.300 --> 01:06:29.140 Das heißt, ich amortisiere dann viele Merge-Operationen in einer 01:06:29.140 --> 01:06:37.240 dieser Gruppen über also viele Delete-Min-Operationen aus einer dieser 01:06:37.240 --> 01:06:41.200 Gruppen über einen Puffer, wo ich dann immer gleich M-Stück davon 01:06:41.200 --> 01:06:41.860 raushole. 01:06:42.240 --> 01:06:45.800 Und dann kann ich es mir zum Beispiel auch leisten, Pufferblöcke von 01:06:45.800 --> 01:06:46.760 der Platte zu lesen. 01:06:46.900 --> 01:06:48.900 Man sieht hier auch recht komplexe Farben. 01:06:49.120 --> 01:06:53.060 Die roten Sachen sind im Hauptspeicher, die blauen sind extern. 01:06:53.200 --> 01:06:56.360 Aber es gibt hier so grüne Sachen, die dann hin und her geswappt 01:06:56.360 --> 01:06:59.480 werden, die dann für die asymptotische Analyse auch wichtig sind. 01:07:03.320 --> 01:07:05.980 Und dann habe ich mehrere von den Gruppenpuffern und dann gibt es 01:07:05.980 --> 01:07:08.580 nochmal so einen Mischer und ich habe dann einen kleinen Deletion 01:07:08.580 --> 01:07:08.900 -Puffer. 01:07:09.020 --> 01:07:15.020 Also ich habe eine zusätzliche Hierarchie-Ebene da drin, wie das Ganze 01:07:15.020 --> 01:07:19.660 dann abläuft und warum das dann diese Effizienz hier erreicht. 01:07:19.760 --> 01:07:24.060 Das ist ein relativ komplexes Argument, aber damit möchte ich sie ja 01:07:24.060 --> 01:07:24.880 auch nicht belasten. 01:07:26.620 --> 01:07:32.000 Ich möchte halt nur hervorheben, dass diese einfache Queue hier eine 01:07:32.000 --> 01:07:37.860 Verallgemeinerung hat, die tatsächlich auch sehr gut skaliert für 01:07:37.860 --> 01:07:41.880 beliebig große Eingaben und theoretisch fast das Beste liefert, was 01:07:41.880 --> 01:07:43.600 man sich vorstellen kann. 01:07:44.440 --> 01:07:45.240 Fragen dazu? 01:07:45.860 --> 01:07:48.520 Dann möchte ich Ihnen jetzt auch mal ein paar Experimente dazu 01:07:48.520 --> 01:07:48.920 berichten. 01:07:51.540 --> 01:07:58.580 Wir haben Experimente gemacht mit 32-Bit- Schlüsseln, zufällig 01:07:58.580 --> 01:07:59.080 gewählt. 01:08:00.420 --> 01:08:03.840 32 -Bit- assoziierter Information. 01:08:05.160 --> 01:08:09.240 Dieser Lösch-Puffer, der kann ruhig auch sehr klein sein, der ist 01:08:09.240 --> 01:08:14.460 Größe 32, die Gruppen-Puffer sind Größe 256, Merging-Degrees 128. 01:08:17.800 --> 01:08:19.980 Compiler auf hochoptimierend gesetzt. 01:08:23.580 --> 01:08:27.480 Und wir haben dann diese Parameter tatsächlich festgehalten über ganz 01:08:27.480 --> 01:08:29.460 viele Architekturen, die wir ausprobiert haben. 01:08:30.080 --> 01:08:33.260 Und das hat irgendwie nie einen Unterschied gemacht, wenn man an denen 01:08:33.260 --> 01:08:33.760 dreht. 01:08:34.120 --> 01:08:38.240 Ich habe die Experimente jetzt wiederholt für eine aktuelle 01:08:38.240 --> 01:08:42.380 Architektur, habe da allerdings nicht mehr an den Parametern gedreht. 01:08:42.460 --> 01:08:48.480 Das wäre nochmal ganz spannend, ob das inzwischen nach fast 20 Jahren 01:08:48.480 --> 01:08:52.060 irgendwie sich die Architekturen so stark gewandelt haben, dass man da 01:08:52.060 --> 01:08:53.020 mal dran drehen müsste. 01:08:53.020 --> 01:08:57.060 Aber es funktioniert immer noch ohne Änderung der Parameter ganz gut. 01:08:57.760 --> 01:09:01.440 Wir haben uns meistens die folgende Operationenfolge angeschaut. 01:09:02.260 --> 01:09:05.380 Element einfügen, Element löschen, Element einfügen. 01:09:05.460 --> 01:09:06.840 Das mache ich groß N mal. 01:09:07.320 --> 01:09:10.640 Das heißt, dadurch, das ist immer so, dass es zwei Schritt vor, ein 01:09:10.640 --> 01:09:11.760 Schritt zurück spielt. 01:09:12.440 --> 01:09:16.060 Dann wächst also die Größe der Queue linear. 01:09:17.080 --> 01:09:20.280 Und dann mache ich es umgekehrt, dann mache ich DeleteMin, Insert, 01:09:20.400 --> 01:09:22.520 DeleteMin und dann schrumpft sie wieder linear. 01:09:26.380 --> 01:09:30.500 Wir haben dann auch verschiedene Eingabefolgen untersucht. 01:09:30.620 --> 01:09:32.780 Es war ein bisschen überraschend, dass das dann tatsächlich eine 01:09:32.780 --> 01:09:33.860 gewisse Rolle spielt. 01:09:35.000 --> 01:09:39.380 Trotzdem ist es jetzt vielleicht völlig absurd, sich einfach mal das 01:09:39.380 --> 01:09:40.140 anzuschauen. 01:09:43.000 --> 01:09:44.920 Und jetzt können wir mal gucken, was da passiert. 01:09:45.080 --> 01:09:50.220 Also die beste Maschine damals war der DEC-Alpha-Prozessor mit 500 MHz 01:09:50.220 --> 01:09:51.160 Taktfrequenz. 01:09:51.460 --> 01:09:52.660 Das ist Baujahr 97. 01:09:58.090 --> 01:10:01.030 Und was ich hier plotte, ist dieses groß N. 01:10:01.210 --> 01:10:05.910 Das ist gleichzeitig die maximale Queuegröße und ein Viertel der 01:10:07.130 --> 01:10:07.850 Operationen. 01:10:09.070 --> 01:10:15.210 Auf der Y-Achse plotte ich nicht die Laufzeit, weil die wächst 01:10:15.210 --> 01:10:20.350 natürlich stark an mit der Eingabegröße, sondern ich normiere das 01:10:20.350 --> 01:10:26.370 sozusagen nach einer unteren Schranke für die Anzahl Vergleiche und 01:10:26.370 --> 01:10:31.650 damit habe ich dann sowas wie eine Laufzeit pro Vergleich oder sowas, 01:10:32.550 --> 01:10:33.670 die ich da plotte. 01:10:37.250 --> 01:10:44.810 T-DeleteMin plus T-DeleteInsert geteilt durch LogN, weil ich sowas wie 01:10:44.810 --> 01:10:46.790 LogN -Vergleiche pro Element brauche. 01:10:50.690 --> 01:10:53.910 Das heißt, das ist insbesondere so, dass wenn es keine 01:10:53.910 --> 01:10:59.610 Speicherhierarchie gäbe, müsste man bei einem binären Heap, das sind 01:10:59.610 --> 01:11:04.090 hier diese Kreise, müsste man eigentlich eine flache Kurve erwarten. 01:11:05.170 --> 01:11:08.030 Das ist aber nicht der Fall, bzw. 01:11:08.310 --> 01:11:15.030 das ist am Anfang flach bis bei dieser Architektur 16.384 Elemente und 01:11:15.030 --> 01:11:16.810 dann geht es so langsam linear hoch. 01:11:18.510 --> 01:11:23.590 Das liegt halt daran, dass mit jeder Verdoppelung der Eingabegröße ich 01:11:23.590 --> 01:11:26.110 dann einen zusätzlichen Cache-Fall im Endeffekt kriege. 01:11:29.200 --> 01:11:32.920 Dann gab es ein Paper, das sagt, oh wir haben eine geniale 01:11:32.920 --> 01:11:35.800 Verbesserung von binary Heaps, wir machen 4-ary Heaps. 01:11:36.820 --> 01:11:39.340 Die waren zumindest auf der Architektur tatsächlich ein bisschen 01:11:39.340 --> 01:11:43.140 besser, aber haben natürlich den gleichen Effekt, dass Cache-Falls 01:11:43.140 --> 01:11:44.900 gibt, aber man spart irgendwie einen Faktor. 01:11:45.180 --> 01:11:46.620 Also die Kurve ist flacher. 01:11:46.780 --> 01:11:50.380 Das ist schon ein bisschen besser, aber irgendwie nicht super 01:11:50.380 --> 01:11:50.760 spannend. 01:11:51.480 --> 01:11:56.680 Während unsere Datenstruktur tatsächlich flach ist, was ein bisschen 01:11:56.680 --> 01:11:59.000 überraschend war, dass die Kurve sogar runter geht. 01:12:00.160 --> 01:12:03.320 Da dachten wir erst, das liegt an so Lower Order Terms. 01:12:04.020 --> 01:12:08.880 Es ist aber tatsächlich ein zusätzlicher Effekt, dass diese konkrete 01:12:08.880 --> 01:12:19.040 Operationenfolge führt dazu, dass ein immer größerer Anteil der Delete 01:12:19.040 --> 01:12:21.840 -Min -Operationen aus dem Puffer erfolgt. 01:12:22.180 --> 01:12:28.240 Beziehungsweise wenn ich etwas in den Insertion-Puffer tue und dann 01:12:28.240 --> 01:12:33.060 das Delete-Min sozusagen ein frisch eingefügtes Element löscht, dann 01:12:33.060 --> 01:12:35.300 spart sich das einiges an IO-Operationen. 01:12:35.680 --> 01:12:39.340 Und es ist bei den verallgemeinerten Dingen dann sogar so, was die 01:12:39.340 --> 01:12:42.680 Elemente ja in erster Näherung tun, ist, dass sie erstmal in die 01:12:42.680 --> 01:12:44.700 Gruppe geschrieben werden, dann in die, dann in die. 01:12:45.220 --> 01:12:48.260 Das heißt, sobald ich irgendwas direkt aus dieser Gruppe rausmische 01:12:48.260 --> 01:12:52.940 oder aus der, spare ich auch bereits IOs, die ich kriegen würde, wenn 01:12:52.940 --> 01:12:56.060 das hier wirklich durch alle Gruppen wandert, das Element. 01:12:58.920 --> 01:13:03.340 Und man kann sich überlegen, dass diese Eingabefolge irgendwie dazu 01:13:03.340 --> 01:13:11.240 führt, dass ein frisch eingefügtes Element tendenziell ziemlich klein 01:13:11.240 --> 01:13:13.860 ist verglichen mit den Elementen, die noch in der Queue sind. 01:13:14.300 --> 01:13:17.200 Weil das ist ja eine Priority-Queue, man löscht immer die kleinsten 01:13:17.200 --> 01:13:17.480 Elemente. 01:13:18.260 --> 01:13:21.180 Das heißt, alte Elemente, die schon lange in der Queue sind, sind 01:13:21.180 --> 01:13:22.500 tendenziell ziemlich groß. 01:13:23.320 --> 01:13:27.260 Während frisch eingefügte irgendwie uniform verteilt sind und dann 01:13:27.260 --> 01:13:29.200 eher zu den kleinen gehören. 01:13:29.360 --> 01:13:32.160 Und das ist ein Lokalitätseffekt, von dem man dann tatsächlich 01:13:32.160 --> 01:13:32.840 profitiert. 01:13:33.560 --> 01:13:35.760 Es gibt auch Anwendungen, die diese Struktur haben. 01:13:36.200 --> 01:13:38.640 Man muss allerdings dazu sagen, es gibt auch welche, bei denen das 01:13:38.640 --> 01:13:39.680 tatsächlich nicht passiert. 01:13:40.520 --> 01:13:44.500 Zum Beispiel Dijkstra's Algorithmus macht ja, hat ja monotone Priority 01:13:44.500 --> 01:13:47.660 -Queues, wo halt die eingefügten Elemente immer größer werden. 01:13:48.080 --> 01:13:51.840 Weil das ist ja dann so dieser sich ausbreitende Suchradius des 01:13:51.840 --> 01:13:52.940 Dijkstra -Algorithmus. 01:13:52.940 --> 01:13:55.240 Da profitiert man nicht davon. 01:13:55.760 --> 01:13:58.880 Das heißt, wenn man jetzt andere Eingabefolgen angucken würde, würde 01:13:58.880 --> 01:14:00.900 man tatsächlich hier was Flaches sehen. 01:14:01.100 --> 01:14:07.800 Trotzdem gewinnt man irgendwie einen deutlichen Faktor gegenüber 01:14:07.800 --> 01:14:08.400 Konkurrenzimplementierung. 01:14:08.900 --> 01:14:11.760 Und dann ist natürlich aus heutiger Sicht spannend, wie sieht das 20 01:14:11.760 --> 01:14:12.800 Jahre später aus? 01:14:13.700 --> 01:14:17.160 Da habe ich eine einigermaßen aktuelle Architektur von den letzten 01:14:17.160 --> 01:14:25.210 Jahren, AMD Ryzen 1800X mit 16 MB L3-Cache, 3,6 GHz Taktfrequenz. 01:14:26.900 --> 01:14:28.420 Der ist tatsächlich 01:14:31.480 --> 01:14:36.180 Faktor 20 oder sowas schneller als dieser DC-Alpha. 01:14:37.340 --> 01:14:41.640 Aber was jetzt spannender ist, wir haben eigentlich die Kurve sieht 01:14:41.640 --> 01:14:48.520 qualitativ genau so aus, außer vielleicht, dass der Binary-Heap einen 01:14:48.520 --> 01:14:50.160 viel steileren Anstieg hat. 01:14:50.440 --> 01:14:55.940 Also diese ganze Performance-Steigerung, die ich kriege durch Erhöhung 01:14:55.940 --> 01:15:00.040 von Taktfrequenzen, durch Erhöhung des Instruktionsparallelismus, 01:15:02.060 --> 01:15:06.220 kriege ich tatsächlich nur, wenn ich Cachefalls vermeide. 01:15:06.320 --> 01:15:09.340 Also der Penalty für ein Cachefall ist viel höher geworden als damals, 01:15:11.200 --> 01:15:14.820 weil eben die Latenzen beim Speicherzugriff nicht so stark abgenommen 01:15:14.820 --> 01:15:19.140 haben, wie die Taktfrequenzen zugenommen haben. 01:15:20.000 --> 01:15:26.400 Und hier habe ich praktisch wieder dieses flache Verhalten und am Ende 01:15:26.400 --> 01:15:29.060 einen Faktor 4 gewinnen und das ist eigentlich das gleiche wie der 01:15:29.060 --> 01:15:33.420 Faktor 4, den ich hier hatte, außer dass ich jetzt bis zu 2x30 01:15:33.420 --> 01:15:37.660 Elementen gehen muss, um das zu beobachten und damals bis 2x23. 01:15:38.400 --> 01:15:45.920 Aber das ist auch irgendwie klar, 2x23 das ist hier da passt die 01:15:45.920 --> 01:15:49.740 Eingabe fast noch in den Cache in den L3-Cache zumindest. 01:15:50.640 --> 01:15:52.580 Also das finde ich ein ganz interessantes Ergebnis, dass ein 01:15:52.580 --> 01:15:56.560 sorgfältig entworfener Algorithmus auch über 20 Jahre immer noch seine 01:15:56.560 --> 01:15:58.680 Performance -Vorteile behält. 01:16:00.240 --> 01:16:03.380 So, das waren Priority Queues. 01:16:04.240 --> 01:16:07.320 Jetzt möchte ich mal einen ganz einfachen Graphen-Algorithmus im 01:16:07.320 --> 01:16:13.940 External Memory vorstellen und zwar minimale Spannbäume mit Großkreis 01:16:13.940 --> 01:16:14.600 -Algorithmus. 01:16:16.200 --> 01:16:18.380 Und da machen wir es uns einfach. 01:16:19.120 --> 01:16:24.060 Wir nehmen keinen voll allgemeinen minimalen Spannbaum-Algorithmus, 01:16:24.220 --> 01:16:25.880 sondern einen sogenannten Semi-Externen. 01:16:27.280 --> 01:16:33.200 Semi-Externe Graphen-Algorithmen sind solche, bei denen ich pro Knoten 01:16:33.200 --> 01:16:37.020 konstant viele Maschinenworte im Hauptspeicher halten kann. 01:16:39.000 --> 01:16:44.920 Also M ist gleich Omega klein n, wenn n die Anzahl Knoten ist. 01:16:46.440 --> 01:16:50.080 Das heißt, die Kanten liegen auf der Platte und für die Knoten kann 01:16:50.080 --> 01:16:52.640 ich aber konstant viel Information intern verwalten. 01:16:53.660 --> 01:16:57.940 Das erleichtert mir den Entwurf von IO-effizienten Graphen 01:16:57.940 --> 01:16:58.460 -Algorithmen. 01:17:00.140 --> 01:17:05.420 Also hier die Prozedur Semi-Externer Kruskal, Eingabe ist ein Graph 01:17:05.420 --> 01:17:11.220 mit Knotenmenge 1-n und eben einer Kantenmenge. 01:17:14.000 --> 01:17:16.980 Was noch ganz interessant ist, ich brauche eigentlich gar keine Graph 01:17:16.980 --> 01:17:17.640 -Datenstruktur. 01:17:18.840 --> 01:17:24.080 Ich habe einfach eine Datei, die eine Liste von Kanten enthält. 01:17:25.680 --> 01:17:30.040 Kante ist einfach ein Trippel, ein Knoten, noch ein Knoten und 01:17:30.040 --> 01:17:30.400 Gewicht. 01:17:31.880 --> 01:17:35.300 Und diese Liste E sortiere ich nach absteigendem Gewicht. 01:17:35.420 --> 01:17:39.220 Das ist das gleiche, wie beim Kruskal-Algorithmus ohnehin gemacht 01:17:39.220 --> 01:17:39.540 wird. 01:17:39.840 --> 01:17:44.320 Nur, dass ich hier jetzt einen externen Algorithmus wähle und der hat 01:17:44.320 --> 01:17:46.060 dann eben SortM IOs. 01:17:47.220 --> 01:17:53.620 Und SortM war dieses 2n durch b mal 1 plus log Basis bla aufgerundet. 01:17:54.960 --> 01:17:59.040 So, jetzt deklariere ich eine Union-Find-Datenstruktur. 01:17:59.240 --> 01:18:02.180 Das ist jetzt genau der interne Algorithmus. 01:18:03.340 --> 01:18:08.060 Union-Find-Datenstruktur war eine Datenstruktur, die eine Partition 01:18:08.060 --> 01:18:10.380 meiner Eingabemenge verwaltet. 01:18:10.920 --> 01:18:13.160 Und ich habe die Operation Find und Union. 01:18:15.040 --> 01:18:19.300 Und Find liefert mir immer einen Repräsentanten einer Menge zurück. 01:18:19.440 --> 01:18:26.480 Und Union fügt zwei Elementen zusammen und wenn ich sie gebaut habe, 01:18:26.500 --> 01:18:32.120 am Anfang habe ich eine triviale Partition, wo jedes Element eine 01:18:32.120 --> 01:18:33.500 eigene Teilmenge darstellt. 01:18:34.140 --> 01:18:38.780 Und das Ganze repräsentiert sozusagen den minimalen spannenden Baum 01:18:38.780 --> 01:18:41.400 der Kanten, die ich bereits gesehen habe. 01:18:42.040 --> 01:18:44.100 Erinnern Sie sich vielleicht das Algorithm 1 dran. 01:18:45.460 --> 01:18:52.020 Und was Kruskals Algorithmus macht, er iteriert durch die Kanten in 01:18:52.020 --> 01:18:52.100 ... 01:19:00.190 --> 01:19:05.330 aber ich kann natürlich auch andersrum iterieren, also es ist nicht 01:19:05.330 --> 01:19:06.270 falsch, was da steht. 01:19:06.650 --> 01:19:09.470 Also ich iteriere durch die Kanten in aufsteigender 01:19:10.470 --> 01:19:10.990 Gewichtsreihenfolge. 01:19:11.650 --> 01:19:15.890 Das heißt, ich lese in der Datei, das sind 2n durch b i. 01:19:18.550 --> 01:19:24.470 Wenn ich eine Kante uv gelesen habe, vergleiche ich die Repräsentanten 01:19:24.470 --> 01:19:26.650 der Partitionen, in denen u und v sind. 01:19:27.230 --> 01:19:31.570 Wenn die gleich sind, weiß ich, dass ich die Kante für den minimalen 01:19:31.570 --> 01:19:32.850 Spannbaum nicht brauche. 01:19:33.910 --> 01:19:36.470 Das war die Grundidee hinter dem Kruskals Algorithmus. 01:19:37.470 --> 01:19:42.130 Wenn sie nicht gleich sind, weiß ich, dass ich das als MST-Kante 01:19:42.130 --> 01:19:46.750 verwenden kann, gebe das aus und mache union auf uv. 01:19:46.890 --> 01:19:49.930 Und das ist natürlich wichtig, dass das hier im Hauptspeicher 01:19:49.930 --> 01:19:53.230 passieren kann, weil diese Union-Find-Daten-Struktur, das sind im 01:19:53.230 --> 01:19:57.810 Prinzip irgendwelche Pointer, die ich verfolgen muss. 01:19:57.970 --> 01:20:00.890 Und das auf der Platte zu machen, wäre sehr toll. 01:20:05.290 --> 01:20:07.130 Was gibt es dazu noch zu sagen? 01:20:10.350 --> 01:20:11.450 Erstmal nicht viel. 01:20:11.610 --> 01:20:15.530 Also es ist eigentlich genau der Kruskal Algorithmus, nur dass ich 01:20:15.530 --> 01:20:19.310 noch dazu sage, die Daten liegen halt auf der Platte. 01:20:19.650 --> 01:20:22.210 Also einfacher geht es nicht für einen externen Algorithmus. 01:20:27.160 --> 01:20:33.280 Und die Gesamtkosten sind jetzt so viel wie sortieren plus einmal 01:20:33.280 --> 01:20:35.240 lesen plus die Ausgabe schreiben. 01:20:38.520 --> 01:20:41.440 Wer hat eine Idee, wie man das noch weiter reduzieren kann? 01:20:42.120 --> 01:20:46.080 Nehmen wir mal an, wir würden multivariable merge sort verwenden für 01:20:46.080 --> 01:20:46.760 das Sortieren. 01:20:47.660 --> 01:20:49.000 Also was macht multivariable merge sort? 01:20:49.100 --> 01:20:57.840 Das liest die RANs und schreibt die Ausgabe in sortierter Reihenfolge. 01:20:58.920 --> 01:21:01.380 Die Kanten, die ich da ausgebe, die brauche ich gar nicht erst auf 01:21:01.380 --> 01:21:02.120 Platte schreiben. 01:21:02.820 --> 01:21:05.600 Die kann ich dann gleich hier in dieser Hauptschleife verwenden, wenn 01:21:05.600 --> 01:21:06.160 ich das will. 01:21:07.240 --> 01:21:11.620 Zumindest, wenn ich es mir leisten kann, diese Pufferblöcke für das 01:21:11.620 --> 01:21:16.500 Multivariable Merging gleichzeitig mit der Union-Find-Daten-Struktur 01:21:16.500 --> 01:21:17.660 im Hauptspeicher zu halten. 01:21:18.840 --> 01:21:22.920 Dann ist es sogar so, dass das Ganze billiger ist als Sortieren, weil 01:21:22.920 --> 01:21:25.860 ich die Ausgabe gar nicht schreiben muss, sondern das Einzige, was ich 01:21:25.860 --> 01:21:29.420 schreiben muss, ist der MST und der hat nur N Kanten und nicht M. 01:21:32.180 --> 01:21:37.740 Im Endeffekt ist dieser semi-externe Kurskal ein bisschen billiger als 01:21:37.740 --> 01:21:38.880 die Kanten-Sortieren. 01:21:39.480 --> 01:21:44.540 Und die Union-Find-Daten-Struktur, die ist fast vernachlässigbar, weil 01:21:44.540 --> 01:21:49.680 ich da Log-M-Vergleiche habe, die verglichen mit den fast konstant 01:21:49.680 --> 01:21:53.840 vielen Operationen für so einen Union-Find vernachlässigbar sind. 01:21:54.700 --> 01:21:57.580 Noch Fragen zum semi-externen Kurskal? 01:21:58.320 --> 01:22:00.000 Dann ein bisschen Blick über den Tellerrand. 01:22:00.120 --> 01:22:06.160 Wenn ich noch größere MSTs berechnen will, brauche ich zusätzliche 01:22:06.160 --> 01:22:06.580 Ideen. 01:22:06.580 --> 01:22:10.300 Auch Dinge, die darüber hinausgehen, was wir in Algorithmen 1 an 01:22:10.300 --> 01:22:11.780 Algorithmen kennengelernt haben. 01:22:13.100 --> 01:22:20.460 Der wichtigste Trick ist, wenn ich MST-Kanten identifiziert habe, wie 01:22:20.460 --> 01:22:22.980 auch immer, kann ich die kontrahieren. 01:22:23.100 --> 01:22:27.860 Das heißt, ich identifiziere die beiden Endpunkte und baue also neuen 01:22:27.860 --> 01:22:29.300 Graphen mit weniger Knoten. 01:22:31.900 --> 01:22:37.340 Und wenn ich das weit genug treibe, also viele Kanten kontrahieren 01:22:37.340 --> 01:22:41.580 kann, kann ich einen Graphen, bei dem das N zu groß ist für meinen 01:22:41.580 --> 01:22:45.720 semi -externen Algorithmus, sozusagen schrumpfen zu einem Graphen, der 01:22:45.720 --> 01:22:50.640 viel weniger Knoten hat, aber ungefähr gleich viele Kanten und auf dem 01:22:50.640 --> 01:22:52.900 dann den semi-externen Kurskal ausführen lassen. 01:22:54.920 --> 01:23:00.340 Und was jetzt für diese Vorlesung vielleicht besonders elegant ist, 01:23:01.340 --> 01:23:06.960 wenn man das richtig macht, ist dieses Schrumpfen braucht im 01:23:06.960 --> 01:23:09.800 Wesentlichen eine externe Priority Queue. 01:23:12.300 --> 01:23:17.160 Und die gibt es zum Beispiel auch in der External Memory Algorithmen 01:23:17.160 --> 01:23:20.360 Bibliothek STXXL, die ein Doktorand von mir gemacht hat. 01:23:21.360 --> 01:23:25.740 Und wenn man das dann verwendet, kann man einen ganz allgemeinen 01:23:25.740 --> 01:23:30.920 externen MST-Algorithmus in einer zweistelligen Anzahl Zeilen einen 01:23:30.920 --> 01:23:31.580 Code hinschreiben. 01:23:38.120 --> 01:23:41.740 Das war damals die Bachelor-Arbeit von Dominik Schultes. 01:23:42.640 --> 01:23:46.480 Der hat dann außerdem noch diese allgemeine Priority Queue durch etwas 01:23:46.480 --> 01:23:50.840 ersetzt, was irgendwie ausnutzt, dass man da im Wesentlichen 01:23:50.840 --> 01:23:56.520 ganzzahlige Prioritäten mitarbeiten kann. 01:23:57.640 --> 01:24:00.000 Und da will ich Ihnen jetzt die Messergebnisse zuvorführen. 01:24:03.540 --> 01:24:08.420 Ich habe hier erstmal sehr dünn besetzte Graphen mit M ungefähr gleich 01:24:08.420 --> 01:24:09.020 2n. 01:24:11.360 --> 01:24:17.080 Und hier erstmal die klassischen internen Algorithmen, Kruskals 01:24:17.080 --> 01:24:18.900 Algorithmus und Prims Algorithmus. 01:24:19.200 --> 01:24:22.120 Und hier die Zeit pro Kante in Mikrosekunden. 01:24:23.100 --> 01:24:25.320 Und dann sehen wir hier die internen Algorithmen. 01:24:25.320 --> 01:24:30.600 Da ist jetzt bei den sehr dünnen Kruskal deutlich effizienter und dann 01:24:30.600 --> 01:24:34.300 hier der Prims Algorithmus und auf der damaligen Maschine war halt bei 01:24:34.300 --> 01:24:37.680 20 Millionen Kanten dann Schluss für den internen Algorithmus. 01:24:40.240 --> 01:24:41.720 Der externe Algorithmus 01:24:45.380 --> 01:24:49.920 da zeige ich jetzt unseren Algorithmus für drei verschiedene 01:24:49.920 --> 01:24:55.800 Instanzklassen, Random-Graphen, Geometrische Graphen und Grid-Graphen. 01:24:56.960 --> 01:25:00.220 Und was wir da sehen, ist am Anfang der semi-externe Algorithmus. 01:25:01.200 --> 01:25:03.620 Dem ist das mehr oder weniger egal, was für Graphen das sind. 01:25:04.160 --> 01:25:08.420 Und wir sehen außerdem, das ganze kostet groben Faktor 2 gegenüber 01:25:08.420 --> 01:25:09.900 einem internen Kruskal. 01:25:11.020 --> 01:25:14.100 Und das ist sehr moderat. 01:25:14.140 --> 01:25:16.940 Es war damals mit mehreren Festplatten implementiert. 01:25:18.640 --> 01:25:26.380 Und dann ab 320 Millionen Kanten musste man dann diese Kontraktionen 01:25:26.380 --> 01:25:26.800 durchführen. 01:25:26.900 --> 01:25:31.980 Das kostet dann nochmal einen Faktor 2 und dann differenzieren sich 01:25:31.980 --> 01:25:33.860 die Eingabe-Arten hier aus. 01:25:34.120 --> 01:25:40.260 Also dieser kontraktionsbasierter Algorithmus der ist bei Grid- und 01:25:40.260 --> 01:25:43.920 Geometrischen Graphen funktioniert der ziemlich gut, nicht nur die 01:25:43.920 --> 01:25:46.500 Knotenzahl zu reduzieren, sondern auch die Kantenzahl. 01:25:46.940 --> 01:25:49.380 Während bei Zufalls-Graphen das dann tatsächlich nochmal ein bisschen 01:25:49.380 --> 01:25:49.880 hochgeht. 01:25:52.540 --> 01:25:56.880 Aber was wir sehen, es ist tatsächlich so, dass man externe Memory 01:25:56.880 --> 01:26:02.420 -MSTs sind eine relativ günstige Operation. 01:26:04.040 --> 01:26:09.640 Was für heute allerdings wichtig ist, eine externe Prioritätsliste und 01:26:09.640 --> 01:26:14.040 auch Kruskalls-Algorithmus sind irgendwie inherent sequenzielle Dinge. 01:26:16.080 --> 01:26:21.440 Also dieses Ergebnis ist nicht ohne weiteres auf parallele Algorithmen 01:26:21.440 --> 01:26:22.200 übertragbar. 01:26:22.780 --> 01:26:26.860 Deshalb ist es heute eigentlich wieder ein bisschen offen, was der 01:26:26.860 --> 01:26:32.200 beste parallele externe Algorithmus für minimale Spannbäume wäre. 01:26:33.600 --> 01:26:37.400 Und wenn man will, wäre das auch ein Bachelor-Arbeitsthema oder Master 01:26:37.400 --> 01:26:40.580 -Arbeitsthema, das man sich mal wieder anschauen könnte. 01:26:42.080 --> 01:26:45.140 Also im Gegensatz zu dieser Priority-Queue, die man trotzdem auch 01:26:45.140 --> 01:26:53.640 sequenziell braucht, ist das für Cash-effiziente Queues will man das 01:26:53.640 --> 01:26:56.520 für MSTs nicht unbedingt verwenden, sondern echt parallelen 01:26:56.520 --> 01:26:57.340 Algorithmus haben. 01:26:58.280 --> 01:26:59.840 Da ist das Ergebnis ein bisschen veraltet. 01:27:01.000 --> 01:27:04.340 Aber trotzdem ganz interessant, dass man durch Zusammensetzung dieser 01:27:04.340 --> 01:27:07.600 Ergebnisse, die wir hier vorgeführt haben, auch einen nicht trivialen 01:27:07.600 --> 01:27:08.800 Graphen -Algorithmus kriegt. 01:27:10.200 --> 01:27:15.060 So, dann spare ich Ihnen mal die letzte Folge, sondern mache den Wrap 01:27:15.060 --> 01:27:17.640 -Up dann beim nächsten Mal. 01:27:18.160 --> 01:27:21.260 Und dann gehen wir zum nächsten Kapitel, Approximations-Algorithmus. 01:27:21.460 --> 01:27:21.880 Vielen Dank.