WEBVTT 00:00.000 --> 00:03.100 Ich begrüße Sie zu einer weiteren Fortsetzung der Vorlesung 00:03.100 --> 00:04.140 effizienter Algorithmen. 00:04.900 --> 00:07.330 Wir sind im Kapitel 5, Suchen und Sortieren. 00:07.740 --> 00:11.680 Wir haben uns mit einem der Lieblingsthemen der Informatiker 00:11.680 --> 00:14.460 beschäftigt, mit dem Suchen und Sortieren. 00:14.900 --> 00:19.980 Davor hatten wir ja die Algebraischen Probleme betrachtet und hier 00:19.980 --> 00:22.090 sind wir schon relativ weit gekommen. 00:24.510 --> 00:27.530 Wir hatten hier verschiedenste Dinge angeguckt. 00:27.670 --> 00:31.330 Wir hatten einfache Verfahren betrachtet, parallele Varianten. 00:31.910 --> 00:34.710 Wir hatten Bubble Sort und die parallele Variante Odd-Even 00:34.710 --> 00:36.190 -Transposition Sort betrachtet. 00:36.330 --> 00:39.990 Ich habe Ihnen da diesen Beweis vorgeführt, wo man so visuell sehen 00:39.990 --> 00:46.090 konnte, wie dort induktiv gezeigt werden kann, dass N solche Odd-Even 00:46.090 --> 00:49.230 -Schritte ausreichen, um eine Folge der Länge N zu sortieren. 00:49.230 --> 00:52.010 Wir haben QuickSort nochmal kurz betrachtet. 00:52.250 --> 00:58.270 Nach der Analyse von QuickSort ging es zu dem Merge Sort. 00:58.790 --> 01:03.130 Und da haben wir gesehen, wenn man das Verschmelzen parallel machen 01:03.130 --> 01:06.370 kann, kann man ja vielleicht einiges an Zeit gewinnen. 01:07.210 --> 01:11.670 Und ein paralleles Verfahren war das Verfahren Odd-Even-Merge Sort, wo 01:11.670 --> 01:16.010 wir uns insbesondere mit diesem Merge beschäftigt haben und damit, 01:16.150 --> 01:17.630 wieso das eigentlich korrekt ist. 01:17.810 --> 01:21.670 Ich habe Ihnen gezeigt, dass es ausreicht, die Null-Eins-Folgen zu 01:21.670 --> 01:22.290 betrachten. 01:23.430 --> 01:26.270 Sehr wichtiges Prinzip, das Null-Eins-Prinzip, dass es uns eben 01:26.270 --> 01:30.230 erlaubt, Korrektheitsbeweise für Sortierverfahren zu machen. 01:30.950 --> 01:34.210 Allein über Null-Eins-Folgen eine wesentliche Vereinfachung dieser 01:34.210 --> 01:38.510 Beweise, die aber dann völlig ausreichend ist, um etwas für alle 01:38.510 --> 01:40.530 beliebigen Folgen sagen zu können. 01:40.730 --> 01:42.770 Und wir haben das dann auch bewiesen, das Null-Eins-Prinzip. 01:42.770 --> 01:44.050 Ich habe Ihnen das nochmal gezeigt. 01:44.850 --> 01:49.070 Diese Korrespondenz eines Sortierverfahrens bzw. 01:49.570 --> 01:53.010 eines parallelen Verfahrens mit einem Vergleichernetz. 01:53.810 --> 01:56.170 Ein Vergleichernetz kann man im Prinzip direkt in Hardware 01:56.170 --> 01:59.870 implementieren, indem man einfach jeden Vergleich zu einem Baustein 01:59.870 --> 02:02.450 macht und dann entsprechend hintereinander schaltet. 02:03.230 --> 02:06.350 Das ist also eine sehr einfache Korrespondenz, wobei man hier sieht, 02:06.350 --> 02:11.230 dass die senkrechten Linien entsprechend der Position der einzelnen 02:11.230 --> 02:12.910 Elemente entsprechen, die sortiert werden sollen. 02:14.570 --> 02:18.390 Die Vergleiche erstrecken sich hier immer über ziemliche Distanzen 02:18.390 --> 02:21.490 zwischen den so aufgereihten Elementen. 02:22.510 --> 02:26.750 Mal also über Distanz in halbe, am Ende dann nur Distanz 1. 02:26.930 --> 02:29.870 Aber wenn man das in Hardware realisieren will, wird das ein bisschen 02:29.870 --> 02:32.630 schwierig, diese langen Verbindungen hinzubekommen bzw. 02:32.710 --> 02:35.070 man braucht dann auf jeden Fall lange Leitungen. 02:35.070 --> 02:39.210 Das ist etwas, was ich nicht weiter ausführe, die Hardware 02:39.210 --> 02:39.890 -Implementierung. 02:40.050 --> 02:42.630 Aber da ist tatsächlich bei diesem Verfahren ein Problem, dass der 02:42.630 --> 02:47.290 Aufwand für die Leitungen relativ groß ist und dass das deswegen nicht 02:47.290 --> 02:51.670 unbedingt so einfach implementiert werden kann. 02:52.350 --> 02:55.010 Dann kommt heute die erste neue Folie. 02:56.410 --> 03:03.050 Da geht es jetzt um eine Variante des parallelen Sortierens, bei der 03:03.050 --> 03:08.490 wir uns zunächst mal eine spezielle Folge anschauen, nämlich die 03:08.490 --> 03:10.270 sogenannten bitonischen Folgen. 03:11.090 --> 03:12.910 Was ist eine bitonische Folge? 03:13.090 --> 03:16.890 Das ist eine zyklische Verschiebung einer auf- und absteigenden Folge. 03:17.050 --> 03:20.310 Also das hier ist eine auf- und absteigende Folge, die ist also nicht 03:20.310 --> 03:24.470 sortiert, sondern sie ist im ersten Teil hier sortiert, da geht es 03:24.470 --> 03:26.110 alles schön rauf und dann geht es aber wieder runter. 03:26.110 --> 03:29.650 Wenn man das jetzt zyklisch verschiebt, dann bekommt man sowas in 03:29.650 --> 03:30.330 dieser Art. 03:31.490 --> 03:34.210 Das heißt, es geht runter, es geht wieder rauf, es geht wieder runter. 03:34.390 --> 03:37.270 Das heißt, wir haben so einen Wechsel zwischen auf- und absteigend. 03:38.290 --> 03:42.070 Und wenn wir uns das jetzt mit Null-Eins-Folgen betrachten, wir wissen 03:42.070 --> 03:44.350 ja, wir können uns beschränken auf die Betrachtung von Null-Eins 03:44.350 --> 03:49.930 -Folgen, dann sind das im Prinzip diese beiden Arten von Null-Eins 03:49.930 --> 03:52.610 -Folgen, bei denen wir erst Nullen haben, dann Einsen, dann wieder 03:52.610 --> 03:55.130 Nullen, also aufsteigend und absteigend. 03:55.410 --> 03:58.550 Oder wir haben das Gegenteil, wir haben erst Einsen, dann Nullen und 03:58.550 --> 03:59.750 dann wieder Einsen. 04:00.210 --> 04:03.030 Vielmehr ist das nicht, wenn man sich darauf beschränkt, kann man also 04:03.030 --> 04:05.730 alles andere dann damit zeigen. 04:07.510 --> 04:13.450 Und das ist, wenn man Aussagen machen will darüber, wie z.B. 04:13.650 --> 04:16.830 bitonische Folgen jetzt richtig sortiert werden können, reicht es, 04:16.990 --> 04:18.250 solche Folgen zu betrachten. 04:19.670 --> 04:23.670 Ein Verfahren, mit dem man bitonische Folgen sortieren kann, die sind 04:23.670 --> 04:26.890 ja schon fast vorsortiert, da ist ja gar nicht mehr viel zu tun, wenn 04:26.890 --> 04:29.110 die schon so aufsteigend, absteigend sortiert sind. 04:30.070 --> 04:33.450 Ein Verfahren, um das zu tun, ist hier unten angedeutet. 04:34.090 --> 04:38.630 Das sieht ganz ähnlich aus wie unser Verfahren, das wir hatten, um ein 04:38.630 --> 04:42.030 paralleles Merge-Sort zu machen. 04:43.730 --> 04:46.430 Also nochmal zurück, das war auf der vorigen... 04:47.490 --> 04:50.130 Hier auf der Folie sehen Sie das Vergleichernetz. 04:50.870 --> 04:56.030 Das sieht doch ganz ähnlich aus, diese Folie und die nächste Folie, 04:56.130 --> 04:57.990 die nächsten Vergleiche. 04:58.330 --> 05:02.150 Hier oben, das ist völlig identisch, also dieser Teil hier. 05:03.190 --> 05:05.010 Und danach sieht es ein bisschen anders aus, da haben wir mehr 05:05.010 --> 05:05.240 Vergleiche. 05:06.010 --> 05:09.070 Aber Sie sehen, dass sich das Muster, das wir hier in dem oberen Teil 05:09.070 --> 05:13.810 betrachten, dann dort wiederholt, dort auch nochmal und dort auch 05:13.810 --> 05:14.250 nochmal. 05:15.230 --> 05:19.690 Nämlich wir haben zunächst mal hier bei einer folgenden Länge 16, acht 05:19.690 --> 05:25.950 Vergleiche, wo jeweils das erste Element oder das Element i, wenn wir 05:25.950 --> 05:32.530 hier uns das angucken, Element i, wird verglichen mit dem Element i 05:32.530 --> 05:33.930 plus n. 05:34.410 --> 05:37.970 Oder nehmen wir mal an, i plus n halber. 05:37.970 --> 05:41.630 Wenn wir n Elemente haben, i plus n halber. 05:43.190 --> 05:47.830 Das heißt, wir haben hier immer Abstände, gerade Länge n halber, die 05:47.830 --> 05:50.030 Abstände zwischen den betrachteten Folgen. 05:50.590 --> 05:59.250 Das wird zunächst mal gemacht mit dem großen Abstand, dann parallel 05:59.250 --> 06:05.170 mit einem Abstand n viertel jeweils nebeneinander und dann viermal 06:05.170 --> 06:09.350 parallel mit einem Abstand n achtel und so weiter. 06:09.730 --> 06:12.430 Und dann haben wir am Ende bei diesem Beispiel dann nur noch 06:12.430 --> 06:14.270 Vergleiche von benachbarten. 06:14.630 --> 06:18.890 Aber man sieht, das ist ein sehr schön rekursives, oder es basiert auf 06:18.890 --> 06:20.010 einem rekursiven Verfahren. 06:20.110 --> 06:21.710 Hier ist es iterativ aufgemalt. 06:21.870 --> 06:25.370 Wir machen also erst große Vergleiche, etwas kleinere, dann noch 06:25.370 --> 06:25.890 kleinere. 06:26.590 --> 06:30.010 So, wieso ist das korrekt? 06:30.130 --> 06:31.330 Schauen wir uns an, was passiert. 06:32.210 --> 06:34.250 Wir machen diese Vergleiche. 06:35.490 --> 06:40.070 Hier ist eine solche betonische Folge angegeben. 06:42.110 --> 06:45.730 Wir haben also eine betonische Folge der Art, wie sie hier oben 06:45.730 --> 06:46.750 angegeben ist. 06:47.630 --> 06:49.250 Erst Nullen, dann Einsen, dann Nullen. 06:49.310 --> 06:50.210 Die wollen wir jetzt sortieren. 06:50.370 --> 06:52.570 Wenn wir diese Vergleiche machen, was passiert? 06:53.150 --> 06:56.230 Die Einsen wandern natürlich alle nach rechts, weil wir ja die 06:56.230 --> 06:58.090 Vergleiche in ein Comparison Exchange machen. 06:58.090 --> 07:00.470 Und die Nullen wandern dann nach links. 07:00.590 --> 07:03.970 Das heißt, wir haben in diesem Augenblick hier links eine Folge, die 07:03.970 --> 07:04.790 ist ja schon sortiert. 07:05.350 --> 07:06.570 Da sind ja schon nur noch Nullen. 07:07.450 --> 07:11.590 Und rechts sehen wir, das ist eine betonische Folge. 07:12.050 --> 07:14.690 Nämlich das sind Einsen, dann eine Null und dann Einsen. 07:15.970 --> 07:17.450 Das ist von diesem Typ hier oben. 07:18.430 --> 07:19.370 Dann geht es weiter. 07:19.510 --> 07:21.590 Links kann ja nichts mehr passieren, das bleiben die Nullen. 07:22.090 --> 07:23.410 Rechts passiert folgendes. 07:23.930 --> 07:26.270 Da haben wir jetzt rechts die ganzen Einsen. 07:26.270 --> 07:30.130 Hier sind die ganzen Einsen. 07:32.490 --> 07:36.030 Und die Nullen, da hat sich nicht viel getan, da hat sich nicht viel 07:36.030 --> 07:36.490 verändert. 07:37.550 --> 07:42.170 Aber auf jeden Fall haben wir jetzt hier eine Folge, die ist vom Typ 07:42.170 --> 07:43.250 Eins. 07:43.630 --> 07:46.050 Das können Sie nehmen, wie Sie wollen, von den beiden. 07:46.410 --> 07:48.330 Wir haben hier Einsen gefolgt von der Null. 07:48.990 --> 07:50.590 Und rechts ist schon alles sortiert. 07:52.010 --> 07:53.050 Und dann geht es weiter. 07:53.730 --> 07:58.750 Dann haben Sie rechts eine sortierte Folge. 07:59.330 --> 08:00.510 Alle anderen sind ja schon sortiert. 08:00.610 --> 08:02.670 Und hier haben Sie nochmal eine betonische Folge. 08:02.970 --> 08:04.270 Eine Eins gefolgt von einer Null. 08:04.870 --> 08:06.990 Und anschließend noch ein Vergleich und alles ist sortiert. 08:08.150 --> 08:09.320 Was sieht man hierbei? 08:10.570 --> 08:12.670 Wir haben eine betonische Folge genommen. 08:14.650 --> 08:21.310 Und nach jeder Stufe der Vergleiche haben wir zwei Folgen halber 08:21.310 --> 08:21.630 Länge. 08:24.190 --> 08:28.790 Und es ist so, dass die linke Folge kleiner gleich der rechten Folge 08:28.790 --> 08:29.270 ist. 08:30.390 --> 08:36.550 Hier stehen nur Nullen, da rechts stehen überall Einsen oder Nullen. 08:41.010 --> 08:43.510 Und es ist wieder eine betonische Folge. 08:43.610 --> 08:45.590 Links und rechts sind wieder betonische Folgen. 08:46.870 --> 08:49.730 Das sehen wir hier genauso. 08:51.770 --> 08:54.930 Wenn hier nur Einsen stehen, ist die kleiner gleich der Folge. 08:55.330 --> 08:57.170 Hier die ist kleiner gleich der Folge. 08:57.930 --> 09:00.790 Und dann ist hier wiederum die kleiner als die Folge. 09:01.830 --> 09:05.090 Also die Eigenschaft, die man hier bekommt. 09:05.530 --> 09:09.890 Wobei dieses kleiner gleich der rechten Folge heißt, in dem Fall die 09:09.890 --> 09:13.650 einzelnen Positionen sind alle kleiner gleich den Positionen der 09:13.650 --> 09:14.390 anderen Folge. 09:16.910 --> 09:20.290 Und am Ende ist hier dann alles sortiert, weil das so regressiv weiter 09:20.290 --> 09:20.850 runter geht. 09:23.130 --> 09:28.150 So, das nach Null-Eins-Prinzip, dass wir jetzt nur eine Folge 09:28.150 --> 09:33.850 reingesteckt haben, diese zu Anfang Nullen, Einsen und dann Nullen. 09:34.170 --> 09:36.310 Wir hätten es andersherum genauso machen können, würden Sie auch 09:36.310 --> 09:37.810 sehen, dass das auch gerade so funktioniert. 09:38.590 --> 09:40.810 Das sieht man im Prinzip an diesem Teil. 09:41.490 --> 09:42.870 Da funktioniert es ja auch. 09:42.870 --> 09:45.570 Das ist also relativ einfach einzusehen. 09:45.670 --> 09:47.070 Man kann das noch formaler argumentieren. 09:47.910 --> 09:51.670 Aber dass dieses Vergleichernetz bitonische Folgen sortiert, kann man 09:51.670 --> 09:52.870 also darüber einsehen. 09:55.810 --> 09:57.390 Aber nicht ganz. 09:57.770 --> 09:58.690 Das wäre ein bisschen einfach. 09:58.930 --> 09:59.970 Ich beweise das doch mal lieber. 10:00.890 --> 10:05.830 Und der Beweis läuft so, dass wir genau betrachten, was passiert dort. 10:06.770 --> 10:10.150 Wir wollen eine bitonische Folge sortieren. 10:10.150 --> 10:13.650 Die bitonische Folge hat entweder diese Gestalt oder die Gestalt. 10:15.790 --> 10:17.090 Was passiert dann? 10:17.270 --> 10:20.410 Wir nehmen an, dass das A plus B plus C gleich 2N ist. 10:22.170 --> 10:25.190 Also zwei Teilfolgen der Länge N. 10:26.770 --> 10:31.910 Und wenn das so zwei Teilfolgen der Länge N sind, dann sehen wir, wenn 10:31.910 --> 10:34.450 wir jetzt die einfach untereinander malen, das ist jetzt untereinander 10:34.450 --> 10:38.810 gemalt, das entspricht genau dem, dass wir in diesem ersten Schritt ja 10:38.810 --> 10:44.170 gerade jetzt jeweils Element 1 mit N plus 1 und so weiter, Element 2 10:44.170 --> 10:48.010 mit N plus 2, Element 3 mit N plus 3 vergleichen. 10:49.390 --> 10:53.130 Diese horizontalen, langen Vergleiche sind hier jetzt senkrecht. 10:53.730 --> 10:56.670 Wir haben genau diejenigen Elemente, die verglichen werden müssen, 10:56.770 --> 10:57.530 übereinander geschrieben. 10:58.890 --> 11:02.150 Das war unsere Folge, die wir auf der vorigen Folie gesehen haben. 11:02.250 --> 11:03.310 Wir beginnen mit Nullen. 11:04.930 --> 11:07.910 Ich soll Einsen andeuten und danach kommen wieder Nullen. 11:08.010 --> 11:09.990 Das könnte eine solche Situation sein. 11:11.170 --> 11:14.530 Und hier überlappen sich da in einem Bereich die Einsen. 11:16.110 --> 11:19.150 So, wenn ich das jetzt, wenn ich die Vergleiche durchführe, wandern 11:19.150 --> 11:24.030 natürlich alle Einsen nach unten in diesen beiden Zeilen, die 11:24.030 --> 11:24.810 übereinander liegen. 11:25.410 --> 11:32.090 Das heißt, ich habe anschließend hier unten eine vollständig gefüllte 11:32.090 --> 11:35.730 Zeile, also die N-Elemente, die bereits alles Einsen sind. 11:36.390 --> 11:40.770 Und hier oben drüber liegen die restlichen Elemente. 11:40.810 --> 11:42.690 Das waren Nullen und einige Einsen noch. 11:43.070 --> 11:46.390 Und offensichtlich ist das wieder eine, oben eine betonische Folge, 11:46.970 --> 11:49.870 unten ist bereits alles sortiert, insbesondere auch eine betonische 11:49.870 --> 11:50.170 Folge. 11:50.830 --> 11:54.970 Und bei dem rechten Bild ist es so, dass wir hier mit Einsen anfangen, 11:55.050 --> 11:56.570 dann haben wir Nullen, dann kommen Einsen. 11:56.910 --> 12:00.390 Also völlig symmetrisch zu dem Bild, was wir hier links gerade 12:00.390 --> 12:01.270 betrachtet haben. 12:01.270 --> 12:06.850 Und entsprechend bleiben hier genauso die Einsen oben, die Nullen sind 12:06.850 --> 12:07.310 alle oben. 12:08.430 --> 12:13.390 Und wir haben die eine betonische Folge links, beziehungsweise oben, 12:13.510 --> 12:15.030 und die andere da direkt unten drunter. 12:15.930 --> 12:17.770 So, jetzt gibt es natürlich auch andere Situationen. 12:17.810 --> 12:19.250 Das muss sich ja nicht unbedingt überlappen. 12:20.150 --> 12:22.510 Hier habe ich so einen Überlappungsbereich angenommen. 12:23.050 --> 12:25.750 Es kann ja sein, dass das deutlich mehr Nullen als Einsen sind. 12:26.190 --> 12:31.090 Dann haben wir hier die Nullen, die Einsen, das überlappt sich nicht. 12:31.270 --> 12:34.730 Naja, was dann passiert ist, dass wir hier oben nur Nullen haben. 12:35.570 --> 12:38.410 Die Einsen wandern nach unten, unten bleibt eine betonische Folge 12:38.410 --> 12:38.950 übrig. 12:39.090 --> 12:40.250 Das sind beides die sortierte. 12:40.370 --> 12:43.310 Die nur Nullen ist eine betonische Folge, die unten auch. 12:43.450 --> 12:46.590 Und hier bei dem symmetrischen Bild natürlich der gleiche Effekt. 12:47.130 --> 12:52.010 Die Einsen wandern genau immer zu dem rechten Ende des Pfeils, 12:52.050 --> 12:53.250 beziehungsweise hier nach unten. 12:53.870 --> 12:55.550 Und wir haben die zwei betonischen Folgen. 12:55.550 --> 13:02.730 Es gibt eine weitere Möglichkeit, dass wir hier meinetwegen sehr viel 13:02.730 --> 13:03.990 mehr Nullen haben. 13:04.550 --> 13:09.850 Zunächst mal liegen alle Nullen in dem rechten Teil und die Einsen in 13:09.850 --> 13:10.590 dem linken Teil. 13:10.770 --> 13:13.970 Durch das Vergleichen wandern halt die Einsen alle nach rechts, 13:14.090 --> 13:15.230 beziehungsweise hier nach unten. 13:15.790 --> 13:18.410 Und wir haben oben die Nullen stehen und die Einsen alle dort unten. 13:18.850 --> 13:22.250 Ganz analog dazu haben wir hier diesen Fall betrachtet. 13:23.390 --> 13:27.270 Das sind im Wesentlichen die verschiedenen Situationen, die auftreten 13:27.270 --> 13:27.490 können. 13:27.570 --> 13:31.110 Und wir sehen, egal wie die Nullen und Einsen angeordnet sind, wir 13:31.110 --> 13:35.890 haben immer als Ergebnis zwei Teilfolgen, wobei die eine Teilfolge 13:35.890 --> 13:39.550 schon völlig sortiert ist bei solchen Nullen-Eins-Folgen und in der 13:39.550 --> 13:44.830 anderen sind die restlichen vollständigen Nullen oder Einsen, das 13:44.830 --> 13:49.070 heißt der Bereich ist bereits sortiert, beziehungsweise ist eine 13:49.070 --> 13:51.570 betonische Folge, die aber eben schon sortiert ist. 13:52.710 --> 13:56.310 Also so sieht man mit dem Null-Eins-Prinzip, dass diese Vergleiche, 13:56.330 --> 14:01.050 die man macht, tatsächlich dazu führen, dass wir aus einer betonischen 14:01.050 --> 14:05.730 Folge zwei betonische Folgen machen, wobei die eine kleiner als die 14:05.730 --> 14:10.870 andere ist und das ist genau das, was wir brauchen, um am Ende 14:10.870 --> 14:11.750 sortiert zu haben. 14:13.750 --> 14:14.290 Verständlich? 14:14.290 --> 14:14.830 Gut. 14:15.670 --> 14:18.990 Also haben wir zwei betonische Folgen und damit haben wir dann 14:18.990 --> 14:26.010 gezeigt, dass das Bitonic Sort funktioniert und jetzt wenden wir das 14:26.010 --> 14:27.950 an, um beliebige Folgen zu sortieren. 14:28.810 --> 14:33.530 Nun ist eine beliebige Folge natürlich keineswegs betonisch, aber wir 14:33.530 --> 14:37.630 haben ja eine Situation, wir betrachten einfach mal das Verschmelzen. 14:38.830 --> 14:40.530 Wir verschmelzen sortierte Folgen. 14:40.530 --> 14:46.290 Wir verschmelzen sortierte Folgen als Vorstufe dann zum Sortieren 14:46.290 --> 14:47.150 beliebiger Folgen. 14:48.010 --> 14:49.530 Wir machen ein betonisches Mischen. 14:51.590 --> 14:56.150 Jetzt haben wir hier bei dem Verschmelzen zwei sortierte Folgen, die 14:56.150 --> 14:58.670 sind jeweils hier angedeutet, so aufsteigend sortiert. 14:59.530 --> 15:01.310 Das ist natürlich keine betonische Folge. 15:01.510 --> 15:05.590 Betonisch wäre das, wenn das so aussehen würde, dass wir aufsteigen 15:05.590 --> 15:06.930 und wieder absteigen. 15:07.710 --> 15:08.670 Das haben wir hier nicht. 15:09.250 --> 15:13.730 Jetzt nehmen wir aber genau unser Muster von dem betonischen Sortieren 15:14.450 --> 15:18.950 und verwenden das für das betonische Verschmelzen, indem wir einfach 15:18.950 --> 15:22.250 ein logisches Spiegel in der rechten Folge machen. 15:23.570 --> 15:27.610 Also logisch sieht das so aus, dass wir hier jetzt das einmal gedreht 15:27.610 --> 15:27.970 haben. 15:28.970 --> 15:32.070 Das heißt, wir hätten praktisch jetzt so eine Folge hier betrachtet. 15:32.210 --> 15:33.310 Das ist die betonische Folge. 15:33.850 --> 15:36.530 Dann wären die Vergleiche hier alle lang gewesen. 15:36.930 --> 15:40.170 Das haben wir aber hier einfach, haben wir die Vergleiche verändert in 15:40.170 --> 15:43.050 der Distanz jeweils. 15:43.970 --> 15:49.290 Und dieses Spiegeln der rechten Folge äußert sich dann eben so, dass 15:49.290 --> 15:52.570 andere Elemente miteinander verglichen werden, nämlich das erste mit 15:52.570 --> 16:00.270 dem Endenelement, das zweite mit dem N-ersten und so weiter. 16:01.950 --> 16:03.390 Das ist der erste Schritt. 16:04.490 --> 16:09.630 Das entspricht vollständig dem ersten Schritt bei dem betonischen 16:09.630 --> 16:10.190 Sortieren. 16:10.410 --> 16:13.530 Und danach hatten wir links- und rechtsbetonische Folgen, wobei die 16:13.530 --> 16:15.090 linke Folge kleiner ist als die rechte. 16:15.590 --> 16:20.230 Danach folgt genau das betonische Sortieren, wie wir das gerade auf 16:20.230 --> 16:22.510 der vorigen Folie gesehen haben. 16:23.310 --> 16:26.250 Das heißt, nur die erste Stufe muss verändert werden, weil wir da das 16:26.250 --> 16:30.990 logische Spiegeln simulieren. 16:31.690 --> 16:33.490 Alles andere kann so bleiben wie vorher. 16:34.530 --> 16:41.250 Und damit haben wir jetzt ein Merge-Verfahren, das offensichtlich Log 16:41.250 --> 16:42.390 -End -Schritte braucht. 16:43.230 --> 16:45.290 Das sind gerade hier Log-End-Stufen. 16:49.350 --> 16:52.410 Ich habe hier nochmal die Nullen und Einsen durchgeschoben, das ist 16:52.410 --> 16:53.590 die gleiche Folge wie vorher. 16:54.290 --> 16:58.450 Da ändert sich also nichts, es ist ja hier nur einmal gespiegelt. 17:02.310 --> 17:04.530 Hier sind es jetzt nicht genau die gleiche Folge wie vorher. 17:04.590 --> 17:07.970 Wir haben jetzt hier zwei sortierte Folgen, also Nullen, Einsen, dann 17:07.970 --> 17:10.730 nochmal Nullen und Einsen und einmal logisch gespiegelt. 17:10.730 --> 17:15.790 Das ergibt dann bei den Vergleichen gerade eben diese beiden Folgen 17:15.790 --> 17:18.570 hier links und rechts, betonische Folgen usw. 17:19.490 --> 17:23.530 Und damit entsteht dann durch rekursive Anwendung dieses Merge 17:23.530 --> 17:27.970 -Verfahrens betonisches Merge, also Bitonic Merge Sort. 17:29.050 --> 17:33.410 Wobei jede Merge-Stufe gerade durch dieses betonische Verschmelzen 17:33.410 --> 17:34.090 gemacht wird. 17:34.090 --> 17:39.330 Und jede Merge-Stufe braucht Zeitlog-End und damit haben wir, wie wir 17:39.330 --> 17:43.650 uns vorher schon überlegt hatten, wenn das parallele Merge Zeitlog-End 17:43.650 --> 17:49.650 braucht, dann haben wir insgesamt ein Verfahren, das in Zeitlog 17:49.650 --> 17:56.390 -Quadrat -End läuft, weil wir ja die einzelnen Merge-Stufen parallel 17:56.390 --> 17:56.970 machen konnten. 17:56.970 --> 18:05.730 Das war aus diesem übergeordneten Merge-Sort-Verfahren ja so 18:05.730 --> 18:06.350 abgeleitet. 18:06.810 --> 18:10.710 Also genau wie bei dem Odd-Even Merge Sort haben wir jetzt auch bei 18:10.710 --> 18:13.770 dem Bitonic Merge Sort Laufzeit von Log-Quadrat-End. 18:14.590 --> 18:15.630 Das ist schon nicht schlecht. 18:16.530 --> 18:20.190 Wir haben natürlich einen Parallelitätsgrad von N, also genau wie beim 18:20.190 --> 18:24.990 Odd -Even Merge Sort ist der Zeitgewinn nicht ganz bestmöglich. 18:24.990 --> 18:27.210 Aber immerhin sind wir auf Log-Quadrat-End runter. 18:29.670 --> 18:31.870 Okay, zwei parallele Verfahren. 18:31.970 --> 18:33.310 Sie sehen, was man alles so machen kann. 18:34.570 --> 18:36.490 Übrigens kann man das noch weiter treiben. 18:36.950 --> 18:42.050 Man kann das sogar reduzieren, kann runterkommen bis auf Sortieren in 18:42.050 --> 18:44.570 Zeit O von Log-End. 18:44.570 --> 18:57.470 Und der Parallelitätsgrad dabei ist P aus O von N. 18:57.830 --> 19:03.670 Wir können sogar mit einem linearen Aufwand, mit maximal linear vielen 19:03.670 --> 19:08.150 Vergleichen, die parallel ausgeführt werden müssen, in Zeit Log-End 19:08.150 --> 19:08.810 sortieren. 19:08.810 --> 19:13.050 Das war lange Zeit offen, ist vor einigen Jahren dann mal gezeigt 19:13.050 --> 19:13.450 worden. 19:13.570 --> 19:15.510 Es gibt inzwischen mehrere solcher Ansätze. 19:16.050 --> 19:19.090 Das heißt, man kann tatsächlich einen optimalen Zeitgewinn kriegen, 19:19.230 --> 19:22.790 kann auf Log-End runterkommen mit N Prozessoren. 19:23.810 --> 19:29.250 Das ist ein Verfahren, das hier interessant ist. 19:29.410 --> 19:32.710 Das ist das Verfahren Cold Sort, das ich Ihnen hier nicht vorstelle. 19:33.550 --> 19:35.970 Können Sie in der Literatur nachlesen. 19:36.070 --> 19:37.070 Interessantes Verfahren. 19:37.550 --> 19:41.490 Es gibt noch weitere Verfahren, die ich Ihnen aber hier nicht 19:41.490 --> 19:41.910 vorstelle. 19:42.050 --> 19:42.930 Das würde hier zu weit führen. 19:43.910 --> 19:46.610 Man kann sogar noch weiter runterkommen. 19:47.070 --> 19:49.690 Wäre also wesentlich komplizierter, Ihnen das zu zeigen, als das, was 19:49.690 --> 19:50.910 ich bisher gemacht habe. 19:51.750 --> 19:56.310 Ich möchte gerne auf jetzt eine andere Variante kommen. 19:56.650 --> 19:59.130 Wir hatten das bei den Matrix-Multiplikationen ja auch gemacht. 19:59.130 --> 20:05.770 Eigentlich müssen wir sehen, dass wir mit zweidimensionalen Feldern 20:05.770 --> 20:06.250 arbeiten. 20:06.330 --> 20:06.650 Warum? 20:07.110 --> 20:11.110 Also zweidimensionale Felder, die nur kurze Verbindungen haben 20:11.110 --> 20:11.430 jeweils. 20:13.730 --> 20:17.630 Weil lange Verbindungen, wie wir sie zum Beispiel bei dem Odd-Even 20:17.630 --> 20:21.170 -Merge Sort oder auch bei dem Bitonic-Merge Sort brauchen. 20:21.310 --> 20:23.990 Da haben wir die langen Vergleiche von sehr weit auseinander 20:23.990 --> 20:25.110 befindlichen Elementen. 20:25.110 --> 20:29.570 So etwas ist für eine Hardware-Realisierung nicht so günstig. 20:30.450 --> 20:33.590 Und deswegen schauen wir uns einfach an, was passiert, wenn wir unsere 20:33.590 --> 20:36.590 Prozessoren in einem zweidimensionalen Gitter angeordnet haben. 20:37.290 --> 20:41.490 Und das ist auch eine parallele Rechnerstruktur, die man häufig so 20:41.490 --> 20:45.150 vorfindet, eben wegen dieser schönen direkten Nachbarschaften mit sehr 20:45.150 --> 20:45.950 kurzen Verbindungen. 20:46.050 --> 20:47.230 Das heißt, man kann sehr schnell kommunizieren. 20:48.190 --> 20:54.750 Wir nehmen jetzt an, dass die einzelnen Prozessoren jeweils ein Datum 20:54.750 --> 20:55.310 enthalten. 20:55.590 --> 20:58.490 Sie könnten genauso gut sagen, eine Datei pro Prozessor. 20:58.910 --> 21:02.410 Und wir wollen eine Menge von Dateien, die so verteilt sind über ein 21:02.410 --> 21:03.990 ganzes Feld, insgesamt sortieren. 21:04.850 --> 21:08.370 Ob wir jetzt sagen, eine Datei oder ein Datum ist völlig egal. 21:08.370 --> 21:11.690 Sie können einen Vergleich von zwei Elementen natürlich auch machen 21:11.690 --> 21:18.870 als ein Sortieren, Verschmelzen und Aufspalten von zwei Dateien. 21:19.890 --> 21:24.070 Das ist eine etwas gröbere Operation, aber es ist einfacher, wenn wir 21:24.070 --> 21:27.690 sagen, wir haben hier nur ein Datum pro Prozessor. 21:28.730 --> 21:32.570 Und wir sagen, wir haben hier das Groß-N, das ist ein Klein-N-Quadrat, 21:32.690 --> 21:38.970 das heißt, wir haben hier gerade N Zeilen und insgesamt N Spalten. 21:40.650 --> 21:44.770 Jetzt wollen wir also diese Klein-N-Quadrat-Daten sortieren. 21:45.210 --> 21:46.890 Und die Frage ist, wie macht man das eigentlich? 21:47.110 --> 21:48.930 Was ist eigentlich die Sortierreihenfolge? 21:50.250 --> 21:53.290 Eine typische Reihenfolge, genau, Sie müssen jetzt malen, ich habe mir 21:53.290 --> 21:57.270 die Abbildung, die war früher drin in den Foliensatz, irgendwann ist 21:57.270 --> 21:59.910 die verschwunden und ich habe sie gestern Abend, ich schrieb mir das 21:59.910 --> 22:02.370 auf und habe sie gesucht und tatsächlich gefunden und wieder hier 22:02.370 --> 22:02.910 reinkopiert. 22:05.350 --> 22:07.550 Ich habe es sonst auch gemalt einfach. 22:08.090 --> 22:12.370 Also, ich kann zeilenweise sortieren, das heißt, jede Zeile soll 22:12.370 --> 22:16.310 aufsteigend sortiert sein, wäre eine naheliegende Geschichte. 22:16.310 --> 22:20.990 Ich könnte aber auch sagen, weil mich das stört, dass das Element, das 22:20.990 --> 22:25.710 hier ganz rechts ist, das wäre das Element Klein-N, und das Element N 22:25.710 --> 22:29.170 plus 1 in dieser Folge, die liegen ja weit auseinander. 22:30.110 --> 22:31.930 Das möchte ich eigentlich nicht. 22:32.270 --> 22:35.190 Dann sage ich einfach, hier ist das Element und da ist das Element N 22:35.190 --> 22:39.630 plus 1 und ich sortiere in Schlangenlinien. 22:39.790 --> 22:43.830 Also hier war es im Prinzip abwechselnd nach rechts und nach links. 22:46.410 --> 22:50.510 Dann habe ich eine schöne Eigenschaft, dass die Elemente in 22:50.510 --> 22:55.250 benachbarten Prozessoren gerade so schön sequenziell aufgereiht sind. 22:55.490 --> 23:00.310 Also richtig sortiert, rangrichtig, so direkt nebeneinander liegen. 23:00.730 --> 23:05.110 Während wir hier eben eine große Entfernung hätten zwischen dem 23:05.110 --> 23:08.850 rechtesten Element und dem linkesten Element der nächsten Zeile, das 23:08.850 --> 23:12.650 aber in der Sortierreihenfolge das nächste Element wäre. 23:13.390 --> 23:15.890 Also, sortieren in Schlangenlinien kann interessant sein. 23:16.050 --> 23:17.610 Man kann auch noch anders sortieren. 23:17.730 --> 23:20.890 Sie können auch zum Beispiel sagen, ich sortiere meinetwegen in dieser 23:20.890 --> 23:21.590 Reihenfolge. 23:22.390 --> 23:25.990 Oder Sie nehmen sich irgendeine Hilbert-Kurve, die ein 23:25.990 --> 23:28.630 zweidimensionales Feld ausführt und sagen, das ist meine 23:28.630 --> 23:28.920 Sortierreihenfolge. 23:32.090 --> 23:37.550 Nur, dass Ihnen klar ist, wie ich sortiere, hängt davon ab, welche 23:37.550 --> 23:41.810 Anforderungen ich habe bezüglich der logischen Reihenfolge der 23:41.810 --> 23:42.630 einzelnen Elemente. 23:42.650 --> 23:44.450 in diesem zweidimensionalen Feld. 23:44.550 --> 23:45.950 Und das ist eine räumliche Anordnung. 23:46.610 --> 23:49.830 Bei einer sequentiellen Anordnung, linearen Anordnung, hatten wir 23:49.830 --> 23:50.550 damit kein Problem. 23:50.890 --> 23:52.630 Da war es einfach zu sagen, was sortiert ist. 23:53.130 --> 23:55.690 Hier haben wir keine lineare Anordnung, sondern die müssen wir uns 23:55.690 --> 23:56.210 erst schaffen. 23:56.670 --> 24:02.050 Durch irgendeine Hilbert-Kurve oder irgendeine Anordnung, kann 24:02.050 --> 24:03.670 irgendeine Permutation der Elemente sein. 24:04.230 --> 24:06.850 Das sind naheliegende Dinge, die man hier machen könnte. 24:07.850 --> 24:11.090 Okay, wir sagen, dass MEMD erlaubt sei. 24:11.210 --> 24:15.090 MEMD war Multiple Instruction Multiple Data. 24:15.230 --> 24:19.030 Das heißt, was wir erlauben ist, dass wir unterschiedlich zum gleichen 24:19.030 --> 24:24.990 Zeit in parallel arbeitenden Prozessoren unterschiedliche Befehle 24:24.990 --> 24:25.850 ausführen können. 24:26.590 --> 24:31.450 Wir könnten also zum Beispiel hier gleichzeitig diese beiden 24:31.450 --> 24:33.290 Prozessoren etwas vergleichen lassen. 24:33.530 --> 24:36.870 In der Richtung und diese beiden vergleichen etwas in der Richtung. 24:36.990 --> 24:40.570 Das wären verschiedene Befehle, die gleichzeitig ausgeführt werden. 24:40.970 --> 24:42.710 Und die vielleicht gleichzeitig in der Richtung. 24:44.510 --> 24:48.490 Das wären in dem Fall drei verschiedene Operationen, die wir machen 24:48.490 --> 24:48.890 würden. 24:49.530 --> 24:53.070 Wobei, hier sehen Sie Pfeile, hier sind zwei nebeneinander liegende 24:53.070 --> 24:54.370 Prozessoren mit einem Pfeil verbunden. 24:54.370 --> 24:55.570 Wie gesagt, das ist eine Operation. 24:56.510 --> 24:58.450 Operationen finden aber in Prozessoren statt. 24:58.610 --> 25:03.010 Das heißt, der Prozessor 1 müsste vom Prozessor 2 ein Element lesen 25:03.010 --> 25:06.890 und müsste das Maximum der beiden Elemente nach rechts schreiben. 25:07.890 --> 25:09.370 Das wären also eigentlich mehrere Operationen. 25:10.970 --> 25:14.750 Es können aber mehrere gleichzeitig durchgeführt werden, die 25:14.750 --> 25:15.950 unterschiedlich sind. 25:16.170 --> 25:21.190 Sie wissen, bei SIMD darf ich überall nur das gleiche Operationen 25:21.190 --> 25:21.750 ausführen. 25:22.470 --> 25:25.890 Das heißt, entweder machen die gar nichts oder führen alle die gleiche 25:25.890 --> 25:26.850 Operation aus. 25:29.370 --> 25:32.110 Wie lange dauert das Sortieren in einem zweidimensionalen Feld? 25:32.290 --> 25:32.950 Was ist die Erwartung? 25:34.170 --> 25:37.390 Die einfache untere Schranke ist 2n-2. 25:37.550 --> 25:39.010 Warum 2n-2? 25:39.630 --> 25:43.110 Es kann sein, dass das Element, das zu Anfang hier links oben liegt, 25:43.270 --> 25:45.710 anschließend dort rechts unten landen muss. 25:46.270 --> 25:49.550 Also hier das Element und das Element, das wäre gerade das Minimum und 25:49.550 --> 25:50.230 das Maximum. 25:50.230 --> 25:57.210 Die liegen also gerade in der Manhattan-Distanz, in der Entfernung 2n 25:57.210 --> 25:57.490 -2. 25:58.090 --> 26:01.030 Oder, wenn wir das N nehmen, 2 mal Wurzeln-2. 26:03.690 --> 26:06.770 Manhattan-Distanz heißt, wir müssen die Differenz der Koordinaten 26:06.770 --> 26:07.110 nehmen. 26:07.490 --> 26:10.890 Das heißt, wir müssten hier einmal durchlaufen, einmal darüber laufen, 26:10.990 --> 26:11.930 einmal darüber laufen. 26:12.370 --> 26:16.650 Das sind genau 2n-2 Schritte, um dort rüber zu wandern. 26:16.650 --> 26:20.250 Ohne jeden Vergleich, einfach nur das Datum zu transportieren, wären 26:20.250 --> 26:22.830 schon 2n-2 lokale Vertauschungen. 26:23.390 --> 26:25.410 Schneller kann kein Verfahren laufen. 26:26.410 --> 26:27.930 Kann nicht funktionieren. 26:28.570 --> 26:31.790 Das heißt, das ist eine klare untere Schranke, in diesem Fall sehr 26:31.790 --> 26:36.230 einfach, allein durch die Struktur gegeben, für das Sortieren in 26:36.230 --> 26:37.490 zweidimensionalen Feldern. 26:38.750 --> 26:41.530 Und ich stelle Ihnen natürlich gerne ein Verfahren vor, bei dem ich 26:41.530 --> 26:42.470 selbst beteiligt war. 26:42.930 --> 26:49.050 Der sogenannte LS-Hoch-3-Verfahren, das war in einer Arbeitsgruppe, 26:49.090 --> 26:51.450 die wir 1983 in Kiel hatten. 26:54.530 --> 26:58.230 Und das ist nicht das einzige Verfahren zum Sortieren auf 26:58.230 --> 27:00.430 zweidimensionalen Gittern, aber natürlich ein sehr schönes. 27:01.110 --> 27:02.010 Ich war ja auch beteiligt. 27:02.630 --> 27:05.030 Aber es ist wirklich ein schönes Verfahren. 27:05.130 --> 27:08.430 Sie werden sehen, es ist ein ganz einfaches, elegantes Verfahren. 27:08.430 --> 27:14.650 Es gibt andere, die sind sogar schneller, leicht etwas schneller, aber 27:14.650 --> 27:16.270 sind deutlich komplizierter. 27:16.970 --> 27:20.270 Und ich werde die aber auch am Rande dann auch noch mit erwähnen. 27:21.050 --> 27:23.850 Die Idee ist, dass wir eigentlich wieder ein Merge Sort machen. 27:25.110 --> 27:29.170 Aber hier machen wir ein Merge Sort auf einem zweidimensionalen Feld. 27:29.170 --> 27:36.910 Und wir machen ein Verschmelzen nicht von zwei vorsortierten Folgen, 27:37.070 --> 27:39.730 sondern von vier vorsortierten Feldern. 27:39.830 --> 27:44.250 Sie sehen hier, hier haben wir unser zweidimensionales Feld und wir 27:44.250 --> 27:48.170 haben hier vier Quadranten, die jeweils in Schlangenlinien vorsortiert 27:48.170 --> 27:48.430 sind. 27:48.850 --> 27:50.890 Wir wollen also jetzt in Schlangenlinien sortieren. 27:54.590 --> 27:57.650 Der wesentliche Schritt ist also, dass wir sagen, wir wollen diese 27:57.650 --> 28:03.430 vier Felder verschmelzen zu einer in Schlangenlinien sortierten Folge 28:03.430 --> 28:04.510 auf dem gesamten Feld. 28:05.150 --> 28:06.990 Jetzt ist die Frage, wie macht man das sinnvollerweise? 28:08.030 --> 28:10.770 Zur Vereinfachung nehmen wir an, dass das Ende zweier Potenz ist. 28:10.770 --> 28:12.770 Dann kann man immer schön alles so aufteilen. 28:15.150 --> 28:21.430 Und das ist also unsere Aufgabe, so ein Verschmelzungsverfahren zu 28:21.430 --> 28:21.690 machen. 28:22.570 --> 28:25.150 Und das läuft jetzt folgendermaßen. 28:25.230 --> 28:28.870 Wir machen ein Perfect Shuffle in jeder Zeile des Feldes. 28:30.550 --> 28:38.670 Nehmen wir mal an, wir haben hier Elemente A, B, C, D. 28:39.770 --> 28:42.070 Oder ich mache es mal zur Vereinfachung. 28:42.750 --> 28:45.970 Ich schreibe jetzt hier A, B, C, D hin. 28:46.190 --> 28:47.370 Ist völlig egal, wie ich es schreibe. 28:49.510 --> 28:50.450 Was ist ein Perfect Shuffle? 28:50.470 --> 28:53.250 Das habe ich Ihnen schon mal vorgestellt beim Odd-Even Merge Sort. 28:54.790 --> 28:56.450 Ich mache also folgende Operationen. 28:56.490 --> 29:02.730 Stellen Sie sich vor, Sie haben hier A1, A2, A3, A4. 29:04.490 --> 29:09.940 Und da entsprechend B1, B2, B3, B4. 29:10.690 --> 29:11.870 Was passiert dann? 29:12.150 --> 29:14.110 Das sind also die Elemente der ersten Zeile. 29:15.290 --> 29:18.490 Wenn ich ein Perfect Shuffle mache, dann würde ich hier anschließend 29:18.490 --> 29:18.930 stehen. 29:20.450 --> 29:27.190 A1, B1, A2, B2 und hier hinten A4, B4. 29:27.190 --> 29:38.390 Hier unten würde entsprechend stehen das C1, C2, C3, C4 bzw. 29:38.730 --> 29:42.450 D1, D2, D3, D4. 29:43.090 --> 29:50.050 Und hier würde entsprechend dann in dieser Zeile stehen C1, D1, C2, 29:50.590 --> 29:53.730 D2, C4, D4. 29:53.810 --> 29:54.830 Warum male ich das auf? 29:54.830 --> 30:03.430 Sie sehen, dass in so einer Doppelspalte, kann man natürlich auch 30:03.430 --> 30:09.830 direkt sehen, Elemente aus allen vier Feldern zusammenkommen. 30:12.450 --> 30:17.950 Gerade in den ersten beiden Spalten, die linkesten Spalten der vier 30:17.950 --> 30:22.290 Felder sind hier zusammengeführt in eine Doppelspalte. 30:23.590 --> 30:31.750 Und jetzt sortiere ich diese Doppelspalte jeweils mit OETS, da fehlt 30:31.750 --> 30:35.170 ein Pfeil nach vorne, das ist also das maximale Element, in 30:35.170 --> 30:39.890 Schlangenlinien, in eine Doppelspalte, gehen so abwechselnd darunter. 30:40.410 --> 30:43.270 Das heißt, ich habe jetzt Elemente aus allen vier Feldern, in jeweils 30:43.270 --> 30:49.030 diesen Doppelspalten, ich sortiere mit OETS, OETS, hier habe ich ja 30:49.030 --> 30:51.510 gerade immer benachbarte Elemente, kann ich machen. 30:52.630 --> 30:57.790 Und anschließend wende ich auf der gesamten Matrix in Schlangenlinien 30:57.790 --> 31:01.930 OETS an, aber nicht vollständig, sondern nur zwei Endschritte. 31:03.930 --> 31:09.370 Und ich behaupte, anschließend ist das ganze Feld vollständig in 31:09.370 --> 31:10.270 Schlangenlinien sortiert. 31:13.330 --> 31:17.110 Sie sehen, das ist ein einfaches Verfahren, klar strukturiert, wir 31:17.110 --> 31:21.950 machen einen Perfect Shuffle, sortieren die Doppelspalten, führen 31:21.950 --> 31:24.370 nochmal OETS auf dem gesamten Feld aus. 31:25.510 --> 31:28.750 Da muss man natürlich überlegen, erstmal wie viel Zeit das braucht und 31:28.750 --> 31:32.850 dann auch, ob es korrekt ist, und das werden wir dann gleich sehen. 31:33.050 --> 31:36.270 Aber das ist also im Wesentlichen das Verfahren, Doppelspalten 31:36.270 --> 31:39.070 erzeugen, indem man so einen Perfect Shuffle macht, in den 31:39.070 --> 31:43.430 Doppelspalten sind Elemente aus den vier vorsortierten Feldern drin, 31:44.470 --> 31:49.230 diese Doppelspalten sortieren und dann nochmal eine gewisse Anzahl von 31:49.230 --> 31:52.410 Schritten von OETS auf der gesamten Schlangenlinie ausführen. 31:53.770 --> 31:58.370 Wenn wir das analysieren, wie viel Zeit braucht das? 31:58.370 --> 32:14.810 Ein Perfect Shuffle, ich sagte, wir hatten hier A1, A2, A3, A4 und B1, 32:15.130 --> 32:19.450 B2, B3, B4. 32:19.450 --> 32:21.050 Was passiert dann? 32:21.590 --> 32:28.650 Das B1 wandert hier runter, das A4 wandert dorthin und entsprechend 32:28.650 --> 32:31.130 wandert B1 dann dahin und dann dahin. 32:31.670 --> 32:34.250 Wir haben also hier das B1 und das A1 dort. 32:34.410 --> 32:40.530 Und entsprechend haben wir hier hinten nachher das A4 und das B4 dort 32:40.530 --> 32:40.790 stehen. 32:41.390 --> 32:46.130 Und entsprechend hier daneben, Sie sehen, das wandert hier so schön 32:46.130 --> 32:56.050 rüber, das B2 wandert hier hin, das B3 wandert dorthin und dazwischen 32:56.050 --> 33:02.970 steht dann gerade A2 und hier das A3 und das war es schon. 33:04.530 --> 33:09.950 Das sind im Prinzip die Vertauschungen, die man machen muss, um 33:09.950 --> 33:11.330 Perfect Shuffle auszuführen. 33:11.330 --> 33:18.050 Das heißt, wir haben hier genau diese Linie, wir haben die Linie, wir 33:18.050 --> 33:39.530 haben außerdem das B1, wir haben das A2, das wandert dahin, das A3 33:39.530 --> 33:48.130 wanderte dahin und wir haben hier das B2, das wanderte dahin, B3 33:48.130 --> 33:49.970 wanderte dahin. 33:50.390 --> 33:53.750 Und Sie sehen, an den Schnittpunkten dieser Linien liegen gerade die 33:53.750 --> 33:54.450 Vertauschungen. 33:55.630 --> 33:59.250 Das sind genau die Linien, die ich Ihnen vorher aufgemalt habe bei dem 33:59.250 --> 34:02.950 Perfect Shuffle, bei dem Odd Even Merge Sort, das waren genau diese 34:02.950 --> 34:03.350 Linien. 34:03.350 --> 34:07.110 Hier natürlich die beiden auch noch, die seien ja nicht verändert. 34:07.990 --> 34:10.310 Und Sie brauchen also an jedem Schnittpunkt dieser Linien eine 34:10.310 --> 34:10.650 Vertauschung. 34:11.850 --> 34:18.350 Und man sieht sofort, das sind nacheinander Inhalte minus eins 34:18.350 --> 34:24.810 Vertauschungen, um dieses Perfect Shuffle auszuführen durch rein 34:24.810 --> 34:25.590 lokale Operationen. 34:26.320 --> 34:30.690 Das sind jeweils rein lokale Operationen, nacheinander so ausgeführt. 34:31.170 --> 34:35.430 Also Inhalte minus eins Takte für die Vertauschungen, für das Perfect 34:35.430 --> 34:35.750 Shuffle. 34:36.490 --> 34:42.010 Und dann kommt OITS auf folgende Länge 2n, das sind 2n Schritte, 2n 34:42.010 --> 34:48.550 Takte, man kann sogar in dem Fall 2n minus eins machen, aber 2n sind 34:48.550 --> 34:49.470 ein bisschen großzügig. 34:49.470 --> 34:53.550 Und dann im dritten Schritt, das war dieses Odd Even Transposition 34:53.550 --> 34:58.850 Sort auf der gesamten Schlangenlinie, das war dieser Schritt hier, der 34:58.850 --> 35:00.730 dann zu der sortierten Folge führen sollte. 35:01.370 --> 35:05.550 Da fehlen überall die Pfeilspitzen, aber Sie wissen, was gemeint ist. 35:06.230 --> 35:10.170 Nochmal 2n Takte, wenn wir zusammenzählen, haben wir 4,5n minus eins 35:10.170 --> 35:18.990 Takte, um ein Feld mit kleinen n² Elementen zu verschmelzen, ausgehend 35:18.990 --> 35:21.450 von vier vorsortierten Teilfeldern. 35:23.070 --> 35:29.130 Also das ist der Aufwand, 4,5n minus eins, um vier solche 35:29.130 --> 35:31.630 vorsortierten Teilfelder zu verschmelzen. 35:31.630 --> 35:35.270 Und damit haben wir uns also die Zeit analysiert. 35:35.890 --> 35:40.590 Die Frage ist, warum reicht das gerade so aus, warum reichen hier 35:40.590 --> 35:47.150 diese 2n Takte aus auf der gesamten Folge, um insgesamt das zu 35:47.150 --> 35:47.650 sortieren. 35:48.550 --> 35:54.870 Und das schauen wir uns jetzt an, indem wir uns das Feld genauer 35:54.870 --> 35:58.170 betrachten, natürlich mit Nutzung des Null-Eins-Prinzips. 35:59.530 --> 36:03.350 Wir haben unsere vier vorsortierten Felder alle in Schlangenlinien 36:03.350 --> 36:09.470 sortiert, das heißt, wenn wir Null-Eins-Folgen haben, sind das alles 36:09.470 --> 36:13.650 Folgen 0 hoch A, 1 hoch B oder irgendwas. 36:13.650 --> 36:17.790 Also hier haben wir erst Nullen, dann Einsen, und die Einsen werden 36:17.790 --> 36:26.470 einige Halbzeilen, in diesem Fall also, diese Bereiche, vollständig 36:26.470 --> 36:27.610 mit Einsen gefüllt sein. 36:27.790 --> 36:31.290 Dann gibt es vielleicht eine Zeile, die nicht vollständig gefüllt ist 36:31.290 --> 36:33.610 mit Einsen, und oben drüber sind nur Nullen. 36:33.610 --> 36:37.870 Und das sieht in allen Quadranten genauso aus. 36:38.790 --> 36:44.510 Nullen, Einsen, es kann sein, dass eine Zeile nicht vollständig mit 36:44.510 --> 36:48.310 Nullen oder Einsen gefüllt ist, sondern nur teilweise, und dann kommen 36:48.310 --> 36:49.550 vollständige Einszeilen. 36:50.290 --> 36:54.330 Jetzt sagen wir, wir haben hier insgesamt klein A, klein B, klein C, 36:54.470 --> 36:58.450 klein D, halbe Einszeilen, die also vollständig sind jeweils. 36:59.470 --> 37:03.510 Und dann kommen noch so diese Extrazeilen dazu, die eventuell da sind, 37:03.630 --> 37:07.050 und da das Ganze ja in Schlangenlinien sortiert wird, kann es sein, 37:07.170 --> 37:10.590 dass die mit Nullen beginnen und dann Einsen haben, oder mit Einsen 37:10.590 --> 37:11.790 beginnen und dann Nullen haben. 37:11.870 --> 37:16.010 Je nachdem, ob ich in dem Fall würde ich gerade in dieser Richtung 37:16.010 --> 37:18.610 sortieren, in dem Fall würde ich gerade in der Richtung sortieren. 37:20.270 --> 37:27.850 So, in dem Fall hätten wir also dreimal von rechts nach links 37:27.850 --> 37:32.710 sortiert, aufsteigen, und einmal von links nach rechts aufsteigen 37:32.710 --> 37:34.700 sortiert, in den Quadranten. 37:36.760 --> 37:39.520 So, jetzt werden die Operationen ausgeführt. 37:39.640 --> 37:45.240 Nach Schritt 2 sieht das so aus, oder wir kommen gleich auf einen 37:45.240 --> 37:45.760 anderen Punkt. 37:45.880 --> 37:49.540 Betrachten wir zunächst mal den Fall, dass dieses E gerade ist. 37:49.560 --> 37:51.500 Was heißt das, wenn E gerade ist? 37:53.220 --> 37:56.400 Die Summe von A, B, C und D ist gerade. 37:59.040 --> 38:04.800 Das heißt, ich kann diese vollen, ich habe ja jetzt genau A plus B 38:04.800 --> 38:09.560 plus C plus D Elemente in meiner Doppelspalte, das war ja gerade hier 38:09.560 --> 38:16.920 immer eine Spalte aus jedem Quadranten, das sind genau A plus B plus C 38:16.920 --> 38:17.440 plus D. 38:17.440 --> 38:22.100 Wenn das eine gerade Zahl ist, dann heißt das, die teilen sich so 38:22.100 --> 38:27.100 schön gleichmäßig auf, auf einen gewissen Bereich, nämlich gerade E 38:27.100 --> 38:28.460 halbe volle Zahl. 38:30.220 --> 38:33.640 Jetzt kann es aber sein, dass oben drüber noch irgendwelche 38:33.640 --> 38:35.480 angefangenen Einszeilen waren. 38:36.720 --> 38:41.680 Das sind aber maximal vier weitere Elemente, da kommt keins, da kommt 38:41.680 --> 38:44.840 eins, da kommt eins, da kommt eins, wenn wir die linkeste Doppelspalte 38:44.840 --> 38:45.440 betrachten. 38:45.440 --> 38:47.620 Dann hätten wir drei, die dazukommen. 38:48.820 --> 38:51.900 Und wir hätten hier vielleicht auch irgendwo einen Bereich, wo wir mal 38:51.900 --> 38:53.460 vier dazunehmen müssen. 38:54.160 --> 38:56.780 Aber mehr als vier können das nicht sein, die dazukommen. 38:57.220 --> 39:02.120 Das heißt, diese beiden Zeilen hier sind genau der Platz, den man 39:02.120 --> 39:06.140 braucht, um zusätzliche Einsen noch aufzunehmen. 39:07.560 --> 39:09.840 Und diese Zeilen reichen aber auch aus. 39:09.840 --> 39:11.840 Nur dort kann etwas unsortiert sein. 39:11.980 --> 39:14.600 Oben drüber sind garantiert nur Nullen. 39:16.080 --> 39:18.920 Dann kommt dieser Bereich, der noch nicht sortiert ist, das sind aber 39:18.920 --> 39:20.160 maximal zwei Zeilen. 39:20.780 --> 39:23.760 Und dann kommt der Bereich unten drunter, wo nur Einsen liegen. 39:26.540 --> 39:31.520 Und das heißt, wenn ich jetzt 2n Schritte von OETS ausführe, dann ist 39:31.520 --> 39:32.320 das Ganze sortiert. 39:32.500 --> 39:35.680 Weil ich ja nur diese beiden Zeilen noch sortieren muss. 39:37.280 --> 39:40.200 Und damit weiß ich, das reicht aus. 39:40.540 --> 39:45.340 Danach habe ich eine in Schlangenlinien sortierte Folge vorliegen. 39:45.780 --> 39:47.880 Offensichtlich ist für den Fall das kein Problem. 39:48.820 --> 39:52.800 Jetzt betrachten wir das für den Fall, dass das E ungerade ist. 39:52.940 --> 39:54.680 Und da haben wir eine gewisse schwierige Situation. 39:55.960 --> 40:02.080 Wenn das E ungerade ist, dann heißt das doch, wir haben nicht so eine 40:02.080 --> 40:07.320 schöne Aufteilung wie hier, dass sich das gerade so schön gleichmäßig 40:07.320 --> 40:07.980 aufteilt. 40:08.060 --> 40:12.100 Dieses a plus b plus c plus d in zwei gleich große Hälften. 40:12.380 --> 40:14.510 Sondern wir haben einen solchen Bereich. 40:15.120 --> 40:21.840 Da liegen unsere Einsen aus den vier vollständigen, aus den vier 40:21.840 --> 40:22.380 Spalten. 40:23.420 --> 40:27.980 Das waren jeweils diese a plus b plus c plus d Einsen aus den 40:27.980 --> 40:31.720 vollständigen Einszeilen der vier Quadranten. 40:32.720 --> 40:36.560 Jetzt kann es natürlich weiterhin sein, dass wir vier weitere Einsen 40:36.560 --> 40:40.720 bekommen aus den unvollständigen Einszeilen. 40:41.920 --> 40:46.260 Vier weitere Zeilen heißt aber, wir haben hier insgesamt drei Zeilen, 40:46.340 --> 40:47.360 die nicht sortiert sind. 40:48.040 --> 40:51.920 Das wäre schlecht, da reichen zwei Endschritte nicht aus, um zu 40:51.920 --> 40:52.340 sortieren. 40:53.300 --> 40:56.420 Also müssen wir jetzt das ein bisschen genauer betrachten, was 40:56.420 --> 40:57.640 eigentlich vorkommen kann. 40:58.740 --> 41:06.080 Es ist die Frage, gibt es eventuell eine Doppelspalte ohne eine 41:06.080 --> 41:06.940 zusätzliche Eins? 41:08.700 --> 41:11.400 Also eine Doppelspalte, bei der keine Eins vorkommt. 41:12.880 --> 41:20.080 Wann kann das eigentlich passieren, dass eine Doppelspalte keine 41:20.080 --> 41:21.360 zusätzliche Eins hat? 41:21.360 --> 41:28.060 Das heißt, in allen Quadranten ist an dieser Position oben über diesen 41:28.060 --> 41:29.460 vollen Einszeilen eine Null. 41:31.800 --> 41:34.640 So etwas sehen Sie hier nicht in diesem Beispiel. 41:38.980 --> 41:47.120 Wenn ich eine Doppelspalte habe, wo das auftritt, dann kann man sich 41:47.120 --> 41:51.340 überlegen, dass in allen anderen Doppelspalten höchstens drei 41:51.340 --> 41:54.260 zusätzliche Einsen da sein können. 41:57.960 --> 42:06.780 Weil nämlich eine dieser Zeilen in diesen vier Quadranten ganz leer 42:06.780 --> 42:11.300 sein muss, wir haben ja ein ungerades E. 42:13.100 --> 42:20.880 Und wenn diese nicht angefangenen Zeilen alle in die gleiche Richtung 42:20.880 --> 42:27.840 gehen würden, wenn die alle von links nach rechts sortieren würden, 42:28.240 --> 42:39.040 aufsteigen, dann würde das bedeuten, die liegen alle entweder in einer 42:39.040 --> 42:44.640 ungeradzahlig nummerierten Zeile, wenn Sie vier ungerade Zahlen 42:44.640 --> 42:47.240 addieren, haben Sie eine gerade Zahl. 42:48.120 --> 42:52.480 Also wenn das E ungerade sein soll, dann kann es nur so sein, dass 42:52.480 --> 42:55.540 drei in der einen Richtung sortieren und eins in der anderen. 42:56.380 --> 42:57.720 Anders geht es nicht. 42:58.860 --> 43:01.680 Wenn aber drei in der einen Richtung sortieren und eins in die andere, 43:02.320 --> 43:08.620 und wir haben einen Bereich, wo keine Nullen vorkommen, dann sind in 43:08.620 --> 43:17.600 allen anderen Positionen maximal drei angefangene Zeilen da, die noch 43:17.600 --> 43:18.820 hier berücksichtigt werden müssen. 43:19.460 --> 43:23.160 Das heißt, wenn wir eine Doppelspalte haben ohne das zusätzliche Eins, 43:23.160 --> 43:26.800 dann sind es insgesamt höchstens drei zusätzliche Einsen. 43:27.520 --> 43:31.320 Dann würde es aber bedeuten, wir kriegen nur drei dazu, hätten wir 43:31.320 --> 43:35.400 diese beiden Zeilen, die noch sortiert werden müssen, obendrüber 43:35.400 --> 43:38.620 würden diese Felder hier, das wären alles Nullen. 43:40.300 --> 43:43.140 Es wären wieder nur zwei Zeilen noch nicht sortiert. 43:43.660 --> 43:47.700 Der andere Fall wäre, wenn es also keine solche Doppelspalte ohne eine 43:47.700 --> 43:53.380 zusätzliche Eins gibt, dann ist in jeder Position, jeder Doppelspalte, 43:53.580 --> 43:58.320 mindestens eine Eins aus einer angefangenen Halbzeile dabei. 43:59.660 --> 44:03.760 Und das heißt, diese Zeile hier, da es mindestens eine ist, ist diese 44:03.760 --> 44:05.560 Zeile garantiert vollständig sortiert. 44:07.460 --> 44:11.600 Und das heißt, wir haben hier obendrüber noch eventuell zwei Zeilen, 44:11.620 --> 44:12.720 die noch nicht sortiert sind. 44:13.660 --> 44:17.980 Und auch in dem Fall reichen unsere zwei Endschritte aus, um insgesamt 44:17.980 --> 44:18.540 zu sortieren. 44:21.020 --> 44:27.180 Also, wir haben dann jeweils zwei unsortierte Zeilen, insgesamt 44:27.180 --> 44:33.000 reichen also die zwei Endschritte aus von OETS auf der gesamten 44:33.000 --> 44:33.700 Schlangenlinie. 44:34.260 --> 44:39.280 Und wir haben damit gezeigt oder eingesehen, dass dieses Merge, das 44:39.280 --> 44:45.080 Vierfach -Merge von vier in Schlangenlinien sortierten Quadranten, so 44:45.080 --> 44:48.400 auf diese Art und Weise zu einer sortierten Schlangenlinie führt. 44:50.320 --> 44:59.240 Und offensichtlich also mit 4,5n plus 1 Elementen, oder Schritten 44:59.240 --> 44:59.680 meinte ich. 45:00.200 --> 45:01.960 Ich hoffe, das war verständlich. 45:04.620 --> 45:07.640 Und Sie sehen, wie schön das Null-Eins-Prinzip ist. 45:08.260 --> 45:11.220 Stellen Sie sich vor, Sie müssten das argumentieren mit beliebigen 45:11.220 --> 45:11.680 Folgen. 45:12.760 --> 45:14.180 Da hätten Sie sehr viel zu tun. 45:14.620 --> 45:17.480 Da müssten Sie nämlich über den Sortiertheitsgrad einer Folge 45:17.480 --> 45:17.820 argumentieren. 45:18.820 --> 45:24.300 Und müssten zeigen, wie durch den jeweiligen Schritt dieses Verfahrens 45:24.300 --> 45:27.460 der Sortiertheitsgrad der zu sortierenden Folgen sich verringert. 45:27.760 --> 45:31.440 Sodass Sie insgesamt am Ende eine vollständig sortierte Folge haben. 45:31.680 --> 45:40.760 Und hier, dass nach dem Schritt also die maximale Abweichung von der 45:40.760 --> 45:43.040 vollständigen Sortierung halt gerade 2n wäre. 45:44.300 --> 45:45.780 Sehr kompliziertes Verfahren. 45:46.320 --> 45:49.180 Oder sehr komplizierter Beweis, wenn man das so macht mit Null-Einsen. 45:49.440 --> 45:51.220 Ist es sehr einfach zu argumentieren. 45:52.380 --> 45:55.120 Und dann haben wir das gesamte Verfahren LS hoch 3. 45:55.680 --> 46:00.660 Das ist klar, wir machen also für n kleiner gleich 2. 46:00.840 --> 46:03.720 Wenn wir ein kleines Feld haben, dann sortieren wir das Feld durch 46:03.720 --> 46:04.900 einen trivialen Algorithmus. 46:05.580 --> 46:08.540 Also ein kleines Feld mit 4 Elementen kann man sehr schnell in 46:08.540 --> 46:09.520 Schlangenlinien sortieren. 46:09.520 --> 46:12.720 Und das geht also in weniger als 4 Schritten. 46:13.700 --> 46:17.140 Und wenn es größer ist, wenden wir das LS hoch 3 an. 46:18.840 --> 46:22.700 Und verschmelzen das mit dem entsprechenden Verfahren Merge N. 46:23.080 --> 46:29.060 Dann haben wir also hier insgesamt ein Verfahren, das rekursiv so 46:29.060 --> 46:34.320 beschrieben werden kann, dass wir LS hoch 3 Sort anwenden auf einem 46:34.320 --> 46:37.540 Feld der Dimensionen in halbe mal in halbe. 46:38.220 --> 46:41.480 Und anschließend noch 4,5 N dazufügen müssen. 46:42.440 --> 46:46.380 Ich habe jetzt hier das kleine N genommen als Parameter, ich hätte das 46:46.380 --> 46:47.540 große N nehmen können. 46:48.020 --> 46:50.760 Dann müsste ich das entsprechend modifizieren. 46:51.580 --> 46:55.640 Aber insgesamt sieht man, wir haben hier 9 N minus 14. 46:56.320 --> 47:01.240 Wenn man diese Rekursionsgleichung auflöst, und das ist in Groß O von 47:01.240 --> 47:02.860 Wurzel Groß N. 47:03.720 --> 47:06.980 Groß N, also die Anzahl der Elemente, die wir sortieren wollen. 47:07.540 --> 47:12.100 Wir würden in Wurzel N eine Folge mit N Zahlen sortieren, wenn wir ein 47:12.100 --> 47:13.380 zweidimensionales Feld nehmen. 47:14.880 --> 47:19.220 9 N minus 14, man kann mit ein bisschen genauer hingucken, kann man an 47:19.220 --> 47:22.740 ein paar Stellen ein bisschen einsparen und kommt dann bei diesem 47:22.740 --> 47:24.140 Verfahren sogar auf 7 N. 47:25.600 --> 47:28.880 Weiter sind wir bei diesem Ansatz nicht runtergekommen. 47:29.800 --> 47:35.720 Es gibt aber ein Verfahren, das tatsächlich mit 3 N arbeitet. 47:36.860 --> 47:46.100 Und 3 N ist schon im Vergleich zu dem Faktor 3 schneller, ist aber ein 47:46.100 --> 47:48.620 sehr kompliziertes Verfahren. 47:49.180 --> 47:50.660 Da gehe ich später nochmal drauf ein. 47:51.560 --> 47:54.100 Und die untere Schranke, die werden wir uns gleich überlegen, diese 47:54.100 --> 47:56.040 untere Schranke 3 N, wo die herkommt. 47:57.280 --> 48:01.140 Wir sind also ziemlich nah dran an der unteren Schranke mit den 7 N. 48:01.140 --> 48:05.460 Und das bezieht sich auf ein MIMD-Verfahren. 48:07.120 --> 48:11.160 Warum haben wir uns dieses Verfahren, das beste Sortierverfahren mit 3 48:11.160 --> 48:13.680 N, war schon bekannt. 48:13.780 --> 48:16.640 Das haben wir auch gekannt, als wir dieses LSO3-Verfahren entwickelt 48:16.640 --> 48:17.080 haben. 48:17.880 --> 48:23.700 Das war aber analysiert und beschrieben als ein Verfahren unter dem 48:23.700 --> 48:24.780 SIMD -Modell. 48:25.760 --> 48:31.180 Unter dem SIMD-Modell hatte das eine höhere Anzahl von 48:31.180 --> 48:31.780 Einzeloperationen. 48:33.300 --> 48:37.080 Und bezüglich dieser Zählweise von Operationen war unser Verfahren 48:37.080 --> 48:37.380 besser. 48:38.000 --> 48:41.440 Aber ein MIMD-Verfahren, ein anderes Berechnungsmodell, da hatten wir 48:41.440 --> 48:42.480 einen kleinen Fehler gemacht. 48:43.200 --> 48:47.480 Und es war tatsächlich so, dass bei einer Konferenz, wo wir dann, 48:49.640 --> 48:54.140 einer meiner Kollegen hatte dann ein optimales Verfahren für Sortieren 48:54.140 --> 48:58.500 auf zweidimensionalen Feldern in der Zeit 3 N, das war noch anders als 48:58.500 --> 49:01.120 das, was wir hier gemacht haben, tatsächlich entwickelt. 49:01.760 --> 49:04.480 Da meldet sich einer der Autoren dieses anderen Verfahrens, das wir 49:04.480 --> 49:07.800 schon kannten, und sagte, er hätte doch oft nur eins gehabt mit 3 N. 49:08.380 --> 49:11.820 Nur das war so dargestellt, dass man das einfach nicht gesehen hat. 49:15.440 --> 49:19.440 Also gleichzeitig eine ganze Reihe von Verfahren, die vorgestellt 49:19.440 --> 49:24.120 wurden auf Sortierverfahren auf zweidimensionalen Feldern, die alle 49:24.120 --> 49:28.000 versuchten weiter heranzukommen an dieses 3 N und die etwa in der 49:28.000 --> 49:33.000 gleichen Klasse waren wie unser LSO3-Sort, aber mit einer wesentlich 49:33.000 --> 49:34.120 komplizierteren Struktur. 49:34.500 --> 49:36.900 Also ich behaupte, unser Verfahren ist wirklich sehr einfach mit 49:36.900 --> 49:37.660 diesen drei Schritten. 49:40.260 --> 49:43.420 Und auf jeden Fall eignet sich das sehr gut, um das in einer Vorlesung 49:43.420 --> 49:44.380 schnell mal vorzustellen. 49:45.760 --> 49:49.140 So, jetzt gehen wir zu den unteren Schranken. 49:49.580 --> 49:51.560 Warum kommt man auf 3 N? 49:51.600 --> 49:53.460 Wir hatten vorhin gesagt, trivial ist 2 N. 49:55.080 --> 49:56.700 Wie kommt man auf 3 N? 49:57.080 --> 50:00.400 Wir nehmen an, wir müssen jetzt eine allgemeine Untersuchung machen 50:00.400 --> 50:04.220 für beliebige Verfahren, auch auf beliebigen zweidimensionalen 50:04.220 --> 50:04.460 Feldern. 50:04.460 --> 50:07.380 Dann ist es gar nicht so einfach, welche Annahmen man dort macht. 50:08.420 --> 50:11.160 Wir nehmen an, wir haben eine geordnete Datenmenge D, wir haben 50:11.160 --> 50:13.300 irgendwie Z-Zeilen und S-Spalten. 50:15.040 --> 50:19.740 Jeder Prozessor, der enthält also hier ein Datum in einem 50:19.740 --> 50:21.640 Kommunikationsregister. 50:21.860 --> 50:25.900 Das heißt, die Nachbarn können darauf zugreifen, auf dieses Register. 50:26.640 --> 50:29.680 Und er kann beliebige weitere Elemente in seinem lokalen Speicher 50:29.680 --> 50:30.000 haben. 50:31.560 --> 50:35.140 Jeder Prozessor kann also in jedem Takt die Inhalte seiner Nachbarn 50:35.140 --> 50:35.640 lesen. 50:35.680 --> 50:36.560 Das ist also ein Takt. 50:37.400 --> 50:41.900 Inhalte lesen, Operationen ausführen und den eigenen Speicherbereich 50:41.900 --> 50:42.320 verändern. 50:43.540 --> 50:49.100 Wenn ich also zum Beispiel zwei hier nebeneinander hätte, da könnte 50:49.100 --> 50:51.860 jeder beim Nachbarn das Element lesen. 50:52.680 --> 50:55.840 Und der eine würde das Minimum sich hinschreiben in sein eigenes 50:55.840 --> 50:58.360 Register, der andere das Maximum der beiden Elemente. 50:58.360 --> 51:02.360 Dann hätten sie ein Vergleich und Vertausch im Prinzip dargestellt. 51:04.060 --> 51:09.380 Also das heißt, wir können in einem Takt lesen, Operationen ausführen 51:09.380 --> 51:11.080 und den eigenen Speicherbereich verändern. 51:12.140 --> 51:15.440 Wir könnten also so einen Vergleich und Vertauschung in einem Takt 51:15.440 --> 51:16.360 ausführen. 51:17.880 --> 51:21.400 Die Inhalte der Kommunikationsregister seien zeilenweise oder 51:21.400 --> 51:23.380 zeilenweise in Schlangenlinien zu sortieren. 51:23.380 --> 51:25.600 Beides sei hier mal angenommen. 51:26.040 --> 51:28.480 Man kann das Ganze, die unteren Schranken, auch auf andere 51:28.480 --> 51:33.960 Sortierordnungen anwenden und kommt dann auch zu ähnlichen Schranken. 51:35.680 --> 51:38.720 Triviale untere Schranke kennen Sie schon, S plus Z minus 2. 51:39.500 --> 51:44.100 Das war die Überlegung, dass wir hier einmal so durchlaufen müssen. 51:45.180 --> 51:46.140 Das ist also trivial. 51:47.240 --> 51:48.300 Nicht trivial. 51:49.460 --> 51:53.200 Ich zeichne das einfach, um Ihnen zu zeigen, wie man solche Beweise 51:53.200 --> 51:54.480 macht über untere Schranken. 51:55.580 --> 52:00.160 Für untere Schranke muss ich etwas zeigen, dass ein beliebiges 52:00.160 --> 52:04.680 Verfahren für bestimmte Folgen mindestens eine gewisse Zeit braucht. 52:04.860 --> 52:09.360 Egal welches Verfahren ich nehme, muss ich einen schlechten Fall 52:09.360 --> 52:13.660 konstruieren können, für den das Verfahren schlecht wird oder lange 52:13.660 --> 52:14.400 Zeit braucht. 52:15.560 --> 52:18.840 Wir hatten gesagt, wir nehmen an, dass unsere Datenmenge eine 52:18.840 --> 52:20.120 geordnete Menge ist. 52:20.180 --> 52:23.620 Wir nehmen mal an, wir haben hier eine große Datenmenge zur Verfügung 52:23.620 --> 52:27.240 und nehmen mal an, wir können negative und positive Zahlen da 52:27.240 --> 52:35.860 reinschreiben und können das also so machen, dass wir das Feld 52:35.860 --> 52:41.740 vollständig von 1 bis n² mit Zahlen füllen könnten oder auch mit 52:41.740 --> 52:42.540 negativen Zahlen. 52:43.820 --> 52:47.940 Das ist sicherlich keine besondere Einschränkung, das ist immer noch 52:47.940 --> 52:49.760 eine sehr beliebige Folge. 52:50.440 --> 52:53.220 Die Anordnung ist sehr wichtig, nicht welche Elemente da sind. 52:53.640 --> 52:57.620 Das Ganze sind ja Operationen, bei denen es nur darauf ankommt, Größen 52:57.620 --> 52:58.920 von Elementen zu vergleichen. 52:58.980 --> 53:01.320 Die konkreten Werte werden hier nicht ausgenutzt. 53:01.400 --> 53:02.460 Das ist ein ganz wichtiger Punkt. 53:03.460 --> 53:10.320 So, jetzt nehmen wir uns eine Anfangsbelegung her unseres Feldes und 53:10.320 --> 53:15.500 das sei also eine Anfangsbelegung nur von Zahlen aus dem Bereich 1 bis 53:15.500 --> 53:16.020 n². 53:16.800 --> 53:20.500 Also nur positive Zahlen, irgendwie verteilt auf unser 53:20.500 --> 53:21.740 zweidimensionales Feld. 53:21.740 --> 53:27.060 Jetzt kommt die wesentliche Idee, wir betrachten einen bestimmten 53:27.060 --> 53:33.860 Bereich dieses Feldes und wollen untersuchen, wie dieser Bereich, das 53:33.860 --> 53:41.620 ist also der Bereich, jetzt hier grau angedeutet, wir wollen uns 53:41.620 --> 53:48.980 angucken, wie dieser Bereich das Element hier oben beeinflusst. 53:51.180 --> 53:53.580 Also, ich möchte folgendes machen. 53:54.720 --> 54:00.220 Ich möchte angucken, wie dieser dreieckige schraffierte Bereich den 54:00.220 --> 54:02.420 Sortiervorgang insgesamt beeinflusst. 54:03.160 --> 54:04.800 Und ich nenne das Ganze Jokerzone. 54:04.940 --> 54:06.900 Sie kennen Joker aus dem Kartenspiel. 54:07.500 --> 54:08.480 Welche Rolle hat ein Joker? 54:09.040 --> 54:14.060 Ich lege ihn einfach hin und bei Bedarf nimmt er irgendeinen Wert an, 54:14.140 --> 54:15.560 der gerade passt zu der Umgebung. 54:15.560 --> 54:20.240 Und hier will ich also mir angucken, was das Sortierverfahren macht 54:20.240 --> 54:21.220 mit dieser Folge. 54:21.980 --> 54:24.700 Und dann will ich erst sagen, welche Elemente dort in dem Dreieck 54:24.700 --> 54:25.580 tatsächlich drin sind. 54:25.760 --> 54:27.700 Welche Werte dort eigentlich drinstehen. 54:28.360 --> 54:31.160 Das heißt, das ist der Bereich, mit dem ich spielen kann. 54:31.960 --> 54:36.140 Mein Jokerbereich, den ich verändern kann, um einen schlechten Fall zu 54:36.140 --> 54:36.780 konstruieren. 54:38.700 --> 54:43.280 So, jetzt sage ich, es sollen dort mindestens zwei S-Elemente liegen. 54:43.600 --> 54:47.860 Das heißt, ich habe hier diese Seitenlängen, müssen gerade größer 54:47.860 --> 54:49.360 gleich zweimal Wurzel S sein. 54:50.060 --> 54:54.600 Da wissen wir, die Fläche da unten drunter ist dann mindestens zwei S. 54:55.060 --> 55:00.520 Und S ist die Anzahl der Spalten meines zweidimensionalen Feldes. 55:00.700 --> 55:04.640 Das ich hier immer quadratisch aufgemalt habe, aber könnte auch völlig 55:04.640 --> 55:06.700 andere Größenverhältnisse haben. 55:09.800 --> 55:14.480 So, und ich nehme noch an, dass die Elemente in der Jokerzone zu 55:14.480 --> 55:16.940 Anfang zumindest größer sind als alle anderen. 55:18.220 --> 55:20.680 Ich will ja nur irgendeinen schlechten Fall konstruieren. 55:21.320 --> 55:23.660 Ein schlechter Fall kann auch darin bestehen, dass ich hier unten 55:23.660 --> 55:26.680 große Elemente habe, wo man sagt, naja, das Ganze soll ja sortiert 55:26.680 --> 55:27.060 werden. 55:27.720 --> 55:29.020 Dann bleiben die ja alle hier unten. 55:29.160 --> 55:32.360 Wenn die alle so groß sind, dann können die ja gar nicht viel 55:32.360 --> 55:32.860 beeinflussen. 55:32.940 --> 55:35.300 Aber Sie werden sehen, dass es wichtig ist, diese Annahme zu machen. 55:36.820 --> 55:41.680 Und das heißt eben insbesondere, Elemente, die hier oben stehen, die 55:41.680 --> 55:45.940 werden durch die Elemente, die hier sind, nicht in ihrer Anordnung 55:45.940 --> 55:46.880 irgendwie verschoben. 55:47.400 --> 55:51.460 Sondern die Elemente, die hier in dem weißen Bereich liegen, deren 55:51.460 --> 55:55.980 Rangfolge, deren Anordnung in der sortierten Folge wird eigentlich 55:55.980 --> 56:01.000 unabhängig sein von den Elementen, die in dem dreieckigen Bereich 56:01.000 --> 56:02.080 dieser Jokerzone liegen. 56:03.380 --> 56:07.960 So, und jetzt nehmen wir an, wir haben ein beliebiges 56:07.960 --> 56:11.240 Sortierverfahren, das mit einer solchen Folge arbeiten muss. 56:12.160 --> 56:17.780 Wir nehmen auch noch an, dass die Prozessoren nicht beliebig mächtig 56:17.780 --> 56:22.380 sind, sondern die enthalten nach jedem Schritt genau ein Element der 56:22.380 --> 56:23.300 zu sortierenden Folge. 56:23.300 --> 56:27.240 Die können also nicht so eine große Menge von Elementen der 56:27.240 --> 56:33.580 sortierenden Folge abspeichern und dann das ausnutzen, um weitere 56:33.580 --> 56:34.540 Operationen auszuführen. 56:34.940 --> 56:37.180 Die haben immer nur ein Element, auf das sie zugreifen können. 56:38.940 --> 56:40.740 Und jetzt überlegen wir uns Folgendes. 56:42.020 --> 56:45.660 Wir hatten ja gesagt, wir wollen sehen, welcher Einfluss dieses 56:45.660 --> 56:48.380 Dreieck hat auf den Sortiervorgang. 56:50.180 --> 56:55.740 Wie lange dauert es denn, bis Informationen über die Elemente in 56:55.740 --> 57:00.960 diesem dreieckigen Feld überhaupt hier links oben angekommen sein 57:00.960 --> 57:01.120 können? 57:01.180 --> 57:03.800 Das ist das am weitesten entfernte Element in dem Feld. 57:04.500 --> 57:10.400 Das heißt, es wird am längsten dauern, Auswirkungen der Werte, die in 57:10.400 --> 57:13.900 dem Dreieck gespeichert sind, hier oben spürbar zu machen. 57:15.140 --> 57:22.440 In jedem Schritt kann ich ja nur eine Diagonale weiter mich nach vorne 57:22.440 --> 57:24.300 bewegen, also in dieser Richtung. 57:25.340 --> 57:28.080 Ich kann eins nach oben, eins nach links und so weiter. 57:28.540 --> 57:33.360 In jedem Schritt kann ich so sukzessive Operationen ausführen und 57:33.360 --> 57:37.960 komme diesem Element dort oben immer näher. 57:37.960 --> 57:39.880 Und wie lange dauert das? 57:40.640 --> 57:47.940 Wir hatten hier insgesamt, dieses hier sind ja Z-Zeilen, wir hatten 57:47.940 --> 58:01.320 hier zwei Wurzel S, das war dieser Teil, zwei Wurzel S. 58:05.240 --> 58:16.080 Also Z-2 Wurzel S, dann dauert das genau Z-2 Wurzel S, dann sind wir 58:16.080 --> 58:22.420 hier oben, also diesen Bereich hier zu laufen, das ist Z-2 Wurzel S. 58:23.000 --> 58:26.760 Und dann müssten wir uns ja noch diese Distanz angucken und das ist 58:26.760 --> 58:30.420 nochmal S-1, um von dort nach dort zu kommen. 58:30.420 --> 58:36.340 Das heißt, wir haben insgesamt, das ist ja die Differenz der 58:36.340 --> 58:40.700 Koordinaten, das ist ja gerade die Anzahl der Takte, die ich brauche, 58:40.780 --> 58:41.380 um da hinzukommen. 58:41.980 --> 58:47.120 Ich habe genau so viele Takte, bis in diesem Feld der Prozessor, der 58:47.120 --> 58:51.000 dort liegt, Informationen über den Inhalt der Joker-Zone erhalten 58:51.000 --> 58:51.440 kann. 58:52.960 --> 58:57.240 Vorher kann das, was dort passiert, sich nicht ausgewirkt haben oder 58:57.240 --> 59:02.360 nicht beeinflusst gewesen sein durch Elemente aus dem Dreieck. 59:03.720 --> 59:07.480 Insbesondere stammt das Element, das dort in dem Augenblick liegt, 59:08.800 --> 59:13.640 nicht aus der Joker-Zone, sondern ist ein Element aus dem weißen 59:13.640 --> 59:16.520 Bereich, das durch irgendwelche anderen Operationen dahingekommen ist. 59:17.760 --> 59:26.520 Und jetzt bewegt das Sort anschließend dieses Element A natürlich an 59:26.520 --> 59:29.120 die endgültige Position, die kann ja irgendwo sein. 59:29.200 --> 59:33.060 Wir hatten bisher nur geguckt, wie lange dauert es, bis Information 59:33.060 --> 59:36.940 aus dem dreieckigen Bereich, aus der Joker-Zone, sich auswirken kann 59:36.940 --> 59:39.840 auf das Element, das in der Zelle 1.1 liegt. 59:40.720 --> 59:43.120 Danach muss das Verfahren nicht fertig sein. 59:43.200 --> 59:46.680 Es kann sein, dass das noch weiter sortiert wird und dass das Element 59:46.680 --> 59:50.900 A jetzt noch wandert an irgendeine Position. 59:52.040 --> 59:54.560 Und das ist jetzt eine Position in der Spalte J. 59:56.480 --> 01:00:00.500 Das sei die endgültige Position, wenn die Folge sortiert ist. 01:00:01.760 --> 01:00:05.020 Und jetzt setze ich den Joker ein. 01:00:06.480 --> 01:00:14.880 Jetzt verändere ich meine Folge so, dass das A garantiert noch weiter 01:00:14.880 --> 01:00:19.320 wandern muss, nämlich garantiert ganz nach rechts wandern muss. 01:00:20.600 --> 01:00:22.060 Wie kann ich das erreichen? 01:00:23.120 --> 01:00:27.060 Gerade eben sah das so aus, als wenn das nur ein paar Schritte nach 01:00:27.060 --> 01:00:34.300 rechts wandern muss, nur die Distanz S-J überwinden muss. 01:00:35.200 --> 01:00:40.180 Das kann aber sein, dass das Element hier irgendwo lag und um das 01:00:40.180 --> 01:00:42.920 jetzt ganz nach rechts zu bewegen, muss es erstmal in der 01:00:42.920 --> 01:00:44.560 Sortierreihenfolge ganz rumlaufen. 01:00:45.640 --> 01:00:49.560 Das heißt, um das so darüber zu bewegen, muss ich ja dafür sorgen, 01:00:50.280 --> 01:00:55.220 dass entsprechend kleinere Elemente in der Folge sind, die dazu 01:00:55.220 --> 01:01:00.040 führen, dass das Element A einen höheren Rang erhält in der zu 01:01:00.040 --> 01:01:00.880 sortierenden Folge. 01:01:01.660 --> 01:01:07.520 So, und nun muss ich also genügend viele Elemente zur Verfügung haben, 01:01:07.800 --> 01:01:13.860 um dieses Element von der vorherigen Position an diese Position rechts 01:01:13.860 --> 01:01:14.340 zu schieben. 01:01:14.840 --> 01:01:17.880 Und im schlechtesten Fall muss ich das über diese Schlangenlinie 01:01:17.880 --> 01:01:23.260 schieben und deswegen brauche ich dafür zwei S-1 Werte, die kleiner 01:01:23.260 --> 01:01:24.740 sein müssen als das Element A. 01:01:25.460 --> 01:01:30.940 Und das mache ich einfach so, dass ich die Werte, dass ich zwei S-1, 01:01:31.080 --> 01:01:36.480 beziehungsweise ausreichend viele Elemente aus der Jokerzone negativ 01:01:36.480 --> 01:01:36.800 mache. 01:01:37.700 --> 01:01:42.360 Die sind garantiert alle kleiner als das Element A, diese negativen 01:01:42.360 --> 01:01:44.660 Werte, weil alle anderen, alle Werte waren ja positiv. 01:01:44.660 --> 01:01:48.120 Diese negativen sind kleiner als alle anderen, liegen also ganz am 01:01:48.120 --> 01:01:48.900 Anfang der Folge. 01:01:50.120 --> 01:01:54.180 Und keines der Elemente, das ich jetzt negiert habe, war vorher 01:01:54.180 --> 01:01:55.120 kleiner als A. 01:01:55.860 --> 01:02:00.280 Weil ja alle Elemente aus der dreieckigen Zone größer als A sein 01:02:00.280 --> 01:02:04.320 sollten, beziehungsweise größer als alle anderen Elemente in dem Feld. 01:02:05.300 --> 01:02:10.700 Und deswegen kann ich garantieren, dass ich ausreichend viele Elemente 01:02:10.700 --> 01:02:15.900 in meiner Jokerzone habe, um das Element ganz nach rechts zu schieben. 01:02:16.660 --> 01:02:22.540 Und wenn ich das hingekriegt habe, dann weiß ich, dass ich nach dem 01:02:22.540 --> 01:02:29.360 Zeitpunkt, wo ich frühestens Informationen aus dem dreieckigen Feld 01:02:29.360 --> 01:02:34.000 der Jokerzone hatte, die das Element A beeinflussen konnten, noch 01:02:34.000 --> 01:02:39.980 mindestens S-1 Takte brauche, um das Element von dort nach rechts zu 01:02:39.980 --> 01:02:42.280 schieben, in die rechteste Spalte. 01:02:44.860 --> 01:02:52.060 Also habe ich insgesamt diese Z-2 Wurzel S plus S-1 Takte, das war das 01:02:52.060 --> 01:02:55.000 erste, nochmal S-1 weitere Schritte. 01:02:57.460 --> 01:03:01.880 Das ist also die Überlegung für diesen Beweis der unteren Schranke. 01:03:02.280 --> 01:03:05.360 Das Wesentliche ist diese Idee mit dieser Jokerzone, die ich so 01:03:05.360 --> 01:03:09.300 anordnen kann, dass ich einen schlechten Fall konstruiere, mit dem 01:03:09.300 --> 01:03:12.020 dieser beliebige Algorithmus auch zurechtkommen muss. 01:03:12.180 --> 01:03:14.520 Und ich sage, der braucht dann mindestens so und so viele Takte. 01:03:15.920 --> 01:03:19.720 Und die untere Schranke ist also genau der Wert, den wir gerade eben 01:03:19.720 --> 01:03:20.820 auf der Folienfolie hatten. 01:03:23.400 --> 01:03:28.560 Und das hier ist also genau der Wert. 01:03:29.300 --> 01:03:34.720 Das Ganze ist aus Z plus 2S minus irgendwas Größenordnung Wurzel S. 01:03:39.130 --> 01:03:43.670 So, das ist offensichtlich die untere Schranke, Z plus 2S. 01:03:45.990 --> 01:03:48.550 Z plus 2S, das ist ja ganz einfach. 01:03:49.550 --> 01:03:54.570 Wenn wir ein quadratisches Feld haben, S gleich Z gleich N, haben wir 01:03:54.570 --> 01:03:58.830 also N plus 2N macht 3N minus Groß O von Wurzel N. 01:03:59.550 --> 01:04:01.990 Das ist was kleines, das kann ich ignorieren. 01:04:03.230 --> 01:04:08.070 Ich habe also vor dem Term größter Ordnung, dem N, habe ich eine 3 01:04:08.070 --> 01:04:08.410 stehen. 01:04:09.910 --> 01:04:14.830 Und damit habe ich also das von 2N auf 3N erhöht, diese untere 01:04:14.830 --> 01:04:15.250 Schranke. 01:04:15.990 --> 01:04:22.530 Wenn ich jetzt S und Z anders wähle, also zum Beispiel ein Feld wähle, 01:04:22.650 --> 01:04:29.850 das in etwa so eine Struktur hat, dann ist natürlich mit diesem 01:04:29.850 --> 01:04:36.530 Argument der Einfluss der Anzahl der Spalten nicht mehr so groß. 01:04:37.890 --> 01:04:44.070 Wenn ich also S gleich N durch Wurzel 2 habe, und entsprechend Z 01:04:44.070 --> 01:04:52.010 gleich N mal Wurzel 2, dann ist unsere untere Schranke 2 mal Wurzel 2 01:04:52.010 --> 01:04:52.530 mal N. 01:04:53.470 --> 01:04:58.530 Wurzel 2 ist 1,4, so grob. 01:04:59.790 --> 01:05:05.330 Das heißt, das wäre etwa 2,8 mal N, also etwas weniger. 01:05:08.250 --> 01:05:10.530 Gut, also damit haben wir eine untere Schranke. 01:05:10.710 --> 01:05:13.710 Für quadratische Felder haben wir also 3N, das untere Schranke. 01:05:13.850 --> 01:05:16.710 Für nicht-quadratische Felder eine etwas kleinere Schranke. 01:05:18.050 --> 01:05:25.250 Und wenn das Verhältnis also noch mehr zu Lasten der Zeilen geht, dann 01:05:25.250 --> 01:05:29.670 wird also nicht noch kleiner der Wert, sondern wird er wieder größer. 01:05:31.110 --> 01:05:34.970 Jetzt gibt es das Verfahren von Thompson-Kung, das sogenannte S 01:05:34.970 --> 01:05:36.090 -Quadrat -Wave-Merge. 01:05:36.150 --> 01:05:39.270 Dieses S-Quadrat ist allerdings nicht die Anzahl der Spalten in diesem 01:05:39.270 --> 01:05:41.270 Fall, sondern ist gleich der Wurzel aus N. 01:05:41.270 --> 01:05:46.890 Das heißt, die machen folgendes, die haben hier ihr zweidimensionales 01:05:46.890 --> 01:05:47.230 Feld. 01:05:48.490 --> 01:05:58.370 Jetzt machen sie hier eine Aufteilung in Wurzel-N, also 1 bis Wurzel-N 01:05:58.370 --> 01:05:59.750 Teilfelder. 01:06:01.650 --> 01:06:08.410 Und die Länge jeweils, also hier, das sind jeweils Wurzel-N Zeilen. 01:06:09.090 --> 01:06:12.110 Das heißt, ich habe hier jeweils N Elemente drin. 01:06:16.410 --> 01:06:24.310 Und entsprechend habe ich hier also ein sehr breites Merge, S-Quadrat 01:06:24.310 --> 01:06:24.970 -Wave -Merge. 01:06:25.930 --> 01:06:29.130 Wir hatten bei dem LSO3-Verfahren ein Vierfach-Merge. 01:06:29.590 --> 01:06:36.450 Hier ist es ein S-Quadrat, also ein N-Fach-Merge. 01:06:39.350 --> 01:06:45.130 Und dieses Verfahren ist in jedem der beiden Fälle, ob ich also jetzt 01:06:45.130 --> 01:06:50.450 dieses Seitenverhältnis habe oder quadratisches Feld, kommt in jedem 01:06:50.450 --> 01:06:55.070 Fall mit 3N Operationen aus, sofern ich MIMD erlaube. 01:06:56.330 --> 01:07:00.670 Dieses Verfahren lag schon vor, auch als wir LSO3 entwickelt haben 01:07:00.670 --> 01:07:05.530 oder als viele andere auch noch solche 2-dimensionalen Feldern 01:07:05.530 --> 01:07:08.110 entworfen haben. 01:07:08.470 --> 01:07:13.610 Aber die beiden Thompson und Kung, die haben nicht das Null-Eins 01:07:13.610 --> 01:07:15.930 -Prinzip verwendet für den Beweis der Korrektheit. 01:07:16.450 --> 01:07:20.390 Ein sehr komplizierter Artikel, sehr komplizierte Argumentation 01:07:20.390 --> 01:07:22.830 darüber, warum das Ganze korrekt ist. 01:07:25.390 --> 01:07:29.110 Und unser Artikel war ganz einfach zu lesen, ganz einfach zu beweisen, 01:07:29.110 --> 01:07:29.990 dass es richtig ist. 01:07:30.650 --> 01:07:37.410 Der Beweis war eben so, dass es dort ein SIMD-Verfahren war, mit 01:07:37.410 --> 01:07:41.090 deutlich höherer Anzahl von Operationen. 01:07:42.330 --> 01:07:50.890 Und bei SIMD ist es so, dass man mittlerweile bei 6N ist, für die 01:07:50.890 --> 01:07:52.090 Anzahl der Operationen. 01:07:52.510 --> 01:07:55.310 Man kennt aber keine bessere Schranke, als die, die wir gerade 01:07:55.310 --> 01:07:56.090 überlegt haben. 01:07:56.850 --> 01:07:59.030 Also insofern ist man da auch relativ nah dran. 01:07:59.830 --> 01:08:03.510 Und es ist halt einfach interessant, inwieweit man tatsächlich bei 01:08:03.510 --> 01:08:09.050 Problemen exakt optimale Verfahren bekommen kann, die sogar bezüglich 01:08:09.050 --> 01:08:11.710 der Konstante genau die untere Schranke erreichen. 01:08:12.290 --> 01:08:15.090 Das haben wir bei der Auswertung von Polynomen gesehen. 01:08:15.370 --> 01:08:18.870 Da war das beim Horner-Schema so, dass wir genau die Anzahl der 01:08:18.870 --> 01:08:19.610 Operationen hatten. 01:08:20.150 --> 01:08:25.970 Hier bei der Anzahl der Schritte geht es also bei MEMD auch. 01:08:26.090 --> 01:08:27.330 Mit genau 3N. 01:08:28.410 --> 01:08:35.230 Aber wenn man halt sagt, ich mache SIMD, dann ist das schon etwas 01:08:35.230 --> 01:08:37.490 schwieriger, die untere Schranke noch weiter nach oben zu drücken. 01:08:39.110 --> 01:08:43.710 Wenn man diese Annahme nicht macht, dass die Prozessoren nur ein 01:08:43.710 --> 01:08:48.350 Element der Folge speichern dürfen, durchaus noch irgendwelche anderen 01:08:48.350 --> 01:08:53.210 Elemente, aber die dürfen das nicht wirklich weiter ausnutzen, dann 01:08:53.210 --> 01:08:56.830 ist es so, dass man tatsächlich nur die triviale untere Schranke hat. 01:08:58.230 --> 01:09:03.370 Und dann gibt es auch schnellere Sortierverfahren, die nah rankommen 01:09:03.370 --> 01:09:04.450 an das 2N. 01:09:05.370 --> 01:09:08.590 Da gibt es einen Übersichtsartikel von Nigam und Sani aus dem Jahr 01:09:08.590 --> 01:09:09.170 1995. 01:09:10.090 --> 01:09:13.670 Die haben das alles mal zusammengestellt und das waren also ganz 01:09:13.670 --> 01:09:14.650 interessante Überlegungen. 01:09:15.270 --> 01:09:17.330 Warum ist man überhaupt so an diesen Sortierverfahren auf 01:09:17.330 --> 01:09:18.730 zweidimensionalen Feldern interessiert? 01:09:18.730 --> 01:09:22.110 Ich sagte schon, es gibt halt Prozessorarchitekturen mit 01:09:22.110 --> 01:09:25.570 zweidimensionalen Feldern und das Interessante ist nicht unbedingt 01:09:25.570 --> 01:09:29.250 jetzt einzelne, also zu sortieren, wenn ich nur einzelne Daten drauf 01:09:29.250 --> 01:09:34.790 drin habe, sondern ich möchte sortieren größere Dateien über ein 01:09:34.790 --> 01:09:36.170 zweidimensionales Feld hinweg. 01:09:36.590 --> 01:09:41.370 Muss ich eine größere Datenmenge insgesamt sortieren und mache dann 01:09:41.370 --> 01:09:45.950 eben Operationen auf einzelnen Dateien und dafür sind das interessante 01:09:45.950 --> 01:09:46.530 Verfahren. 01:09:46.530 --> 01:09:50.170 Oder Sie wollen in Hardware tatsächlich ein Sortierverfahren 01:09:50.170 --> 01:09:53.870 implementieren auf einzelnen Elementen und müssen meinetwegen in 01:09:53.870 --> 01:09:57.790 irgendwelchen Signalprozessoren effiziente Hardware entwickeln. 01:09:58.590 --> 01:10:02.090 Und dafür sind diese Verfahren eben auch sehr gut geeignet. 01:10:02.510 --> 01:10:05.290 Da haben wir auch unser Verfahren direkt auf dem Chip implementiert. 01:10:05.670 --> 01:10:07.870 Also das gibt es, dieses LSO3 gibt es auch direkt auf dem Chip 01:10:07.870 --> 01:10:14.250 implementiert und hat eben den Vorteil, dass Sie keine langen 01:10:14.250 --> 01:10:17.450 Leitungen brauchen für die Kommunikation zwischen Elementen, die 01:10:17.450 --> 01:10:21.030 irgendwelche Werte berechnen, sondern alle Kommunikation geht über 01:10:21.030 --> 01:10:22.050 direkte Nachbarschaft. 01:10:22.930 --> 01:10:25.530 Und das ist der wesentliche Punkt bei diesem Verfahren. 01:10:26.970 --> 01:10:29.570 Gut, das war also die untere Schranke. 01:10:29.690 --> 01:10:32.650 Ich sagte schon, es gibt zahlreiche Arbeiten, auch für andere 01:10:32.650 --> 01:10:36.990 Sortierordnungen, spaltenweise, spiralförmig. 01:10:37.550 --> 01:10:39.510 Dann kann ich andere Strukturen machen. 01:10:39.670 --> 01:10:42.530 Ich kann zweidimensionale Gitter mit Wraparound verwenden, also ein 01:10:42.530 --> 01:10:42.990 Torus. 01:10:42.990 --> 01:10:44.570 Ich kann sehen, wie ich darauf sortieren kann. 01:10:45.070 --> 01:10:47.130 Oder auf einem Kreis, oder was immer Sie sich vorstellen. 01:10:47.310 --> 01:10:49.610 Also der Fantasie sind da kaum Grenzen gesetzt. 01:10:50.310 --> 01:10:54.030 Und man kriegt immer irgendwelche Erkenntnisse über Sortierverfahren. 01:10:54.670 --> 01:10:57.390 Und ich möchte Ihnen eine andere Struktur noch kurz vorstellen, weil 01:10:57.390 --> 01:10:59.130 die eigentlich sehr interessant ist. 01:10:59.690 --> 01:11:06.090 Ist ein bisschen etwas, was diese beliebig parallelen PRAMs verbindet 01:11:06.090 --> 01:11:07.730 mit zweidimensionalen Feldern. 01:11:08.370 --> 01:11:09.970 Das ist ein sogenanntes Mesh of Trees. 01:11:13.150 --> 01:11:15.110 Und was ist so ein Gitter von Bäumen? 01:11:15.610 --> 01:11:18.270 Sie sehen das, wir haben hier ein zweidimensionales Feld. 01:11:19.070 --> 01:11:21.050 Nur wir haben keine nächsten Nachbarschaftsverbindungen. 01:11:21.370 --> 01:11:25.050 Beziehungsweise, wenn Sie genauer hingucken, haben wir hier auch so 01:11:25.050 --> 01:11:25.990 direkte Nachbarschaftsverbindungen. 01:11:26.770 --> 01:11:29.170 Die sind durchaus miteinander verbunden. 01:11:30.750 --> 01:11:32.670 Der auch mit der, mit dem, der mit dem. 01:11:32.790 --> 01:11:35.670 Also die sind so miteinander durchaus verbunden. 01:11:35.790 --> 01:11:38.590 Wobei, die sind hier nicht direkt verbunden, die beiden Elemente in 01:11:38.590 --> 01:11:38.810 der Mitte. 01:11:38.810 --> 01:11:43.310 Aber ich habe durchaus so kleine, fast direkte Verbindungen. 01:11:43.470 --> 01:11:44.490 Aber das geht dann über den Baum. 01:11:45.470 --> 01:11:47.070 Also das ist eine andere Struktur. 01:11:48.530 --> 01:11:51.210 Bei diesem Mesh of Trees habe ich also ein Gitter. 01:11:52.150 --> 01:11:54.990 Und ich habe sogenannte Spaltenbäume, die sind hier in grün 01:11:54.990 --> 01:11:55.770 gezeichnet. 01:11:56.890 --> 01:11:59.650 Ich habe Seilenbäume, die sind hier in blau gezeichnet. 01:11:59.890 --> 01:12:01.350 Und jetzt möchte ich sortieren. 01:12:02.550 --> 01:12:04.470 Also ein Verfahren von Tom Leighton. 01:12:05.570 --> 01:12:07.550 1983 entwickelt worden von ihm. 01:12:08.810 --> 01:12:11.550 Der Tom Leighton ist übrigens derjenige, der die Verfahren entwickelt 01:12:11.550 --> 01:12:15.350 hat, die bei dem Akamai zugrunde liegen. 01:12:15.510 --> 01:12:18.870 Wenn Sie mal sich mit Internet beschäftigt haben, wissen Sie, was 01:12:18.870 --> 01:12:19.750 Akamai ist. 01:12:19.870 --> 01:12:28.110 Akamai ist ein Verfahren, um Inhalte im Web sehr effizient zum 01:12:28.110 --> 01:12:29.570 Anwender zu bringen. 01:12:29.570 --> 01:12:35.230 Indem man an den Rändern des Internets sehr viele Server hat, die 01:12:35.230 --> 01:12:41.650 jeweils die aktuellen Inhalte von dem Originalserver zur Verfügung 01:12:41.650 --> 01:12:42.310 stellen können. 01:12:42.850 --> 01:12:45.650 Der ist Milliardär mittlerweile durch diese Idee, die er damals hatte. 01:12:46.130 --> 01:12:49.730 Also ein theoretischer Informatiker, der eine gute Idee hatte, die man 01:12:49.730 --> 01:12:51.490 im Internet hervorragend einsetzen konnte. 01:12:52.050 --> 01:12:55.830 Und hat dann die Firma Akamai gegründet und dabei sehr viel Geld 01:12:55.830 --> 01:12:56.190 verdient. 01:12:57.150 --> 01:13:00.110 Dieses ist nun ein Verfahren, mit dem er nicht viel Geld verdienen 01:13:00.110 --> 01:13:03.170 konnte, aber trotzdem eine interessante Struktur. 01:13:04.070 --> 01:13:09.530 Und hier haben wir jetzt ein zweidimensionales Feld, ein n-Kreuz-n 01:13:09.530 --> 01:13:09.950 -Feld. 01:13:10.530 --> 01:13:14.250 Und wir wollen zwei Folgen der Länge n sortieren. 01:13:14.350 --> 01:13:17.990 Also n Quadratprozessoren, Folgen der Länge n. 01:13:17.990 --> 01:13:24.870 Sie erinnern sich, wir hatten mal bei dem, als wir die Bestimmung des 01:13:24.870 --> 01:13:29.770 Minimums gemacht haben, sagten wir, wir machen n Quadratvergleiche 01:13:29.770 --> 01:13:30.250 gleichzeitig. 01:13:30.870 --> 01:13:31.970 Das können Sie hier auch machen. 01:13:32.070 --> 01:13:35.230 Sie können natürlich auch sortieren mit n Quadratvergleichen und 01:13:35.230 --> 01:13:39.590 bekommen dann Informationen über die jeweiligen Ranganordnungen der 01:13:39.590 --> 01:13:40.190 Elemente. 01:13:40.630 --> 01:13:43.350 Aber müssen das natürlich geeignet auswerten können. 01:13:43.470 --> 01:13:45.350 Genau das liefert diese Struktur. 01:13:46.350 --> 01:13:50.330 So, ich verteile zunächst mal die zu sortierende Folge der Länge n 01:13:50.330 --> 01:13:54.490 über die Zeilen und Spaltenbäume des Mesh of Trees an die Prozessoren. 01:13:55.030 --> 01:13:59.390 Das heißt, das Element x1 wandert also hier hin. 01:13:59.470 --> 01:14:00.550 Da habe ich also Element 1. 01:14:02.650 --> 01:14:07.190 Über den Spaltenbaum wandert das hier also überall runter. 01:14:08.090 --> 01:14:12.170 Und über den Zeilenbaum verteile ich die auch. 01:14:13.430 --> 01:14:16.110 Da habe ich also das Element 1 nochmal. 01:14:17.150 --> 01:14:19.870 Und zwar auch in allen Elementen der ersten Zeile. 01:14:19.970 --> 01:14:27.550 Und entsprechend habe ich dann hier das Element 2 und da das Element 3 01:14:27.550 --> 01:14:28.970 und da das Element 4. 01:14:28.970 --> 01:14:36.970 Und entsprechend habe ich also hier zum Beispiel das Element 3 und da 01:14:36.970 --> 01:14:38.910 das Element 2 und so weiter. 01:14:40.270 --> 01:14:46.070 Das heißt, ich erzeuge alle Paarungen von Elementen aus dieser Folge, 01:14:46.290 --> 01:14:48.010 die hier vier Elemente hat. 01:14:49.310 --> 01:14:51.630 Jetzt habe ich in jedem Prozessor zwei Elemente. 01:14:51.810 --> 01:14:54.770 Eines aus dem Spaltenbaum, eines aus dem Zeilenbaum. 01:14:56.630 --> 01:15:00.190 Jetzt vergleiche ich die Daten in den Prozessoren. 01:15:00.870 --> 01:15:04.570 Nehmen wir mal an, wir haben hier Zahlen drin stehen. 01:15:04.690 --> 01:15:07.310 3, 0, 2, 1. 01:15:09.150 --> 01:15:11.890 Jetzt vergleiche ich die Daten in den Prozessoren. 01:15:14.490 --> 01:15:20.190 Und zwar schreibe ich als Ergebnis eine 1 rein in den Prozessor, wenn 01:15:20.190 --> 01:15:21.450 a größer b ist. 01:15:21.450 --> 01:15:24.750 Wenn also das Element aus dem Spaltenbaum größer ist als das Element 01:15:24.750 --> 01:15:25.770 aus dem Zeilenbaum. 01:15:28.170 --> 01:15:34.910 In dem Fall hätte ich das erste Element 3, da würde ich also eine 0 im 01:15:34.910 --> 01:15:35.950 Prinzip reinschreiben. 01:15:36.670 --> 01:15:39.270 Hier würde ich das mit dem zweiten Element vergleichen, da würde ich 01:15:39.270 --> 01:15:40.510 eine 1 reinschreiben. 01:15:41.190 --> 01:15:44.070 Ich würde es mit dem dritten Element vergleichen, da würde ich eine 1 01:15:44.070 --> 01:15:44.730 reinschreiben. 01:15:44.830 --> 01:15:47.150 Mit dem vierten Element vergleiche ich auch eine 1 reinschreiben. 01:15:52.350 --> 01:15:56.630 Also, wenn der Wert aus dem Spaltenbaum größer ist als der Wert aus 01:15:56.630 --> 01:15:59.050 dem Zeilenbaum, schreibe ich eine 1 rein, ansonsten eine 0. 01:16:01.070 --> 01:16:05.430 Jetzt nutze ich die Spaltenbäume fürs Rechnen. 01:16:06.110 --> 01:16:10.870 Ich sende die Ergebnisse, also diese Nullen und Einsen, zu den 01:16:10.870 --> 01:16:15.850 Spaltenbaumwurzeln und addiere sie dabei. 01:16:15.850 --> 01:16:21.750 Das heißt, ich nehme die beiden hier zusammen, 1 plus 1 macht 2, da 01:16:21.750 --> 01:16:22.710 kommt eine 1 dazu. 01:16:22.830 --> 01:16:28.170 Hier oben an der Spaltenbaumwurzel würde ich also eine 3 berechnen. 01:16:29.170 --> 01:16:30.630 Die drei Einsen sind aufaddiert. 01:16:31.770 --> 01:16:37.770 An der Spaltenbaumwurzel für dieses zweite Element, x2, würde hier 01:16:37.770 --> 01:16:39.390 natürlich eine 0 stehen. 01:16:40.730 --> 01:16:45.950 Und hier würde entsprechend eine 1 stehen und da würde eine 2 stehen. 01:16:47.810 --> 01:16:51.570 Das ist natürlich klar, ich habe es gerade so gemacht. 01:16:51.650 --> 01:16:55.150 Das sind also jetzt die Spaltenbaumwurzeln, also hier in diesen 01:16:55.150 --> 01:16:57.730 Elementen, da stehen jeweils die Summen drin. 01:16:58.730 --> 01:17:08.810 Und diese Summen sind genau der Rang dieses Spaltenbaumelements in der 01:17:08.810 --> 01:17:10.050 zu sortierenden Folge. 01:17:10.430 --> 01:17:20.370 Weil ich ja gezählt habe, wie oft war dieses Element größer als ein 01:17:20.370 --> 01:17:21.070 anderes Element. 01:17:21.070 --> 01:17:27.450 Das heißt, das Element x1 hat den Rang 3, es ist an dritter Stelle, 01:17:27.970 --> 01:17:30.830 also nicht an dritter, an vierter Stelle, ich fange von 0 an. 01:17:32.590 --> 01:17:38.250 Der Rang des Datums xi steht in Wurzel dieses Spaltenbaums und der 01:17:38.250 --> 01:17:43.510 kleinste Rang ist 0, also ich zähle von 0 bis n-1. 01:17:43.510 --> 01:17:50.110 Und jetzt nehme ich die binäre Darstellung des Ranges, um den 01:17:50.110 --> 01:17:52.970 rangrichtigen Weg durch den Spaltenbaum zu einem Blatt zu gehen. 01:17:53.030 --> 01:17:53.650 Was heißt das? 01:17:54.610 --> 01:18:03.210 Ich nehme für 0, also meine Darstellungen sind 0,0, 0,1, 1,0 und 1,1, 01:18:03.310 --> 01:18:05.910 das sind die möglichen Rangwerte. 01:18:06.590 --> 01:18:12.610 Wenn ich also 0,0 habe, 0,0 heißt hier zum Beispiel, ich muss zweimal 01:18:12.610 --> 01:18:17.030 nach rechts gehen, rechts, rechts, ich lande dort, da kommt die 0 hin. 01:18:18.810 --> 01:18:20.870 Dieser Prozessor wird im Prinzip aktiviert. 01:18:21.310 --> 01:18:24.570 Dieses Element hier, da stand zweimal eine 1, da laufe ich also hier 01:18:24.570 --> 01:18:25.110 unten hin. 01:18:27.110 --> 01:18:31.630 Und entsprechend werde ich bei dem Element an diese Stelle kommen, bei 01:18:31.630 --> 01:18:35.030 der 2 habe ich 1,0, einmal nach links, einmal nach rechts, ich bin da 01:18:35.030 --> 01:18:35.550 gelandet. 01:18:35.910 --> 01:18:42.270 Bei dem letzten hier, bei diesem x4, da habe ich 0,1 stehen, einmal 01:18:42.270 --> 01:18:44.850 nach rechts, einmal nach links und ich lande dort. 01:18:46.190 --> 01:18:54.710 Und anschließend gebe ich die Werte von den erreichten Prozessoren aus 01:18:54.710 --> 01:18:56.130 über die Spaltenbäume aus. 01:18:57.130 --> 01:19:02.130 Das heißt, ich gebe jetzt über den ersten Spaltenbaum oben das Element 01:19:02.130 --> 01:19:11.010 x2 aus, über den zweiten Zeilenbaum das Element x4, über den dritten 01:19:11.010 --> 01:19:18.130 das Element x3 und über den untersten Zeilenbaum das Element x1. 01:19:19.850 --> 01:19:25.590 Das heißt, ich habe diese Baumstruktur ausgenutzt, um einerseits den 01:19:25.590 --> 01:19:30.990 Rang auszurechnen und andererseits die richtige Ausgabe zu machen. 01:19:31.130 --> 01:19:33.850 Also auch das richtig zu adressieren, ein Element auszuwählen, das 01:19:33.850 --> 01:19:38.070 gerade rangrichtig ist und dann entsprechend die Ausgabe zu machen. 01:19:38.570 --> 01:19:41.370 Auf die Art und Weise kann man also auch sortieren. 01:19:41.810 --> 01:19:44.190 Das Sie nur sehen, was für ein schönes Problem das Sortieren ist, was 01:19:44.190 --> 01:19:45.990 man da alles für Verfahren sich überlegen kann. 01:19:46.570 --> 01:19:51.170 Und hier ist natürlich so, wenn wir das analysieren, das sind 01:19:51.170 --> 01:19:53.830 insgesamt 4 log n plus 1 Takte. 01:19:54.470 --> 01:19:59.090 Wir hatten log n Takte, um zu Anfang zu verteilen, alles auf die 01:19:59.090 --> 01:20:01.730 Prozessoren zu verteilen über die Spalten- und Zeilenbäume. 01:20:01.810 --> 01:20:04.210 Das dauert log n Takte, um durch den Baum durchzulaufen. 01:20:05.690 --> 01:20:10.030 Ein Takt, um zu vergleichen, da jeweils die 0 und 1 reinzuschreiben. 01:20:10.030 --> 01:20:13.310 Dann log n Takte, um den Rang zu berechnen. 01:20:14.290 --> 01:20:18.470 Nochmal log n Takte, um mit der Darstellung des Ranges 01:20:18.470 --> 01:20:22.490 durchzunavigieren und den entsprechenden Prozessor anzusprechen. 01:20:23.350 --> 01:20:27.950 Und dann von dem angesprochenen Prozessor aus über den Zeilenbaum nach 01:20:27.950 --> 01:20:30.110 etwas auszugeben, dauert wieder log n Takte. 01:20:30.630 --> 01:20:33.770 Damit habe ich also 4 log n plus 1 Takte, habe also in log n Zeit 01:20:33.770 --> 01:20:39.130 damit sortiert, aber mit n² Prozessoren, was natürlich schlecht ist. 01:20:40.030 --> 01:20:45.070 Also ich habe sogar 3 n² minus 2 n Prozessoren, wenn ich die Knoten in 01:20:45.070 --> 01:20:47.030 den Spalten- und Zeilenbäumen mitrechne. 01:20:47.570 --> 01:20:49.250 Da habe ich so viele Prozessoren. 01:20:50.170 --> 01:20:51.130 Effizienz ist sehr schlecht. 01:20:51.230 --> 01:20:53.430 Ich habe hier nochmal das Cold Sort aufgeführt, was ich hier nicht 01:20:53.430 --> 01:20:55.030 behandelt habe. 01:20:55.170 --> 01:20:58.530 Da kann man tatsächlich mit großen Größenordnungen n Prozessoren 01:20:58.530 --> 01:20:59.030 auskommen. 01:20:59.030 --> 01:21:04.870 Aber ich wollte Ihnen gerne diese Struktur Mesh of Trees nochmal 01:21:04.870 --> 01:21:08.070 dargestellt haben, dass Sie einfach sehen, was für 01:21:08.070 --> 01:21:13.350 Verbindungsstrukturen man sich so überlegt für parallele Rechner. 01:21:14.550 --> 01:21:17.630 Diese Spalten- und Zeilenbäume können Sie auffassen als eine 01:21:17.630 --> 01:21:20.230 Möglichkeit, mit dem Concurrent Read, Concurrent Write 01:21:20.230 --> 01:21:21.030 zurechtzukommen. 01:21:21.030 --> 01:21:24.570 Bei Concurrent Read, Concurrent Write haben Sie Lese- und 01:21:24.570 --> 01:21:25.370 Schreibkonflikte. 01:21:25.850 --> 01:21:29.590 Die kann man auflösen, indem man das über eine Baumstruktur macht. 01:21:30.110 --> 01:21:33.990 Und dann ist man von vornherein bei solchen Bäumen. 01:21:34.110 --> 01:21:35.770 Dann hat man diese Spalten- und Zeilenbäume. 01:21:38.730 --> 01:21:42.210 Man hat also für Mesh of Trees eine Vielfalt von Algorithmen. 01:21:42.750 --> 01:21:45.690 Diese Struktur ist also für viele verschiedene Probleme tatsächlich 01:21:45.690 --> 01:21:46.470 betrachtet worden. 01:21:47.670 --> 01:21:52.050 So, jetzt machen wir noch ganz schnell eine untere Schranke für die 01:21:52.050 --> 01:21:53.790 Anzahl der Vergleiche beim Sortieren. 01:21:54.790 --> 01:21:56.050 Das ist hier nur eine Folie. 01:21:56.210 --> 01:21:58.590 Eigentlich bräuchte man mehr, aber ich will es trotzdem etwas 01:21:58.590 --> 01:21:59.990 einfacher machen. 01:22:00.910 --> 01:22:04.610 Die Frage ist, ob man mit weniger Vergleichen als bei Merge Sort 01:22:04.610 --> 01:22:05.430 auskommen kann. 01:22:06.630 --> 01:22:08.710 Jetzt zurück zum allgemeinen Problem. 01:22:08.950 --> 01:22:10.570 Da hatten wir N-Log-N-Vergleiche. 01:22:10.570 --> 01:22:13.450 Jetzt bei den parallelen Verfahren haben wir Schritte betrachtet. 01:22:16.130 --> 01:22:21.430 Und jetzt gucken wir uns eine untere Schranke für Sortieren mit 01:22:21.430 --> 01:22:22.830 allgemeinen Sortierverfahren an. 01:22:22.870 --> 01:22:26.310 Das heißt, wir wissen nur etwas über die Größenverhältnisse, nichts 01:22:26.310 --> 01:22:27.470 über die konkreten Werte. 01:22:28.590 --> 01:22:31.930 Und wir haben dafür ja im Prinzip Entscheidungsbäume verwendet. 01:22:32.830 --> 01:22:36.230 Und wenn die Elemente alle verschieden sind, dann wissen wir, dass es 01:22:36.230 --> 01:22:39.190 in Fakultät verschiedene Anordnungen geben kann. 01:22:39.190 --> 01:22:45.350 Aus einer eingegebenen Folge der Länge N, wenn wir sie sortieren, je 01:22:45.350 --> 01:22:49.630 nachdem, was eingegeben wurde, haben sie in Fakultät verschiedene 01:22:49.630 --> 01:22:53.690 Permutationen, die vorkommen können, also N-Fakultät Blätter. 01:22:54.210 --> 01:23:01.490 Wenn Sie einen Baum haben, der hier unten gerade N-Fakultät Blätter 01:23:01.490 --> 01:23:08.430 hat, dann wissen Sie, die Höhe dieses Baumes ist dann Log von N 01:23:08.430 --> 01:23:09.710 -Fakultät. 01:23:10.790 --> 01:23:15.410 Log von N-Fakultät überlegt man sich sehr einfach. 01:23:16.930 --> 01:23:18.690 Ist gerade die Größe N Log N? 01:23:18.750 --> 01:23:20.270 Das können Sie sich wirklich sehr einfach überlegen. 01:23:21.050 --> 01:23:24.370 Sie wissen, was N-Fakultät ist, Produkt aller Zahlen von 1 bis N. 01:23:25.070 --> 01:23:27.270 N-Fakultät ist sicherlich kleiner als N hoch N. 01:23:28.210 --> 01:23:31.450 Und wenn Sie Log von N hoch N nehmen, ist das N mal Log N. 01:23:32.110 --> 01:23:33.510 Dann sind Sie bei N mal Log N. 01:23:34.790 --> 01:23:40.230 Und wenn Sie sagen, ich nehme nur die eine Hälfte, ich gehe nur bis N 01:23:40.230 --> 01:23:43.710 halber und mache einfach nur N halber und gehe dann nicht alle Zahlen 01:23:43.710 --> 01:23:44.030 dahin. 01:23:44.490 --> 01:23:50.210 Also N-Fakultät ist sicherlich größer als N halber hoch N halber. 01:23:52.470 --> 01:23:54.190 Und das ist aber auch N Log N. 01:23:54.190 --> 01:23:57.570 Also wenn Sie da von Log nehmen, Log von N halber hoch N halber, ist 01:23:57.570 --> 01:23:58.450 das auch N Log N. 01:23:59.290 --> 01:24:01.450 Das ist eine ganz grobe Abschätzung, ganz einfach. 01:24:02.290 --> 01:24:04.750 Und wenn Sie es genauer wissen wollen, dann müssen Sie sich die 01:24:04.750 --> 01:24:05.830 Sterling -Zahl angucken. 01:24:06.430 --> 01:24:09.250 Man kann das also sehr genau abschätzen, das ist aber dann etwas 01:24:09.250 --> 01:24:09.830 aufwendiger. 01:24:11.310 --> 01:24:15.550 Aber jetzt sage ich hier, die maximale und die mittlere Weglänge sind 01:24:15.550 --> 01:24:20.010 in jedem Entscheidungsbaum von Satirverfahren in Omega von N Log N. 01:24:20.010 --> 01:24:25.790 Das heißt, im schlechtesten Fall braucht ein Sortierverfahren 01:24:25.790 --> 01:24:29.870 mindestens Zeit N Log N. 01:24:30.510 --> 01:24:36.050 Das heißt, die maximale Weglänge wird immer mindestens N Log N als 01:24:36.050 --> 01:24:37.130 Weglänge haben. 01:24:37.450 --> 01:24:39.330 Schauen wir uns die mittlere Weglänge an. 01:24:39.850 --> 01:24:43.070 Offensichtlich, hier hätten wir eine ganz gleichmäßige Verteilung der 01:24:43.070 --> 01:24:43.530 Weglängen. 01:24:44.430 --> 01:24:47.730 Und der Beweis für diesen Satz läuft so, dass man sich überlegt, ich 01:24:47.730 --> 01:24:52.410 hätte einen Baum, eine Verteilung dieser N-Fakultät Blätter, sodass 01:24:52.410 --> 01:24:59.590 die Distanz, wenn ich hier die verschiedenen Wege betrachte, könnten 01:24:59.590 --> 01:25:00.850 unterschiedlich lang sein. 01:25:01.450 --> 01:25:06.530 Und wenn die Distanz der Pfadlängen größer als 2 ist, dann kann man 01:25:06.530 --> 01:25:08.510 zeigen, kann man sie um 1 reduzieren. 01:25:10.410 --> 01:25:12.910 Und das Verfahren wird immer noch richtig sein. 01:25:12.910 --> 01:25:20.370 Und wenn die Distanz größer als 1 ist, wenn ich es dann immer um 01:25:20.370 --> 01:25:24.830 mindestens 1 reduzieren kann, dann heißt das, dass ich einen solchen 01:25:24.830 --> 01:25:27.370 Baum vielleicht mit einer Stufe brauche. 01:25:27.730 --> 01:25:30.570 Aber das ist ein Baum, der auf jeden Fall die mittlere Weglänge 01:25:30.570 --> 01:25:31.270 optimiert. 01:25:32.030 --> 01:25:36.870 Und damit ist das auch eine untere Schranke für die maximale Weglänge. 01:25:37.430 --> 01:25:38.750 Die kann aber größer sein. 01:25:39.230 --> 01:25:43.150 Also N Log N ist eine einfache untere Schranke für die Anzahl der 01:25:43.150 --> 01:25:44.950 Vergleiche im Mittel- und im schlechtesten Fall. 01:25:45.890 --> 01:25:49.670 Und wenn Sie mir das erlauben, dann zeige ich Ihnen jetzt noch zum 01:25:49.670 --> 01:25:55.370 bisschen überraschen ein spezielles Sortierverfahren, das ich nur ganz 01:25:55.370 --> 01:25:56.330 kurz hier darstelle. 01:25:56.910 --> 01:25:57.390 Binsort. 01:25:57.630 --> 01:25:59.790 Sie stellen eine Reihe von Dosen auf. 01:26:00.930 --> 01:26:02.930 Sie wollen meinetwegen Zahlen sortieren. 01:26:03.130 --> 01:26:06.710 Sie haben eine ewig lange Folge, sind aber nur Zahlen von 1 bis 4 01:26:06.710 --> 01:26:06.950 drin. 01:26:07.690 --> 01:26:13.890 Dann werfen Sie alle 1 hier rein, alle 2 da rein, alle 3 da rein. 01:26:16.230 --> 01:26:19.810 Dann haben Sie die 1, 2, 3, 4 haben Sie jetzt in diesen Dosen drin 01:26:19.810 --> 01:26:23.970 stehen und anschließend holen Sie die 1 raus, die 2, die 3, die 4 und 01:26:23.970 --> 01:26:24.610 Sie haben sortiert. 01:26:25.750 --> 01:26:29.530 Sie schauen die einzigen einzelnen Elemente nur an, führen keinen 01:26:29.530 --> 01:26:33.330 einzigen Vergleich aus und können in linearer Zeit sortieren. 01:26:35.050 --> 01:26:37.870 Wir haben gerade gesehen, wir brauchen mindestens N log N, also untere 01:26:37.870 --> 01:26:39.430 Schranke für allgemeine Sortierverfahren. 01:26:40.070 --> 01:26:44.090 Offensichtlich, wenn man mehr weiß, wenn man weiß, welche Elemente man 01:26:44.090 --> 01:26:46.650 sortieren muss, kann man auch in linearer Zeit sortieren. 01:26:47.490 --> 01:26:49.970 Das wollte ich nur noch kurz am Ende erwähnen. 01:26:50.490 --> 01:26:53.910 Da machen wir nächstes Mal dann noch kurz weiter und kommen dann zum 01:26:53.910 --> 01:26:54.650 nächsten Kapitel. 01:26:55.210 --> 01:26:58.290 Ne, nicht nächsten Kapitel, sondern nächsten Thema in diesem Kapitel, 01:26:58.750 --> 01:26:59.730 nämlich Suchverfahren. 01:27:00.350 --> 01:27:01.750 Okay, vielen Dank für die Aufmerksamkeit.