So, schönen Tag.
Ich begrüße Sie zur Fortsetzung der Vorlesung Effiziente Algorithmen.
Es sind, wie üblich, nicht sehr viele Studenten da, aber es waren
einige.
Ich freue mich immer, Sie zu sehen, das habe ich schon oft gesagt.
Ich habe vorhin gesagt, dass ich mir eigentlich nicht dazu führen
sollte, dass nur noch sehr wenige kommen.
Weil ich denke, dass ich schon so im direkten Ansehen eigentlich
anders Sachen vermitteln kann.
Aber das ist etwas, was Sie selbst entscheiden müssen.
Letztes Mal haben wir uns beschäftigt mit den Sortierverfahren und
waren also schon deutlich weiter als hier.
Das ist natürlich jetzt die erste Folie.
Wir haben uns einiges angeguckt.
Wir hatten, nachdem wir ja die einfachen Verfahren, was wir davor
schon angeguckt hatten, da hatten wir uns noch mit Bubble Sort
beschäftigt, mit der Korrektheit von Bubble Sort, beziehungsweise von
Transposition Sort natürlich, der parallelen Variante.
Ich hatte Sie auch darauf hingewiesen, dass das für bestimmte
parallele Modelle ein optimales Verfahren sein kann.
Wir hatten dann Quicksort betrachtet, ein Verfahren, das Sie schon
lange kennen, und hatten gesehen, wie hier die Zeitkomplexität ist.
Hätte Ihnen dann auch das mittlere Verhalten kurz dargestellt, wie man
das nachweisen kann, dass wir hier halt auch end-of-end kommen,
weswegen der Name Quicksort auch wirklich berechtigt ist.
Und hatten dann uns mit Merge Sort beschäftigt, als eigentlich ein
Muster für eine ganze Vielzahl von Algorithmen, insbesondere wenn man
sie parallel ausführt, weil es dann eben darum geht, wie kann ich das
Mergen, also das Verschmelzen von zwei Listen eigentlich machen.
Das Schöne ist, dass sich eben hier viele mit dem ganz nach der Weide
Konker -Ansatz, und zwar nach einer ganz strengen Anwendung, immer
schön hälftig aufteilen.
Wie man viele Teilprobleme parallel bearbeiten kann, wie man diese
Merge -Probleme bearbeiten kann.
Wir hatten gesehen, dass man das mit diesem Odd-Even Merge machen
kann, wo man die Elemente an den geraden und ungeraden Positionen der
beiden zu verschmelzenden Teilfolgen sich hernimmt und dann
entsprechend iterativ weiter bearbeitet und am Ende nur noch eine
kleine Zeile von Vergleichen ausführt, was dann rekursiv dazu führt,
dass wir dieses Bild haben von Vergleicherstrukturen für so ein Odd
-Even Merge und das halt mit Log-N-Stufen, in denen jeweils eine ganze
Reihe Vergleiche parallel ausgeführt werden.
Ich hatte Ihnen insbesondere letztes Mal dann auch das 0-1-Prinzip
vorgestellt.
Wesentliche Technik, um sich von der Korrektheit von Algorithmen zu
überzeugen, bei denen es also um Sortieren geht.
Und das ist halt eine ganz entscheidende Vereinfachung des Aufwandes,
um sich davon zu überzeugen, dass ein Verfahren richtig ist.
Man kann übrigens sogar noch die Anzahl der Folgen, die man betrachten
muss, reduzieren, weil sich einige dieser 0-1-Folgen überdecken.
Das heißt, wenn ich mir dann bestimmte 0-1-Folgen angucke, kann es
sein, dass damit schon eine gewisse Menge von anderen 0-1-Folgen
abgedeckt ist.
Das ist eine ganz interessante Tatsache.
Also man kann das sogar um den Faktor Wurzeln noch reduzieren, wenn
man sich das genauer anguckt.
Also das Wesentliche ist, wir können uns darauf beschränken, die 0-1
-Folgen zu betrachten.
Das hatte ich an hier gemacht, auch bei Tonicsort.
Wobei bei Tonicsort zunächst einmal ein Sortierverfahren ist, auf
schon ziemlich stark vorsortierten Folgen, aber eben nicht
vollständig, sondern dieses bitonische Aufsteigen und Absteigen zügig
verschoben.
Wir hatten gesehen, dass man das dann einsetzen kann, nachdem wir uns
von der Korrektheit überzeugt hatten, um zwei Folgen zu mischen, bei
denen man einfach das bei Tonicsort verwendet und nur die erste Stufe
logisch etwas verändert, indem man die rechte Teilfolge einfach als
vertauschte oder gespiegelte Folge betrachtet.
Und wenn man die halt gespiegelt betrachtet, hätte man eine bitonische
Folge.
Das heißt, das bei Tonicsort kann hier für das Mischen von zwei Folgen
eingesetzt werden.
Und so kommt man dann auf das bei Tonicsort, das war hier am Ende bei
Tonicsort, dann auch Größenordnung log²n, mit etwas mehr Vergleichen
als bei dem odd-even-merge.
Ich wollte Ihnen eigentlich dadurch am Wesentlichen zeigen, welche
verschiedenen Ansätze das gibt.
Dass es also viele Varianten gibt für parallele Sortierverfahren.
Was man hier auf jeden Fall sieht, ist, dass das hier deutlich
systematischer, das ist einfach ein Muster, das sich immer wiederholt.
Diese Vergleiche gibt man bei diesem Bild hier noch deutlicher, dass
man eben hier zunächst mal so eine Stufe hat, wo man Elemente mit
einem Abstand in Halbe miteinander vergleicht, dann Abstand in
Viertel, in Achtel und so weiter.
Also immer die Abstände der Elemente, die verglichen werden, geht um
die Hälfte runter.
Und man hat alle diese Elemente verglichen.
Anders als bei dem odd-even-merge, da war die Anzahl der Vergleiche
etwas reduziert.
Aber das sah nicht ganz so hübsch systematisch aus, wie bei dem, was
wir bei Tonicsort machen.
Und das nächste ist dann diese Folie gewesen, das war die letzte, mit
der ich mich länger beschäftigt habe, letztes Mal das Sortieren im
zweidimensionalen Feld.
Und hier haben wir uns zunächst mal überlegt, wenn wir zweidimensional
sortieren, da müssen wir uns überlegen, wie wollen wir eigentlich die
Elemente anordnen.
Dazu muss man sich aber überlegen, was ist eine sinnvolle
Sortierreihenfolge.
Man kann sich irgendeine Reihenfolge hernehmen, muss dann dafür
sorgen, dass anschließend die Elemente auch wirklich in dieser
Anordnung aufsteigend sortiert sind.
Und das, was man eben standardmäßig macht, ist entweder zeilenweise
oder zeilenweise in Schlangenlinien.
Und wir hatten dann überlegt, dass für diese beiden Fälle man eine
sehr einfache untere Schranke bekommt, indem man einfach annimmt, dass
die Elemente an den beiden Ecken miteinander vertauscht werden müssen,
damit die richtige Größenreihenfolge hergestellt ist.
Und dann hat man halt sofort eine untere Schranke von 2n-2, wobei n
die Kantenlänge des zweidimensionalen Feldes ist.
Also das ist eine ganz einfache untere Schranke.
Und jetzt zeige ich Ihnen eben dieses Verfahren LSO3-Sort, das ich
letztes Mal schon ganz kurz einmal gezeigt habe.
Ein Verfahren, das systematisch Folgen sortiert, im Prinzip wieder
nach dem Merge-Sort-Prinzip.
Allerdings hier nicht in zweifaches Merge, sondern ein Vierfach-Merge.
Ich habe also vier Quadranten, die jetzt jeweils vorsortiert sind in
Schlangenlinien, und die sollen verschmolzen werden zu einem in
Schlangenlinien sortierten Feld.
Also Annahme ist, wir müssen in Schlangenlinien sortieren, machen das
rekursiv, und nehmen einfach an, wir haben schon die vier Quadranten
soweit sortiert.
Nun ist die Frage, wie kann man ein Merge machen mit vier Teilfolgen
auf so einem zweidimensionalen Feld.
Und dazu haben wir uns halt ein sehr schönes und ein sehr einfaches
Verfahren ausgedacht.
Es ist nicht das optimale Verfahren, um auf zweidimensionalen Feldern
zu sortieren.
Ich werde darauf später nochmal ganz kurz eingehen, was das optimale
Verfahren ist.
Aber es ist ein sehr einfach strukturiertes und trotzdem auch recht
schnelles Verfahren.
Also was machen wir hier?
Wir fangen an mit einem Perfect Shuffle in jeder Zeile des Feldes.
Wenn man ein Perfect Shuffle macht, wissen Sie, in jeder Zeile des
Feldes heißt das, ich nehme also hier die Elemente von der linken und
der rechten Hälfte her, und habe dann halt hier jeweils im Prinzip ein
Element von links, rechts, links, rechts und so weiter, links, rechts.
Die sind einfach dann schön ineinander verschoben, Sie wissen, ein
perfektes Mischen, die werden ineinander verschränkt.
Jetzt habe ich also nebeneinander immer Elemente aus der linken und
der rechten Hälfte.
Und das heißt, wenn ich mir anschaue, das was in so zwei nebeneinander
liegenden Zeilen drin ist, dann sehen wir, das waren ja Elemente aus
den vier Quadranten.
Das ist eine Spalte aus dem linken Quadranten und eine Spalte aus dem
rechten Quadranten.
Das ist einfach die Idee, wir machen also im Prinzip, ist das so schon
mal, wir legen jetzt schon mal Elemente nebeneinander, aus jeweils
linken und rechten Quadranten, verschmelzen also das, eigentlich ist
das jetzt so eine Vorbereitung für ein Zweifachmört.
Aber wir machen das natürlich, wir haben jetzt eine ganze Spalte,
eigentlich jetzt aus den vier Quadranten Elemente drin liegen.
Und die Idee ist, dass wir das jetzt ausnutzen und sortieren jede
Doppelspalte, in der also Elemente aus den vier Quadranten drin sind,
in Schlangenlinien von oben nach unten aufsteigen.
Das ist, wir wissen, wie man das machen kann, zum Beispiel mit OETS,
man kann irgendein Verfahren nehmen, OETS ist ein Verfahren, wissen
wir, der arbeitet mit lokalen Operationen, das kann man hier
sicherlich anwenden.
Das heißt, die Operationen, die ich machen müsste, wären so, dass ich,
also ich mache mal jetzt hier normal das nebeneinander ein, ich müsste
also Vergleiche machen, die abwechselnd von links nach rechts laufen,
das wäre ein Schritt, das wäre meinetwegen, wenn wir sagen, das ist
der OTT-Schritt, das erste Paar, 1, 2, die werden miteinander
verglichen.
Und in dem EVEN-Schritt würde ich also im Prinzip da einen Vergleich
haben, da einen Vergleich, da einen Vergleich, da einen Vergleich.
Das ist jetzt einfach so in den nebeneinander liegenden Doppelspalten
dargestellt, was in zwei aufeinanderfolgenden Schritten passiert bei
dem OETS, wenn man das so auf Doppelspalten ausführt.
Also das heißt, wir würden dort, wenn wir OETS machen, abwechselnd
Vergleiche machen in den jeweils nebeneinander liegenden Elementen in
diesen Zeilen, und zwar einmal links nach rechts, also das Maximum
nach rechts und in der Zeile drunter Maximum nach links.
Schön Schlangenlinienart, alternierend aufsteigen, absteigen und dann
eben nach unten, jeweils am rechten und am linken Rand.
Das ist also einfach das OETS-Prinzip übertragen auf dieses Sortieren
in einer Schlangenlinie.
Und ich habe also einfach diese Reihenfolge, die ich dort haben
möchte, diese Schlangenlinienreihenfolge, die guckt man sich an, und
wie mache ich da auch OETS, und dann kommt man auf genau diese
Struktur in den beiden, also dass man so eine Schlangenlinie sortiert.
Und das Maximum soll dann eben da so ein Pfeil jeweils stehen, damit
klar ist, das Aufsteigen sortiert.
Jetzt haben wir etwas erreicht, dass diese Doppelspalten jeweils
sortiert sind.
Vorher waren sogar diese vier Quadranten schon sortiert.
Jetzt sind Doppelspalten sortiert.
Und jetzt kommt etwas, was so aussieht wie Magic, zwei Endschritte von
OETS.
xn ist die Kantenlänge meines Feldes.
Ich wende zwei Endschritte von OETS ein.
Zwei Endschritte reichen aus, um eine Folge der Länge 2n zu sortieren,
vollständig.
Hier habe ich aber eine Folge der Länge n².
Ich behaupte, mit 2n Schritten kann ich das, was jetzt entstanden ist
nach diesem Sortieren in den Doppelspalten, in den Schlangenlinien,
dann ist das Ganze, was rauskommt, vollständig sortiert.
Das ist zunächst mal nicht intuitiv klar.
Das heißt, ich gehe davon aus, der Sortiertheitsgrad, den ich habe,
der ist schon so groß, dass die maximalen Abstände zwischen nicht am
richtigen Platz befindlichen Elementen 2n sind.
Denn dann kann ich das in 2n Schritten tatsächlich hinbekommen.
Und das ist zuerst mal eine mutige Behauptung.
Wir werden es später sehen, dass man das mit dem 0-1-Prinzip sehr
einfach beweisen kann.
Aber das zunächst mal zu diesem Verfahren.
Drei einfache Schritte.
Perfect Shuffle.
Wissen Sie, wie das geht?
Einfach ein Umordnen der Elemente.
Das zweite, Doppelspalten sortieren, einfache Vergleiche.
Links, rechts, oben, unten.
Und schließlich nochmal wieder einfache Vergleiche.
Aber das eine Mal auf die Doppelspalten, das andere Mal auf der
gesamten Matrix als Schlangenlinie.
Also OITS auf diesem linearen Feld, das ihr so sich durch unser Feld
hindurchschlängelt.
Sodass wir am Ende dann tatsächlich ein vollständig sortiertes Feld
haben.
Ja, das ist also jetzt unser Verfahren.
Gucken wir uns erst mal an, was für einen Zeitaufwand das hat.
Wenn wir uns jetzt überlegen, wie viel Zeit brauchen wir.
Der erste Schritt, Perfect Shuffle.
Das hatten wir bei dem Odd-Even-Merge so als, naja, das braucht ja
eigentlich gar keine Zeit.
Wenn ich das auf einem zweidimensionalen Feld mache, braucht das schon
Zeit.
Ich arbeite nur mit lokalen Operationen.
Ich habe ja auf dem Feld nur hier meine direkten
Nachbarschaftsbeziehungen.
Also nur jeweils verbunden mit den vier direkten Nachbarn.
Da kann ich natürlich nicht beliebig die Elemente über das Feld hinweg
schieben.
Da muss ich sukzessive die Elemente miteinander verschränken.
Jetzt muss ich ja Elemente von der linken Seite, das ist hier die
linke Seite, das ist die rechte Seite, die muss ich nebeneinander
bringen.
Das heißt, ich muss das Element, das ist hier die Hälfte, hier ist
also links, da ist rechts.
Ich muss also das Element, was hier steht als erstes, das Element muss
an die zweite Position kommen.
Nachher soll hier ein Element stehen, eins von links, eins von rechts.
Also das erste Element hier, das was da steht, an der Position, das
muss anschließend hier hinkommen.
Wenn man sich das anschaut, dann mache ich hier einfach einige
Vertauschungen.
Lokale Vertauschungen, das sollen diese Doppelfeile andeuten.
Einfach nur lokale Vertauschungen.
Und dann wird natürlich das Element sukzessive nach dort
transportiert, nach dort transportiert, nach dort transportiert und
hier ist das alte linke Element.
Also das hier wäre praktisch dann, danach wäre hier also L1 und da
würde im Prinzip R1 stehen, wenn das hier dort R1 ist und das L1.
Das ist einfach eine Menge von solchen Vertauschungen.
Und das heißt, dieses Element wandert an die Position.
Das nächste Element wandert entsprechend auch hier rüber.
Und wenn Sie sich angucken, wie die Wege hier durch diese Vergleiche
oder diese Vertauschungen laufen, sehen Sie, das ist genau das
Perfekte.
Da kann man sich leicht davon überzeugen.
Und ich brauche dafür N½-1 Takte, weil ich halt genau diese Distanz
überwinden muss.
Die Distanz von N½-1.
Nicht genau N½, dann wäre das R1 an die Position von L1 gekommen.
Wenn ich R1 und L1 verkaufe, das will ich ja gar nicht.
Ich will es neben das R1 kriegen und die Distanz ist gerade N½-1.
Und dann muss ich das OITS auf folgende Länge 2n anwenden.
Da wissen wir, dass das in 2n Takten immer möglich ist.
Ich könnte sogar das mit einem Takt weniger machen, aber das ist jetzt
irrelevant.
Man kann das sogar noch etwas optimieren, weil man etwas weiß über die
Reihenfolge der Elemente, die da drin sind.
Und der Schritt 3 OITS, 2n Schritte von OITS, da steht ja gerade 2n,
also 2n Takte.
Und ich habe insgesamt 4,5n-1 Takte für diese 3 Schritte.
Das brauche ich also, also klein n, um n²-Elemente zu verschmelzen,
bzw.
4 Folgen zu verschmelzen, die jeweils n²-Viertel-Elemente haben.
Das ist also die Zeit, also 4,5n-1 Takte.
Und dann müssen wir später sehen, wie sich das dann bei einer
rekursiven Anwendung auf das Zeitverhalten auswirkt.
Aber das ist dann anschließend einfach nur eine übliche Anwendung
unserer Rekurrenzkleidung.
Also zum zeitlichen Ablauf, das ist, glaube ich, sehr einsichtig, dass
das genau diese Zeit ist.
Man kann das noch etwas reduzieren, aber das will ich jetzt hier
überschlagen.
Wichtig ist natürlich, sich anzugucken, warum ist das eigentlich
korrekt.
Und da muss man sich einfach Folgendes überlegen.
Wenn wir natürlich 0-1-Folgen betrachten, wir wollen es die Arbeit so
einfach wie möglich machen, also 0-1-Folgen, unten in dem grauen
Bereich 1n, im weißen Bereich jeweils 0.
Dann kann es unterschiedliche Situationen geben.
Auf jeden Fall ist es so, dass wir einige Zeilen haben werden, in
denen nur 1n stehen.
Und einige, in denen nur 0n stehen.
Und es wird eine Zeile geben, die eventuell 0n und 1n gemischt
enthält.
Denn diese vier Quadranten sind ja sortiert.
Wenn ich vier sortierte Teilfolgen habe, sind das erst 0n und dann 1n.
Und sie unterscheiden sich also durch die Anzahl der vollen 1-Zeilen
und durch die nicht sortierten Zeilen, in denen gerade der Übergang
von 0 auf 1 ist.
Und diese nicht sortierten Zeilen, in denen der Übergang von 0 auf 1
ist, die können auch noch unterschiedlich gerichtet sein.
Sie sehen hier, da geht das von 0 auf 1.
Auch wenn ich es so betrachte, kann ich es auch für Sie anders machen.
Hier geht es also von links nach rechts aufsteigend.
In dieser Zeile geht es von rechts nach links aufsteigend.
Hier ebenfalls von rechts nach links aufsteigend.
Da auch von rechts nach links aufsteigend.
Das ist ein wichtiger Effekt, den man sich genauer angucken muss.
Nach dem Schritt 2 habe ich jetzt zwei Situationen zu betrachten.
Schritt 2 war Sortieren der Doppelspalten.
Wenn ich die Doppelspalten sortiert habe, ich habe ja in meiner
Doppelspalte Elemente aus der linken und der rechten Hälfte, also
genau A, B, C und D, viele Einsen aus den ganzen Einszeilen.
Und dann habe ich eventuell noch weitere Einsen, weil ja hier diese
angefangenen Zeilen noch dazukommen.
Das kann sein, dass noch etwas dazukommt.
Das heißt, nehmen wir mal an, wir haben dieses E, die Anzahl der
Einszeilen, in Quatsch.
Wenn das E die Summe, Entschuldigung, das E ist die Summe dieser A
plus B plus C plus D.
Die sind aufgeteilt auf zwei Zeilen.
Das muss ich in beiden Fällen betrachten, dass das E eine gerade Zahl
ist.
Dann habe ich diese Situation.
Ich habe hier richtig schön, weil das gerade ist, kann ich die schön
aufteilen auf die zwei benachbarten Spalten.
Das sind jetzt die Einsen aus den vollen Einszeilen.
Und dann kann es sein, dass aus weiteren Zeilen, diesen nicht
vollständigen Einszeilen, noch eine Eins dazukommt.
Weil ich vier Quadranten habe, habe ich eben hier zwei weitere Zeilen,
in denen eventuell noch eine weitere Eins steht.
Bis zu vier.
Kann sein, dass gar keine auf da drin ist.
In der Situation, die wir hier haben, können Sie sich sofort angucken,
haben wir, egal welche Doppelspalte Sie sich anschauen, immer
mindestens eine Eins da drin.
Da tritt der Fall gar nicht auf, dass dort keine weitere Eins
dazukommt.
Also, die Höhe dieser vollen Einszeilen ist gerade die Hälfte von E.
Und da das jetzt maximal zwei Zeilen sind, in denen wir zwischen 0 und
4 Einsen haben, reichen 2N Schritte von OITS aus, um diesen Bereich
hier insgesamt zu sortieren.
Das ist eine Folge Länge 2N, maximal Länge 2N, und von der weiß ich,
dass ich die mit 2N Schritten sortieren kann.
Der ganze Rest ist ja schon sortiert.
Das heißt, durch diese Überlegung mit den 0,1 Folgen, kann ich genau
mir angucken, wie groß ist der Bereich, in dem etwas unsortiert ist.
Und ich habe also hier nur einen Bereich, der maximal zwei Zeilen
umfasst, deswegen reichen die 2N Schritte aus.
Also das ist hier die einfache Konsequenz.
Natürlich weiß ich nicht, an welcher Stelle in meiner Matrix, in
meinem Feld, diese Unsortiertheit auftritt.
Deswegen muss ich eben das über das ganze Feld machen.
Aber ich weiß, der Grad der Unsortiertheit, wenn ich das so bezeichne,
das heißt, der maximale Abstand zwischen den Elementen, die an der
falschen Position sind, der ist in diesem Fall 2N.
Das sind nur zwei Zeilen, die sortiert werden müssen.
Jetzt kommt der andere Fall, der ist ein bisschen komplizierter.
Wenn das ungerade ist, das E, dann klappt die Verteilung auf zwei
Spalten nicht so gleichmäßig.
Dann haben wir überall, also natürlich auch wieder unsere Einsen, aber
immer noch hier eine zusätzliche Eins dazu, weil das E ja ungerade
ist.
Also geht das nicht richtig auf.
Und jetzt kommen natürlich auch wieder 0 bis 4 Einsen dazu.
Aus diesen angefangenen Einszeilen, aus den vier Quadranten.
Und das heißt, wenn ich jetzt 4 oben drauflege, dann habe ich hier
einen Bereich von drei Zeilen, in denen Nullen und Einsen auftauchen
können, die noch nicht sortiert sind.
Wenn irgendwo 0 Elemente dazukommen, dann ist halt hier dieses hier
die Zeile, die noch nicht sortiert ist.
Wenn irgendwo 4 Elemente auftauchen, dann habe ich hier oben auch noch
eine Eins und Nullen daneben, also auch nicht sortiert, dann hätte ich
drei Zeilen, die sortiert werden müssen.
Da würden zwei Endschritte nicht ausreichen.
Und nun muss ich mir das genauer angucken.
Was ist eigentlich, also wenn ich mir angucke, das E ist ungerade.
Warum ist das E ungerade?
Weil ich, ich muss angucken, ich habe dieses E ist die Summe von A, B,
C und D.
Das E kann nur ungerade sein, wenn ich eine, wenn also eines von A, B,
C und D ungerade ist oder drei von denen ungerade sind.
Und das, was heißt es, dass das ungerade ist oder gerade?
Das heißt, wenn das A gerade ist und das B ungerade, dann laufen diese
angefangenen Eins-Zeilen in unterschiedlichen Richtungen.
Wenn die alle gerade sind oder alle ungerade, dann laufen die immer in
gleicher Richtung, diese angefangenen Eins-Zeilen.
Aber das, was ich hier angedeutet habe, ist genau so ein Fall, dass
ich drei Richtungen habe, die laufen von links, also drei angefangene
Eins -Zeilen, diese hier, die und diese hier, die laufen von rechts
nach links und die eine hier oben, der linken oberen Ecke, die läuft
von links nach rechts.
Das heißt, wir haben drei angefangene Eins-Zeilen, die in der gleichen
Richtung laufen und eine läuft in der anderen Richtung.
Und jetzt nehmen wir an, es gibt eine Doppelspalte ohne zusätzliche
Eins.
Das tritt in diesem Beispiel hier nicht auf.
Damit irgendwo keine Eins auftaucht, müsste...
Also diese Zeile zum Beispiel hier, müsste etwas weiter rechts die
erste Eins haben.
Weil ich ja an den entsprechenden Stellen, da sind nur Nullen, das ist
der Bereich mit Nullen, das sind Bereiche mit Nullen, das sind
Bereiche mit Nullen.
Damit ich also irgendwo einen Bereich habe, wo keine Eins dazukommt,
müssten diese Einsen hier weiter rechts liegen, als die erste Eins in
diesen angefangenen Eins-Zeilen, die von rechts nach links laufen.
Wenn das aber so ist, dass diese Einsen weiter rechts liegen, dann
habe ich natürlich hier links davon, in dieser Zeile, nur Nullen
stehen.
Das heißt, nur drei andere Quadranten enthalten an diesen Positionen
zusätzliche Einsen.
Nämlich dort, dort und dort.
Das heißt, sobald ich eine Doppelspalte habe, ohne eine weitere Eins
aus einer angefangenen Zeile, habe ich in allen Doppelspalten
höchstens drei Einsen stehen.
Wenn ich aber höchstens drei Einsen stehen habe, dann habe ich nicht
diese Situation, sondern dann habe ich die Situation, dass nur in
diesen beiden Zeilen noch Einzelne auftauchen können.
Das heißt, ich habe nur zwei Zeilen, die nicht sortiert sind.
Perfekt.
Ich kann mit zwei Einsschritten sortieren.
Der nächste Fall ist, dass in jeder Doppelspalte mindestens eine
zusätzliche Eins steht.
Der erste war ja, ich nehme mal an, ich habe irgendwo keine.
Wenn das nicht der Fall ist, dann habe ich also überall mindestens
eine.
Wenn ich aber überall mindestens eine habe, dann habe ich hier
insgesamt Einsen stehen.
Weil überall mindestens eine Eins steht.
Und das heißt, die Unsortiertheit kann nur in diesem Bereich sein.
Die beiden darüber liegenden Zeilen, das sind auch wieder nur zwei.
Ich habe wieder die Situation, dass ich nur zwei Zeilen habe, in denen
Null und Eins irgendwie gemischt auftauchen.
Das heißt, auch hier reicht es aus, mit zwei N-Schritten zu sortieren.
Die zwei N-OTS-Schritte von Schritt 3 reichen aus, um vollständig
sortiert zu haben.
Das heißt, das Verfahren ist korrekt.
Wir haben nach diesen zwei Einschritten eine sortierte Folge in
unserem zweidimensionalen Feld und haben diese vier vorsortierten
Quadranten erfolgreich gemischt zu einer sortierten Folge.
Ich hoffe, dass das verständlich war.
Und ich glaube, Sie sehen hier, wie hilfreich es ist, sich auf Nullen
und Einsen beschränken zu können.
Wenn Sie da anders argumentieren müssten, über beliebige Folgen,
wünsche ich Ihnen viel Spaß.
Jetzt haben wir insgesamt also den Algorithmus LSO3-Sort für N kleiner
gleich zwei.
Machen wir das Sortieren einfach durch einen trivialen Algorithmus.
Sie können sich überlegen, wie viele Schritte Sie dafür brauchen.
Das geht relativ einfach.
Das sind vier Elemente, die Sie sortieren müssen.
Möglichst wenig zu vergleichen.
Für N größer zwei wenden wir das Rekursiv an.
Und das heißt, wir haben dann unsere übliche...
Also hier sage ich, kleiner gleich vier Schritte.
Mit vier Schritten kriegen Sie das immer hin.
Wenn wir das jetzt Rekursiv anwenden, dann haben wir also hier diese
Abschätzung.
Das Verfahren angewandt auf die vier Teilfelder Rekursiv.
Danach sind sie sortiert.
Das mache ich parallel.
Deswegen T LSO3-Sort von N halbe.
Also auf einem Kreuz N halbe Feld.
Und danach noch 4,5 N.
Das Minus Eins habe ich jetzt weggelassen.
Ich habe also hier dieses N stehen.
Und da wissen wir sofort, naja, das ist ja entsprechend unserer
Rekurrenzgleichungskenntnisse dann eine Zeit, die ist kleiner gleich
tatsächlich 9N-14.
Kann man sich genau ausrechnen, dass das so ist.
Will ich jetzt gar nicht im Einzelnen Ihnen genau zeigen.
Das ist aber, kann man sich überlegen, dass das genau so hinkommt.
Dann haben wir hier 9N-14 oder Groß O von Wurzel aus Groß N.
Groß N ist ja Klein N Quadrat, also die Anzahl der Elemente, die
sortiert werden sollen.
Das heißt, wir können jetzt auf dem zweidimensionalen Feld in Wurzel N
sortieren.
Man kann dieses Verfahren, wenn man also genau die Vorsortiertheit der
einzelnen Bereiche sich anguckt, kann man das auf 7N verbessern.
Das ist dann auch wieder etwas schneller.
Wir hatten gesehen, die untere Schranke, das Triviale ist 2N-2, sind
also hier Faktor 4 bis 5 so etwa.
Größenordnung Faktor 4 sind wir weg von der trivialen unteren
Schranke.
Jetzt kann man, das werden wir gleich sehen, eine untere Schranke
zeigen von 3N.
Minus Klein O von N, also irgendein marginaler Term.
Das heißt, 3N ist tatsächlich eine untere Schranke für Sortieren auf
solchen zweidimensionalen Feldern.
Und da sind wir also nur noch ein Faktor etwas mehr als 2 weg von dem
Optimum.
Wir hatten schon mal so einen Fall bei der Auswertung von Polynomen,
wo wir ganz eng dran waren, da sogar scharf auf dem Optimum.
Hier sind wir also relativ nah dran.
Und es gibt tatsächlich ein Sortierverfahren, das in 3N läuft.
Da gehe ich auch nachher nochmal darauf ein, nur kurz Bemerkung dazu,
dass dieses beste Sortierverfahren ist sogar veröffentlicht worden,
bevor wir uns den LSO3-Sortalgorithmus ausgedacht haben.
Und es gab gleichzeitig mehrere andere Sortierverfahren, die auch auf
zweidimensionalen Feldern gearbeitet haben, die auch ähnliche Zeiten
herausgekriegt haben, völlig unterschiedliche Ansätze.
Und dass das andere Verfahren in Zeit 3N gelaufen ist, war da gar
nicht so richtig klar geworden, weil die in der Veröffentlichung
darauf hingewiesen oder da haben sie angenommen, dass sie auf einem
SEMD -Rechner arbeiten.
Wenn ich auf einem SEMD-Rechner arbeite und ich habe zum Beispiel
hier, ich möchte gerne solch einen Vergleich machen, dann muss ich
erstmal ein Element vom rechten Nachbarn lesen, dann muss ich die
Elemente vergleichen und ich muss das Maximum nach rechts schreiben.
Das sind drei Schritte.
Auf dem SEMD-Rechner, weil ich ja erstmal so aufgeteilt, das sind die
einzelnen Operationen, und so haben die das analysiert und kamen dann
mit einer relativ hohen Konstanten raus, aber bezogen auf den Aufwand,
den man auf einem SEMD-Rechner hat.
Wir haben gesagt, wir haben einen MEMD-Rechner, bei dem ich zum
Beispiel auch sowas machen kann, dass ich in aufeinanderliegenden
Elementen einmal so und in den runterliegenden Teilen so etwas machen
kann.
Das sind unterschiedliche Operationen.
Der eine liest von rechts, der andere liest von links.
Also insofern muss man genau aufpassen, was für ein Modell liegt
eigentlich dahinter.
Und weil die das so analysiert haben, das aber nicht so richtig
deutlich war, wenn man das so etwas oberflächlich gelesen hat.
Und dazu noch kam, dass die einen Beweis gemacht haben für die
Korrektheit, eine Argumentation für die Korrektheit, ohne Rückgriff
auf das Null-Eins-Prinzip, war dieser Artikel, in dem das
veröffentlicht wurde, nur sehr schwer wirklich zu lesen und zu
verstehen und nachzuvollziehen, die Korrektheit des Verfahrens.
Die haben übrigens dort eine andere Aufteilung gemacht, die haben dort
eine wesentlich feinere Aufteilung gemacht, die haben ein sogenanntes
S -Quadrat-Way-Merge gemacht, wobei S also ein Wurzel aus kleinen n
ist.
Also ein wesentlich feineres Merge gemacht.
Ein sehr interessantes Verfahren, ist optimal.
Und auch schon vor der Zeit veröffentlicht, als wir unser Verfahren
veröffentlicht haben, aber unser Verfahren ist von der Struktur her
wesentlich einfacher und auch nicht so weit weg von dem Optimum.
Also insofern muss man immer aufpassen, in welche Richtung man
argumentiert.
Also, ich hoffe, Sie haben das Verfahren verstanden.
Es ist relativ einfach.
Korrektheit kann man sich leicht überlegen über Null-Eins-Prinzip.
Und jetzt will ich Ihnen zeigen, warum 3n eine untere Schranke ist.
Und ich will Ihnen das zeigen, weil dabei auch wieder eine
Beweistechnik drin ist, die sehr interessant ist, die mein Kollege
Manfred Kunde entwickelt hat.
Und es geht also darum, dass wir ein zweidimensionales Feld haben, in
dem wir sortieren wollen.
Das heißt, jedes Element unseres Feldes enthält ein Datum, das
sortiert werden muss, also das in die richtige Reihenfolge gebracht
werden muss.
Und wir haben eine gewisse Anzahl Z von Zeilen, eine gewisse Anzahl S
von Spalten.
Muss also nicht notwendigerweise quadratisch sein, kann auch irgendwie
rechteckig sein.
Wir wollen sortieren, deswegen nehmen wir an, wir haben eine geordnete
Datenmenge D und wir nehmen an, dass die Datenmenge groß genug ist.
Kommt wahrscheinlich erst auf der nächsten Folie.
Also ich nehme an, dass ich auf jeden Fall mindestens n
Quadratelemente habe, dann auch ein bisschen mehr.
Ich nehme an, dass ich zu Beginn in jedem Feldelement ein Datum aus D
im Kommunikationsregister habe.
Also dieser Punkt soll das Kommunikationsregister andeuten, das ich
mit dem anderen vergleichen kann.
Und in jedem Takt kann jeder Prozessor die Inhalte seiner vier
Nachbarn lesen, kann beliebige Operationen ausführen und sein eigenes
Speicherbereich verändern.
Die Inhalte der Kommunikationsregister nehmen wir an, seien
zeilenweise oder zeilenweise in Schlangenlinien zu sortieren.
Ich muss ja jetzt etwas über alle beliebigen Algorithmen aussagen und
das sind jetzt die Einschränkungen für meine Algorithmen.
Wir wissen, die triviale untere Schranke ist s plus z minus 2, das war
dieses 2n minus 2.
Wenn ich eben etwas von dort nach dort bringen muss, dann habe ich
genau dieses s plus z minus 2 als Distanz zu überwinden durch lokale
Operationen.
Das sind allein die Schritte, um das dort hin zu transportieren, sind
s plus z minus 2.
Und jetzt wollen wir uns das nicht trivial angucken.
Wir nehmen dafür an, dass wir mindestens zwei n-Quadratelemente haben.
Und zur Vereinfachung, beziehungsweise 2 mal s mal z, zur
Vereinfachung nehmen wir an, das sind gerade Elemente aus dem Bereich
minus n-Quadrat bis n-Quadrat.
Das heißt, ich nehme an, ich habe negative Elemente und positive
Elemente dort drin in dem D, über die ich argumentieren kann.
Und ich nehme an, dass meine Anfangsbelegung so ist, dass genau die
Elemente von 1 bis n-Quadrat in meinem Feld drinstehen.
In irgendeiner Anordnung, irgendeiner Permutation der Elemente von 1
bis n-Quadrat.
So.
Und die wesentliche Idee sieht jetzt so aus.
Ich betrachte einen gewissen Bereich meines Feldes, eine Jokerzone,
die jetzt hier blau markiert ist, und untersuche, wie die
Anfangsbelegung dieser Zone den Sortiervorgang beeinflusst.
Das heißt, ich schaue mir an einen bestimmten Bereich und schaue mir
an, wie dieser Bereich den Sortiervorgang beeinflusst.
Und die Idee ist folgende.
Ich möchte gerne einen schlechten Fall konstruieren für ein
Algorithmus.
Ich möchte zeigen, egal welchen Algorithmus ich wähle, ich kann eine
Eingabefolge konstruieren, die schlecht ist, also schwierig ist für
diesen Algorithmus, weil gewisse Informationen erstmal aus diesem
unteren Bereich, der hier angegeben ist, woanders hinwandern müssen,
damit dort etwas richtig passieren kann.
Das heißt, ich schaue mir an, wie beeinflussen die Elemente, die in
diesem blauen Bereich liegen, die Endposition der Elemente in der zu
sortierenden Folge.
Und ich möchte praktisch durch die Elemente in dem blauen Bereich
dafür sorgen, dass die Zeit fürs Sortieren möglichst lang ist.
Und das wird nun wie folgt gemacht, das werden Sie gleich sehen.
Wir nehmen also hier dieses dreieckige Bereich, sodass hier mindestens
zwei s-Elemente liegen.
s ist die Anzahl der Spalten, z ist die Anzahl der Zeilen.
Wenn ich hier mindestens zweimal Wurzel-s-Elemente als Kantenlänge
habe, dann habe ich also mindestens zwei s-Elemente dort in dem blauen
Feld.
Und zwei s-Elemente sind genauso viel wie Elemente, die in zwei Zeilen
enthalten sind.
Das heißt, ich muss mindestens so viele Elemente in der dreieckigen
Zone haben, wie ich in zwei Zeilen anordnen kann.
Das ist die Idee dahinter.
Und für die Anfangsbelegung nehme ich mal an, dass die Elemente in der
Joker -Zone größer sind als alle anderen.
Das kann ich ja problemlos hinkriegen, das ist eine spezielle
Anfangsfolge.
Das ist etwas, was für beliebige Folgen gelten soll.
Jetzt nehme ich also hier unsere beliebige Sortierverfahren-Sort.
Und jetzt kommt hier noch eine weitere Annahme.
Ich nehme an, dass nach jedem Schritt jeder Prozessor genau ein
Element der zu sortierenden Folge enthält.
Also keiner kann sich die ganze Folge irgendwie reinschreiben.
Und dann machen wir jetzt folgende Überlegung.
Wie lange dauert es, bis Information aus diesem Bereich, aus der Joker
-Zone, an dieser Stelle hier oben, links oben, irgendeine Wirkung
entfalten kann.
In jedem Schritt mache ich eine Operation, bei der ich irgendwie
Elemente miteinander vergleiche.
Also ich lese etwas rechts oder ich lese etwas unten.
Und dadurch, dass ich etwas unten oder rechts lese, wird Information
nach links bzw.
nach oben bewegt.
Das heißt, sukzessive wandert die Information in diese Richtung, die
hier durch den Pfeil angedeutet ist.
Und irgendwann habe ich genügend Schritte ausgeführt, damit die
Elemente aus der Joker-Zone eine Wirkung entfalten können, auf das
Element hier oben, an der Position.
Dann muss ich mir nur angucken, wie weit ist diese Distanz.
Dann muss ich mir diese Entfernung angucken plus die Entfernung.
Ich habe ein zweidimensionales Gitter, habe also einfach eine
Manhattan -Distanz, die Differenz der Koordinaten.
Das ist für alle Punkte, die auf dieser Linie hier liegen, die gleiche
Distanz.
Das heißt, das ist genau das, was ich mir angucken muss.
Und wie viel habe ich dort drin?
Das waren 2 Wurzel S, war dieser Bereich hier.
Das heißt, ich muss Z-2 Wurzel S, das ist dieses Stück, nach oben
wandern.
Und die horizontale Distanz hier, das ist gerade S-1.
Das heißt, nach Z-2 Wurzel S plus S-1 Takten, habe ich das erste Mal
eine Operation, bei der ein Element aus der blauen Zone mit involviert
sein kann.
Das vielleicht auf dem Weg dahin gewandert ist, durch diese
Vergleiche, die gemacht wurden.
Oder ich kann sagen, dass Informationen dorthin gewandert sein können.
Davor kann das, was da oben passiert, überhaupt nicht beeinflusst
worden sein, durch das, was in der blauen Zone passiert.
Und ich nehme an, dass in dem Takt, in dem das erste Mal Informationen
aus der blauen Joker-Zone eine Rolle spielt, ein Element A dort drin
steht.
Das muss nicht das Element sein, das zu Anfang dort drin stand.
Da sind ja schon alle möglichen Vergleiche gemacht worden, oder alle
möglichen Operationen.
Aber in dem Takt, im Takt Z-2 Wurzel S plus S-1, steht dort ein
Element A drin.
Das stammt mit Sicherheit nicht aus der Joker-Zone.
Und jetzt schaue ich mir an, was passiert bis zum endgültigen
Sortieren.
Bis zum endgültigen Sortieren muss ja dieses Element irgendwo
hinwandern.
Das wird ja irgendwo hin sortiert durch die nachfolgenden Schritte und
ist dann irgendwann an der endgültigen Position angelangt.
Die kann irgendwo sein.
Und jetzt kommt die Idee mit der Joker-Zone zur Geltung.
Jetzt möchte ich dafür sorgen, dass diese Position, an die das Element
A am Ende bewegt wird, möglichst weit weg liegt von der Position, an
der das A war, als es von der Information aus der Joker-Zone
beeinflusst wurde.
Das heißt, möglichst weit weg von dieser linken oberen Ecke.
Ich habe zwei S-Elemente zur Verfügung.
Der maximale Ort, zu dem ich das bewegen kann, wäre also irgendwo da
rechts.
Weiter kann ich das nicht bewegen.
Wie kann ich das bewegen?
Dadurch, dass ich die Elemente aus der Joker-Zone so verändere in der
Größe, dass das Element nach rechts wandern muss.
Sogar nach rechts und noch in die Zeile weiter drunter.
Es könnte aber sein, dass diese Position hier, ich möchte das Ganze
nach rechts bewegen, also die Position soll nachher, und zwar sollen
kleinere Elemente davor kommen.
Ich möchte das Element einfach verschieben durch kleinere Elemente.
Man muss die Frage, in was für einer Zeile ist dieses Element an der
Position, wo es am Ende gelangt war, geht das hier aufsteigend oder
geht das absteigend?
Das heißt, ich mache hier eine Schlangenlinien-Sortierung.
Und da kann es sein, wenn ich jetzt kleinere Elemente dazulaufen
lasse, dann wird ja das Element weiter nach oben kommen, dann bekommt
es eine höhere Rangposition, und läuft dann aber erstmal nach links.
Und dann muss ich es ja erstmal hier ganz rum bewegen, bis es dann
irgendwann dort rechts hinkommt.
Das heißt, das wäre ein Fall, da muss ich das ganz rum bewegen.
Dazu brauche ich diese 2S-Elemente.
Nicht ganz 2S, eigentlich reicht 2S-1 aus, aber immerhin.
Ich muss es eventuell über zwei Zeilen oder fast zwei Zeilen hinweg
bewegen.
Und deswegen brauche ich so viele Elemente.
Und das mache ich so, dass ich also die Elemente in der Joker-Zone,
oder ich suche jetzt eine Folge, bei der, abhängig von dem Element,
was dort stand, halt die endgültige Position von dem A garantiert ganz
rechts ist.
Und dadurch weiß ich, wenn das A zunächst mal hier oben links war, und
anschließend ganz nach rechts gewandert ist, wie es jetzt hier zu
sehen ist, dann habe ich nach diesen Z-2-Wurzel-S-S-1-Takten nochmal
mindestens diese Distanz zu überwinden, also mindestens S-1.
Und damit kann ich also dazu nochmal S-1 draufaddieren.
Und bekomme dann insgesamt, wenn ich das jetzt hier mir angucke als
untere Schranke, Z-plus-2-S-2-Wurzel-S-2.
Ja, das sind nochmal diese S-1 dazugezählt, zu diesem Anfangsweg, bis
wir das Element oben links beeinflusst haben.
Und das heißt, das sind insgesamt Z-plus-2-S-Groß-O-von-Wurzel-S.
Das ist dieses klein O-von-N, was ich im Prinzip ignorieren kann.
Marginal kleiner Term.
Das heißt, meine untere Schranke ist Z-plus-2-S.
Und wenn ich jetzt S-gleich-Z-gleich-N habe, dann ist die untere
Schranke 3-N.
Ja, und damit habe ich hier dann diese untere Schranke gezeigt.
Und wenn ich mir jetzt angucke, andere Verhältnisse von Z und S.
Wenn das S kleiner ist als Z, das heißt, mein Feld sieht im Prinzip so
aus.
Ich habe deutlich mehr Zeilen als Spalten.
Das Verhältnis zwischen den beiden ist 1 zu 2.
Dann habe ich auf einmal die untere Schranke 2-mal-Wurzel-2-mal-N.
Minus-Groß-O-von-Wurzel.
Also eine etwas kleinere untere Schranke.
Das heißt, da greift dieses Argument nicht ganz so stark, weil der Weg
bis hier nach rechts nicht so groß ist.
Dieser Weg hier ist einfach kleiner.
Und das heißt, ich habe hier etwas andere untere Schranke.
Und das Interessante ist, das S-Quadrat-Weg-Merge-Sort von Thomson
-Kung ist, egal welches Verhältnis ich nehme, immer das Optimale.
Also das war dieses von Thomson-Kung, das war das Verfahren, das ich
angedeutet habe.
Wir haben mit einem S-Quadrat-Weg-Merge ein Verfahren entwickelt.
Wie gesagt, das als etwas sehr kompliziert dargestellt.
Und deswegen ist das nicht so richtig wahrgenommen worden.
Ist dann aber irgendwann tatsächlich, hat man das gemerkt.
Und es gibt auch inzwischen mehrere Verfahren, die in Zeit 3N laufen.
Nicht nur dieses von Thomson-Kung.
Und für SIMD hat man allerdings noch, wenn man sagt, ich muss auf
jeden Fall mit SIMD arbeiten.
In jedem Takt, in allen Prozessoren im gleichen Befehl.
Dafür kenne ich keine bessere untere Schranke.
Also es ist mir nicht bekannt, eine bessere untere Schranke als für
SIMD.
Und das beste Verfahren, nach meiner Kenntnis, liegt bei 6M.
Das heißt, da sind wir noch weiter weg.
Ich nehme aber an, dass man eigentlich für SIMD auch eine bessere
untere Schranke hätte zeigen können.
Ja, das also zu diesem zweidimensionalen Sortieren.
Wenn man nicht annimmt, dass die Elemente oder dass die Prozessoren in
jedem Takt nur ein Element der Folge speichern dürfen, dann ist es
sogar so, dass nur die triviale untere Schranke gilt.
Und dann kann man sogar auch diese untere Schranke erreichen.
Das geht aber auch deutlich über das hinaus, was ich Ihnen hier zähle.
Man kann also auf zweidimensionalen Feldern sehr, sehr interessante
Algorithmen entwickeln, die sortieren und die dann diese Schranken
noch verbessern.
Mir lag also vor allem daran, Ihnen nochmal zu zeigen,
zweidimensionales Sortieren reduziert die Laufzeit.
Nicht auf Log N, nur auf Wurzel N, weil ich da diese unteren Schranken
habe.
Ich kann dort sogar optimal sortieren, kann die Schranken erreichen.
Und wir haben hier ein interessantes Verfahren, um untere Schranken zu
zeigen, über diese Joker-Zone, bei der ich im Prinzip in der Lage bin,
also was ein Joker ist, wissen Sie ja, dass man erstmal etwas hinlegt
und dann nach Bedarf den Wert bestimmt, um etwas schlecht zu machen
für den Gegner.
Und genau das ist die Idee hier.
Dass ich eben die Elemente in der blauen Zone, in der Joker-Zone,
schlecht mache für den Algorithmus und dadurch braucht er mindestens
diese Zahlen.
Okay, das also zu diesem... Es gibt dann noch viele andere Verfahren,
mit denen man mit anderen Sortierordnungen arbeitet, also zeilenweise
oder spaltenweise oder spiralförmig oder was immer man machen will.
Man kann auch noch andere Strukturen betrachten.
Man kann ein Torus betrachten, bei dem man also nicht ein einfaches
gitterverbundenes Feld hat, sondern wo das links nach rechts auch noch
verbunden ist.
Man kann lineares Feld betrachten, man kann Kreise betrachten.
Sehr viele verschiedene Strukturen, Bäume, man kann daraus sortieren.
Und man kann auch etwas betrachten, was ich Ihnen auch noch vorstellen
wollte, das ist ein Mesh of Trees.
Auch eine interessante Rechnerstruktur, die zwei Dinge miteinander
verbindet.
Einerseits die Vorteile einer Baumstruktur mit einer Tiefe von log n
bei zwei n Elementen und eine lokale Struktur, das heißt so ein
Gitter.
Ich habe also hier im Prinzip mein Gitter und habe die Elemente anders
verbunden.
Ich habe durchaus lokale Nachbarschaftsbeziehungen, wenn ich also hier
über die erste Stufe gehe, die beiden Elemente hier oben sind zum
Beispiel verbunden über einen Knoten eines Zeilenbaumes.
Genau über diesen einen Knoten eines Zeilenbaumes, also ist das hier
so eine Art lokale Verbindung.
Ich habe also durchaus eine lokale Struktur, habe aber auch, wenn ich
den Baum nach oben laufe, habe ich hier eine Baumstruktur für die
Verbindung, kann also in Zeit log n Informationen über eine ganze
Zeile oder eine ganze Spalte austauschen, weil ich Spaltenwollne und
Zeilenwollne habe.
Und diese Struktur, die hat man also so Anfang der 80er entwickelt,
hat man sich hier ausgedacht.
Das war der Tom Leighton, derjenige, der das Verfahren Akamai
entwickelt hat.
Akamai ist also ein Verfahren, mit dem man in der Lage ist, im
Internet sehr effizient Informationen bereitzustellen.
Der Tom Leighton ist mittlerweile Milliardär, weil er sehr
interessante Ideen hatte, wie man effizient Informationen im Internet
bereitstellen kann.
Fast jeder, der Informationen anbietet, setzt die Technologien von
Akamai an mittlerweile.
Also, nur als kurze Bemerkung, dass man auch als theoretischer
Informatiker, der sich mit Algorithmen beschäftigt, sehr gut
wirtschaftlich interessante Ideen entwickeln kann und umsetzen kann
und sehr viel Geld verdienen kann.
Was wird hier gemacht?
Hier wollen wir sortieren, auf dem Mesh of Trees.
Und hier verwenden wir jetzt, um eine Folge der Länge n zu sortieren,
viel zu viele Elemente, nämlich n²-Elemente.
Ich nehme ein n mal n-Feld fürs Sortieren von n Elementen.
Und verteilen einfach diese n Elemente sowohl über die Zeilenbäume als
auch über die Spaltenbäume.
Ich verteile sie, x1 bis x4 in dem Fall, über die Zeilen- und
Spaltenbäume an die Prozessoren.
Und habe dann hier zum Beispiel in diesem Element die beiden Elemente
1 und 1, x1 doppelt drinstehen.
Hier steht jetzt drin das x1 und x2 und so weiter.
Und hier steht dann x1 und x4 drin.
Und hier unten dann halt entsprechend x4 und x4.
Das passiert nach dem ersten Schritt.
Verteilen über die Spalten- und Zeilenbäume heißt, ich muss lockend
Schritte von der Wurzel bis zu den Blättern laufen.
Dann habe ich also in jedem Prozessor zwei Elemente drin liegen.
Ich kann die beide vergleichen, insbesondere auf ihre Größe.
Und wenn das Element, das über die Spalte kam, wenn das größer ist als
das Element, das über die Zeile kam, dann schreibe ich eine 1 dort
rein.
Ich muss ja irgendwie das festlegen.
Ich gucke mal an, ich vergleiche die beiden Elemente.
Und wenn das Spalten-Element größer als das Zeilenelement ist, dann
schreibe ich dort eine 1 rein, ansonsten eine 0.
Und dann sende ich diese Ergebnisse, die Nullen und Einsen, über
diesen Spaltenbaum zu den Spaltenbaumwurzeln.
Das heißt, ich nehme jetzt hier zum Beispiel in dieser ersten Spalte
die Elemente, die dort stehen, das sind irgendwelche Nullen und
Einsen, die bewege ich nach oben und addiere sie dabei.
Also ich addiere sie dabei, das heißt, ich habe anschließend oben in
der Wurzel dieses Baumes die Anzahl der Elemente, die größer waren,
oder die Anzahl der Vergleiche, bei denen das Element, das in dieser
Spalte verteilt wurde, größer war als die Zeilenelemente.
Ja, wenn es für A größer B, A ist Spalte, B ist Zeile, ich addiere sie
dabei, da stehen dann Einsen.
Das heißt, der Rang, sei jetzt Eins, Zwei, Drei oder Vier aufsteigen,
wenn der Rang Vier ist, ist Vier das größte Element.
Wenn also Vier Einsen drin, wenn hier Vier Einsen drin standen, da
eine Eins, da eine Eins, da eine Eins, da eine Eins, dann war das
Element X1 größer gleich alle anderen.
Es kann natürlich nur dreimal größer sein.
Ja, weil es ansonsten wäre es ja größer gleich.
Da sind maximal drei Einsen drin.
Bei dem ersten steht garantiert eine Null drin, weil das ja gleich
sich selbst ist.
Also drei Einsen.
Das heißt, ich habe Null bis drei Einsen da drin stehen.
Also mache ich das hier in der Rangordnung Null, Eins, Zwei, Drei.
Und jetzt sende ich die Ergebnisse, also das habe ich gemacht, und
jetzt verwende ich die binäre Darstellung des Ranges.
Binäre Darstellung des Ranges.
Ich habe also entweder Null, Null, Null, Eins, Eins, Null oder Eins,
Eins, um rangrichtig durch den Baum nach unten zu laufen.
Das heißt, wenn ich zwei Einsen dort stehen habe, gehe ich zweimal
nach links.
Wenn ich von hier runter laufe, gucke ich durch die Laufrichtung, gehe
zweimal nach links, dann lande ich hier unten.
Zweimal nach eins heißt Rang drei.
Wenn ich keine Eins dort hatte, dann waren alle anderen Elemente
größer, dann lande ich hier, dann gehe ich zweimal nach rechts.
Null heißt nach rechts laufen, Eins heißt nach links laufen.
Ich nehme also einfach die binäre Darstellung und nehme die als
Navigationshilfe durch den Baum.
Und anschließend gebe ich einfach den Wert von den erreichten
Prozessoren aus, also den Wert, der ursprünglich hier reingeschrieben
wurde, das war also der Wert von dem X1, das X1 steht ja hier drin,
gebe ich also den entsprechenden, über die Spalte ursprünglich
eingegebenen Wert, über den Zeilenbaum aus.
Wenn ich also Rang drei hatte, wenn das hier das größte Element war,
also X1 das größte Element war, dann würde ich das an dieser Stelle
ausgeben, Rang drei.
Wenn es das kleinste war, dann wäre ich hier gelandet, würde es über
den Zeilenbaum ausgeben und wäre an der Stelle gelandet.
Das heißt, über das Ausgeben über die Zeilenbäume habe ich garantiert
die rangrichtige Anordnung auch an den Wurzeln der Zeilenbäume.
Und der Aufwand dafür ist relativ schnell abzuschätzen.
Ich habe für das Verteilen oder auch Aufsammeln über die Zeilenbäume
oder Spaltenbäume jeweils Aufwand Block N.
Ich mache einmal einen Vergleich innerhalb der Prozessoren.
Ich habe also vier Mal, ich muss erst mal verteilen über die Spalten-
und Zeilenbäume, damit die Elemente in die Prozessorelemente gelangen.
Dann muss ich den einen Vergleich machen und dann muss ich einmal die
Ergebnisse aufaddieren.
Dann muss ich runter wieder die rangrichtigen Prozessor anstoßen und
der muss über den Zeilenbaum ausgeben.
Das sind also nochmal diese drei Log N-Takte, also vier Log N plus
eins Takten.
Damit habe ich dann in vier Log N plus eins Takten insgesamt sortiert.
Allerdings mit N² Elementen.
Also ich habe drei N² minus zwei N Prozessoren.
Wenn ich noch die ganzen Knoten in den Spalten- und Zeilenbäumen
dazuzähle, sind es drei N² minus zwei N Prozessoren.
Und das heißt, die Effizienz ist nicht allzu doll.
Weil ich mit N² Prozessoren nur eine Laufzeit von Log N erreiche.
Und wir wissen ja, dass wir N Log N, dass das das beste sequenzielle
Verfahren ist.
Und müssen jetzt mit N² Elementen, naja, das ist viel zu viel.
Wir sollten maximal N Log N Elemente verbrauchen.
Es gibt andere Verfahren.
Es gibt ein Verfahren, das nennt sich Cold Sort.
Das läuft deutlich besser.
Ich will hier nicht zu viel Zeit drauf verschwenden, sondern
einsetzen, um Ihnen jetzt nur Sortierverfahren zu erläutern.
Aber man kann eben noch weitere Verfahren finden, die tatsächlich
parallel sortieren.
Es gibt optimales Verfahren, bei dem man mit N Prozessoren tatsächlich
in Zeit Log N sortieren kann.
Allerdings ist die Konstante bei dem Verfahren sehr hoch.
Das heißt, praktisch einsetzbar ist dieses optimale Verfahren leider
nicht.
Praktisch einsetzbar ist sowas wie unser LSO3 Sort oder das von
Thomson Coom.
Oder vielleicht sogar das OETS.
Man muss sich eben genau angucken, auf welcher Struktur muss ich
gerade arbeiten.
Und auch in der PRAM würde man also eher Odd Even Merge Sort oder
Bitonic Sort einsetzen, als diese anderen Verfahren.
Auch dieses Mesh of Trees hier mit N Prozessoren ist einfach zu viel
Platzaufwand.
Ich wollte Ihnen trotzdem diese Struktur darstellen.
Sie ist ganz interessant.
Im Prinzip ist das eine Struktur, die so auf einer PRAM dafür sorgt,
dass man kein Concurrent Read und Concurrent Write braucht, sondern
dass man das verteilen kann.
Über solche Baumstrukturen.
Man könnte das hier auch ohne diese Baumstrukturen als einen PRAM
-Algorithmus formulieren, bei dem man mit Concurrent Read und
Concurrent Write arbeitet.
Mit einer Summenregel.
Wenn ich eine Summenregel nehmen würde, dann würde ich also dieses
hier mit einer, würde ich alles reinschreiben, in eine Position mit
Summenregel als Konfliktlösung und hätte dann sogar in konstanter Zeit
mit N²-Elementen sortiert.
Das geht in der Praxis eben leider nicht.
In der Praxis brauchen wir solche Baumstrukturen.
Das sei dazu genug.
Also hatte ich gerade eben was zu gesagt.
Hängt also was mit Concurrent Read, Concurrent Write Strukturen
zusammen.
Und damit kommen wir ganz kurz eine Folie zum unteren Schrank für die
Anzahl der Vergleiche.
Die Frage ist, ginge es theoretisch besser als mit N-Log-N-Vergleichen
zu sortieren?
Also das waren die Anzahl der Vergleiche bei Merge Sort oder auch bei
Quick Sort im günstigen Fall und im mittleren Fall oder auch bei Heap
Sort.
Heap Sort ist übrigens das von der Anzahl der Vergleiche her beste
Verfahren das man kennt aus sequenziellen Rechnern.
Allerdings eine besondere Variante von Heap Sort.
Nicht die, die Ihnen vorgestellt wurde in den Grundlagen der
Informatik 1.
Aber die sind von der Größenordnung her alle im gleichen Bereich.
Abgesehen von Quick Sort, das im schlechtesten Fall N²-Elemente
braucht.
Und das, was wir uns überlegen müssen, ist einfach, wenn ich eine
untere Schranke mache, worüber argumentiere ich?
Und wir hatten ja gesagt, wir gucken uns allgemeine Sortierverfahren
an, bei denen wir nichts wissen von vornhinein über die Elemente, die
sortiert werden müssen.
Wir wissen nur, wir können sie in Bezug auf die Größe vergleichen.
Mehr wissen wir nicht.
Das sind dann die allgemeinen Sortierverfahren und wir wissen, dass
wir die nur über den Entscheidungsraum sortieren können.
Und wenn man annimmt, dass alle Listelemente verschieden sind, dann
weiß ich bei einem, wenn ich anfange mit der eingegebenen Liste, dann
kann ich hier irgendwelche Entscheidungen treffen und ich habe einen
binären Baum, bei dem ich irgendwann dann hier auf eine ganze Reihe
von Blättern komme und die Anzahl der Blätter, die ich hier habe, die
muss größer gleich N-Fakultät sein.
Weil ich N-Fakultät verschiedene Sortierereihenfolgen haben kann.
N-Fakultät-Permutationen einer Folge.
Das heißt, egal welche Folge ich eingebe, ich muss immer auf die
richtige Sortierereihenfolge kommen.
Das heißt, ich muss jede beliebige Permutation ausführen können durch
das Sortieren.
Und damit habe ich mindestens N-Fakultät-Blätter in meinem
Entscheidungsraum.
Es kann sein, dass bei einem Verfahren, das ausgeführt wird, sogar
mehr als diese N-Fakultät rauskommt.
Dass man also mehrfach der Pfade durchläuft, bei dem ich auf die
gleiche Folge komme, dann hätte ich einen ineffizienten
Entscheidungsraum.
Weil ich brauche eben mindestens diese N-Fakultät.
Und wenn ich mir so einen Baum angucke, sage ich intuitiv sofort, das
geht ja hier noch irgendwie weiter, das ist ja irgendwie ein binärer
Baum.
Dann sage ich, naja, dann ist doch eigentlich klar, dass die Länge der
Wege hier log von N-Fakultät sind.
Es ist nur die Frage, welche Struktur hat denn der Baum.
Wenn das ein vollständiger binärer Baum ist, dann ist es sofort klar,
der muss Log N-Fakultät haben als maximale Pfadlänge oder auch
mittlere Pfadlänge.
Also die Anzahl der Vergleiche im schlechtesten Fall ist ja die
maximale Pfadweglänge, die Anzahl der Vergleiche im Mittel ist die
mittlere Weglänge.
Wenn ich jetzt sagen will, was ist eigentlich die untere Schranke für
die Anzahl der Vergleiche im schlechtesten Fall, also für die maximale
Weglänge, muss ich über alle möglichen Entscheidungsbäume
argumentieren.
Und jetzt kann man sich genau überlegen, was passiert, wenn ich einen
Baum habe, bei dem die Pfade, die hier so durchlaufen, sich um maximal
k oder irgendwas unterscheidet.
Ich habe also irgendeinen Pfad, der hat eine Länge x und ein anderer
Pfad, der hat eine Länge x-k.
Also k sei das Maximum der Unterschiede.
Und da kann man zeigen, wenn das k größer gleich 2 ist, dann kann ich
den Baum so umbauen, kann ich die Struktur so verändern, dass ich den
Abstand um 1 reduziere.
Dass ich dann anschließend k-1 als maximale Differenz habe in den
Pfadlängen.
Das heißt, ich kann, egal, welchen Entscheidungsbaum ich mir hernehme,
ich kann den Baum so verändern, dass ich auf eine maximale
Pfadlängendifferenz von 1 komme, ohne dass das Verfahren inhaltlich
besonders verändert wird.
Und das heißt, eine untere Schranke kann sich beziehen auf...
oder man kann eben auch zeigen, dass diese Vergleiche schlecht sind.
Also es ist klar, wenn die maximale Wegdifferenz k-1 ist, dann habe
ich bei der maximalen Weglänge den bestmöglichen Pfad.
Und für diese Bäume ist auch so, dass die mittlere Weglänge dann auch
der bestmögliche Pfad ist.
Und das kann man sich genau überlegen.
Will ich nicht im Einzelnen durchführen, sondern ich sage Ihnen
einfach, man macht das über diese Überlegung, indem man einfach zeigt,
wenn die Differenz größer ist, kann man das reduzieren auf einen Baum,
der diese maximale Pfadlängendifferenz von 1 hat.
Das ist ein fast ausgeglichener Baum.
Und für diesen fast ausgeglichenen Baum ist tatsächlich die maximale
und die mittlere Weglänge in log n Fakultät natürlich.
Und wenn ich mir log n Fakultät anschaue, dann ist das Omega von n mal
log n.
Das kann man sich überlegen, auf verschiedene Art und Weisen.
Unter anderem über die Stirling-Formel.
Auch darauf will ich nicht im Einzelnen eingehen.
Das sind also einfach Überlegungen für diese Abschätzung.
Man kann das sich sehr einfach abschätzen.
Also im Prinzip log n Fakultät, kann er Ihnen hier etwas hinschreiben,
log n Fakultät ist natürlich kleinergleich log n hoch n.
Da werden Sie sofort zustimmen, dass das der Fall ist.
n Fakultät ist das Produkt von 1 bis n.
Das ist sicherlich kleinergleich log n hoch n.
Und das ist aber gleich n mal log n.
Ja?
Dem werden Sie sicherlich auch sofort zustimmen.
Und natürlich ist das log n Fakultät auch größergleich log Produkt von
sagen wir mal einfach Produkt ja
das ist nehmen wir einfach mal hier ein Teil raus N-Halbe, das ist
größer gleich, N-Halbe, hoch, N-Halbe.
Ich nehme einfach von N-Halbe an, schreibe ich nur mal N-Halbe, mal N
-Halbe und so weiter.
Ich reduziere einfach die zweite Hälfte dieses Produkts.
Und das ist aber gleich N-Halbe mal log N-Halbe.
Das ist ganz einfach.
Ganz grobe Abschätzung.
Aber da sehen Sie sofort, N-Halbe mal log N-Halbe ist natürlich Omega
von N log N.
Und das hier war das N log N.
Hier ist natürlich eine Groß-O von N log N.
Damit haben wir das Log-N-Fakultät sehr einfach abgeschätzt.
Zwischen N-Halbe mal log N-Halbe und N mal log N.
Eine sehr einfache Abschätzung.
Man kann das genauer machen, brauchen wir hierbei nicht.
Also, das ist die untere Schranke für Sortieren.
Jetzt wissen wir, wir brauchen mindestens N log N Vergleiche.
Jetzt kommt ein spezielles Sortierverfahren, das wie folgt arbeitet.
Ich will einfach sortieren durch Dosen werden.
Ich gebe einfach jedem von Ihnen eine Dose.
Da steht auf jedem eine Zahl drauf.
Von, in diesem Fall, 1 bis 5 oder 1 bis 6.
Und ich nehme dann Folge, die hat nur Zahlen 1 bis 6.
Aber die ist bedienlich lang.
Eine sehr lange Folge.
Und ich sortiere jetzt folgendermaßen.
Ich stelle Ihnen also die Dosen hin, nehme meine Folge-Elemente,
schaue mir also irgendein Element an und werfe dieses Element dann in
die entsprechende Dose rein.
Wenn es eine 5 ist, werfe ich es in die Dose 5, wenn es eine 1 ist, in
die Dose 1 und so weiter.
Dazu schaue ich mir natürlich jedes Element nur einmal an.
Aha, das ist Element 4 in Dose 4.
Und anschließend nehme ich meine 6 Dosen her, nehme sie der Reihe nach
und leere sie aus.
Ich nehme also jedes Element aus der ersten Dose, alle aus der
zweiten, alle aus der dritten und so weiter.
Und da ich das in der Reihenfolge 1 bis 6 mache, habe ich sie
anschließend alle sortiert.
Und wenn ich das sogar noch so mache, dass ich die Reihenfolge genau
dabei aufrechterhalte, die Reihenfolge, in der ich die Elemente aus
meiner Ursprungsfolge genommen habe, also wenn ich hier meine sehr
lange Folge habe und da tauchten an vielen Stellen das Element 2 auf.
Und ich schreibe die genau in dieser Reihenfolge, hier das Element,
das, das und so weiter, ich schreibe die schön der Reihen nach in
meine Dose mit Aufschrift 2 rein.
Dann kann ich die natürlich anschließend auch genau in der Reihenfolge
wieder rausholen.
Das heißt, ich kann die also sortieren in Bezug auf die Werte 1 bis 6,
in dem Fall, oder 1 bis K.
Und habe sogar die Reihenfolgen, in denen die vorher aufgetaucht waren
in meiner Folge, aufrechterhalten.
Und ich habe jedes Element nur zweimal angeschaut oder in der Hand
gehabt.
Einmal angeschaut, reingeworfen, einmal rausgeholt.
Das heißt, ich habe insbesondere keinen einzigen Vergleich von
Schlüsseln vorgenommen.
Ich sortiere völlig ohne Vergleich.
Ich habe nur zwei Operationen pro Element, habe also ein sehr, sehr
schnelles Verfahren, lineare Zeit für Sortieren.
Allerdings habe ich eben auch eine ganz andere Information von
vornherein gehabt.
Ich wusste, es sind Elemente von 1 bis 6.
Ich habe mir die Dosen hingestellt und kann entsprechend sortieren.
Das heißt, wenn ich weiß, ich habe nur einen beschränkten Umfang der
Elemente, die ich sortieren muss, und werfe die da einfach sukzessive
rein, dann ist das alles relativ einfach.
Aber wenn der Bereich zu groß ist, dann wird das aufwendig.
Das heißt, auch das hier, dass die ursprüngliche Reihenfolge nicht
verändert wird, kann man also auch im Prinzip machen, habe ich schon
gesagt.
Man kann auch noch anders sortieren, man kann auch einen Radixort
nehmen.
Ich habe beliebige Zahlen, ich weiß nicht, welche tauchen eigentlich
auf.
Aber ich habe meinetwegen irgendwelche 16-Bit-Zahlen,
um das einfacher zu machen.
Dann würde ich einfach zunächst mal nach der ersten Position
sortieren, dann würde ich nach der zweiten Position sortieren und das
mit zwei Dosen machen, dann nach der dritten Position und so weiter.
Hätte ich also 16-mal jeweils so 0,1 Sortierungen zu machen.
Natürlich muss ich immer innerhalb das dann dabei eine richtige
Reihenfolge behalten.
Und dann hätte ich im Prinzip 16-mal linearen Aufwand.
Das ist immer noch konstant.
Allerdings, wenn die alle verschieden sind, dann habe ich maximal 2
hoch 16 verschiedene Elemente.
Und das heißt, dann hätte ich, wenn das 2 hoch 16 n ist, hätte ich
gerade log n solche Dosen und ich müsste aus log n Dosen etwas
rausholen, dann hätte ich log n mal n als Aufwand.
Das kennen wir schon.
Das heißt, man muss aufpassen, was man macht.
Wenn man etwas weiß, was die Unsicherheit über die zu sortierenden
Elemente deutlich reduziert, dann kann man das ausnutzen, kann
spezielle Sortierverfahren machen und kann in linearer Zeit sortieren.
Das tritt in der Praxis durchaus häufig auf und dann sollte man das
auch verwenden.
Also nur, dass Sie wieder sehen, genau wie beim Auswerten von
Polynomen, da hatten wir gesehen, wenn wir die Koeffizienten kennen,
können wir schnell Polynome auswerten, weil wir dann anders daran
gehen können, wenn wir die Koeffizienten vorher kennen, wenn wir das
ausnutzen.
Hier können wir, wenn wir wissen, was ist der Zahlenbereich, dann
können wir eventuell auch deutlich schneller sortieren.
Okay, das war alles, was ich Ihnen zum Sortieren erzählen wollte.
Man hätte darüber noch viel mehr erzählen können auf allen möglichen
anderen Strukturen.
Sortierverfahren machen insbesondere in Bezug darauf, wie kann ich
sortieren, wenn viele meiner Elemente im Hintergrundspeicher liegen.
Da muss man sehen, dass man die Anzahl der Zugriffe auf den
Hintergrundspeicher reduziert.
Und Sie wissen, dass Zugriffe auf den Hintergrundspeicher sehr viel
Zeit brauchen, einfach weil dort die Zugriffszeiten einfach hoch sind.
Und da muss man sehr genau sein Daten- oder das Speichermanagement
machen, um tatsächlich sortieren zu können.
Da hat ja vor kurzem mein Kollege Peter Sanders hier am KIT einen
Weltrekord aufgestellt in Bezug auf das Sortieren von sehr riesigen,
wirklich sehr sehr sehr großen Daten.
Durch sehr effizientes Ausnutzen von parallelen Rechnern, aber auch
durch sehr effizientes Speichermanagement.
Also das ist ein Punkt, wo noch immer sehr viel daran gearbeitet wird.
Und ich hoffe, dass ich Ihnen jetzt einiges in dem Beispiel an
Prinzipien hab präsentieren können.
Insbesondere eben 0-1-Prinzip und dann wie man so auf verschiedene
Strukturen geeignet arbeitet.
Jetzt kommen wir zu Selektionsverfahren.
Einfacher als Sortieren.
Wir wollen nicht insgesamt sortieren.
Wir wollen nur das k-größte Element haben einer Liste.
Also das größte oder kleinste oder fünftgrößte oder was immer.
Das hatte ich ja schon mal definiert.
K von S gleich SJ mit J aus N.
Das heißt, wenn das das k-größte ist, dann gibt es k-1 Elemente, die
kleiner gleich sind.
Ich habe das jetzt richtig gemacht.
I aus N, Si, die Menge aller Indizes, bei denen Si größer als SJ ist.
Oder Si ist gleich SJ, aber die Position von I ist größer als J, ist k
-1.
Das heißt, in der sortierten Reihenfolge ist mein Element SJ hier
irgendwo angeordnet.
Und es sind genau diese k-1 Elemente größer als das SJ.
Das steht hier, Si ist größer als SJ.
Oder sie sind in einer anderen Position.
Dann ist das das k-größte Element.
Wenn ich mir diese Folge anschaue, die hier als Beispiel angegeben
ist, ist das größte Element offensichtlich die 27.
Das sechste größte Element...
Ich muss mal kurz mal durchgucken.
27, 7, 6, dann haben wir die 4, dann haben wir 3 und 3, dann ist das
sechsgrößte Element die 3.
Und das neuntgrößte Element in dem Fall ist die 1.
Und das elfgrößte ist auch die 1.
Wir haben hier drei Einsen drin.
Und das ist einfach diese Anordnung, ganz einfach.
Spezialfall ist der Median, der ist am schwierigsten zu bestimmen.
Ob ich also jetzt das Größte oder Kleinste bestimme, hat den gleichen
Aufwand.
Zwei Größte oder zwei Kleinste, auch gleicher Aufwand, relativ
einfach.
Aber der Median, das ist relativ schwierig, das mittlere Element
wirklich zu bestimmen.
Das heißt, ich muss mir wirklich ein Element angucken, bei dem die
Hälfte der Elemente größer ist.
Und wenn ich also den Median habe, einer Folge der Länge 5 in dem
Fall, hier bei dieser Folge ist das offensichtlich die 3, das
drittgrößte Element.
Folge der Länge 5, 5 durch 2 ist 2,5, nächstgrößere Zahl ist die 3.
Dann habe ich hier also das dritte Element.
In diesem Fall brauche ich das mittlere Element, da habe ich auch 5
Elemente.
Das drittgrößte Element in dem Fall ist die 1.
Und hier habe ich 4 Elemente, da muss ich das zweitgrößte Element
nehmen, das ist in dem Fall die 5.
Und so kann man also den Median definieren.
Sie wissen, dass der Median ungleich dem Mittelwert ist.
Das ist ganz wichtig, das klar zu machen.
Wenn ich also von mittleren Studienzeiten rede, dann ist es besser,
den Median zu nehmen, um zu sagen, mindestens die Hälfte der
Studierenden ist in der Zeit tatsächlich fertig.
Wenn ich den Mittelwert nehme, kann es sein, dass einige wenige
Langzeitstudierende den Wert nach oben schieben.
Und wenn ich jetzt selektieren will, kann ich das auch
unterschiedlicher Art und Weise machen.
Wir wollen also jetzt das k-größte Element bestimmen, vielleicht auch
den Median.
Das kann ich so machen, wenn ich das k-größte Element bestimmen
möchte, dass ich nacheinander das größte, zweitgrößte, drittgrößte
usw.
bestimme, bis ich das k-größte bestimmen kann, dadurch, dass ich die k
-1 größeren rausgenommen habe.
Das ist aber ein Aufwand.
k-1 mal Maximum bestimmen, k-1 mal linearer Aufwand.
Oder, wenn das k größer als 1,5 ist, nehme ich immer das Minimum.
Einfach von einer anderen Richtung angeguckt.
Das ist für das zweitgrößte vielleicht noch in Ordnung.
Für das drittgrößte, wenn ich den Median bestimmen will, hätte ich auf
einmal n,5 mal n Aufwand, wäre quadratischer Aufwand.
Also die Anzahl der Vergleiche dafür wäre im schlechtesten Fall
quadratisch.
Wenn ich den Median z.B.
bestimmen möchte, mit dem Verfahren.
Sicherlich schlecht, denn ich kann ja einfach sagen, ich sortiere
einfach, dann kann ich anschließend, egal welche Rangordnung mich
interessiert, ich nehme einfach das entsprechende, das mir drauf ist.
Aber kein Aufwand mehr.
Da ich ein n log n sortieren kann, ist also der maximale Aufwand, den
ich treiben muss, für Selektion n log n.
Das interessante ist, dass man das besser machen kann.
Ich will ja eigentlich gar nicht alles sortieren.
Und es ist tatsächlich so, man kann in linearer Zeit den Median
bestimmen.
Ja, also geht es besser, kann ich sofort beantworten, es geht.
Und ein einfacher Ansatz, den können wir uns ganz schnell noch
angucken, dann sind wir gleich fertig.
Quick Select.
Quick Sort kennen Sie.
Bei Quick Sort habe ich einfach nur immer bestimmt, habe ich also
irgendein Element hergenommen, das Pivot-Element, dann in meine Folge
entsprechend partitioniert und musste dann in beiden Folgen
weitermachen beim Sortieren.
Wenn ich Quick Select mache, dann partitioniere ich auch und
anschließend gucke ich einfach nach, wo muss ich weitersuchen nach dem
Cart -größten Element.
Also, das Cart-größte Element kann bereits dieses Element sein, das
ist der Fall Nummer 3.
Dann ist nämlich dieses Element C bereits das Cart-größte Element.
Wenn in diesem Bereich der größere der Elemente, die größer gleich
sind, wenn das mehr als K Elemente sind, dann weiß ich, das Cart
-größte Element liegt auf jeden Fall in diesem Bereich.
Links daneben.
Da muss ich nur da weitermachen.
Ich weiß, das kann gar nicht.
In dem Bereich liegen die kleineren, die interessieren mich ja gar
nicht mehr.
Ich muss also nur in einer Hälfte weitermachen.
Und wenn es der andere Fall ist, wenn hier links daneben weniger sind,
dann ist das Cart-größte Element irgendwo in diesem Bereich hier.
Dann muss ich da weitersuchen, aber nicht mehr nach dem Cart-größten,
sondern nach dem K-Betrag von S-größten Element.
Und das heißt, in jedem Fall muss ich nur in einer der beiden Folgen
dann weitersuchen.
Und wenn ich das analysiere, dann habe ich also hier anzugucken, das
Maximum der Vergleiche, die ich machen muss, um in einer der beiden
Teilfolgen weiterzusuchen.
Das können aber im Prinzip, weil ich ja nicht weiß, wo das Element C
hinkommt, kann das eine beliebig große Folge sein.
Und ich bekomme, wie bei Quicksort auch, für den schlechtesten Fall,
nur eine Reduktion der Liste um Länge 1.
Dann habe ich leider n².
Wenn ich aber jedes Mal optimal aufteile, dann habe ich ja nur den
Aufwand für n½ plus linearen Aufwand für die Partitionierung und
Aufwand für n½ plus Partitionierung.
Dann habe ich genauso eine Formel.
T von n ist dann gleich so in etwa T von n½ plus O von n.
Und da wissen wir, das liegt in O von n.
Also ganz einfach.
Das heißt, mit Quickselect habe ich ein bestes Verhalten in der Zeit,
das heißt also nicht mittleres, sondern bestes Verhalten in linearer
Zeit.
Und tatsächlich auch im Mittel, und das ist etwas, was man in der
Übung machen könnte, ist, weiß ich nicht, war glaube ich diesmal nicht
mehr drin, aber kann man sich leicht überlegen.
Die Überlegung, die ich gemacht hatte auf der einen Folie für
Quicksort, kann man hier für Quickselect machen und kriegt raus, das
Verhalten liegt insgesamt in O von n.
Das heißt, da habe ich mittleres Verhalten, das linear ist.
Also eine Verbesserung.
Und das nächste Verfahren, was ich Ihnen in der nächsten Woche
vorstellen werde, ist ein Verfahren, bei dem wir diese Partitionierung
so machen, dass der schlechte Fall niemals auftritt.
Das heißt, wir werden so partitionieren oder so Elemente aussuchen,
als Pivot-Elemente, dass ich garantiert immer einen festen Bruchteil
meiner Folge wegwerfen kann.
Und das ist dann das Verfahren, das hier auf der nächsten Folie kommt.
Das ist dieses Bild.
Ich werde also wissen, dass ich entweder den Teil rauswerfen kann,
oder den Teil rauswerfen kann, also etwa ein Viertel der Elemente
rauswerfen kann, bei jedem Rekursionsschritt von dem Klick-Select.
Und wenn ich das machen kann, dann habe ich immer einen gutartigen
Fall bei der Rekursion und komme insgesamt auf lineare Zeilen.
Das ist also das Verfahren dann, was man hier als lineare
Medienalgorithmus bezeichnet.
Das war's für heute, vielen Dank.
So, schönen Tag.
Ich begrüße Sie zur Fortsetzung der Vorlesung Effiziente Algorithmen.
Und ja, es sind wie üblich nicht sehr viele Studenten da, aber
immerhin einige.
Und ich freue mich immer, sie zu sehen.
Das habe ich schon oft gesagt.
Vor dem Aufzeigen sollte ich eigentlich nicht dazu führen, dass nur
noch sehr wenige kommen.
Weil ich denke, dass ich schon so mit einem direkten Ansehen
eigentlich anders Sachen vermitteln kann.
Aber das ist etwas, was Sie selbst entscheiden müssen.
Letztes Mal haben wir uns beschäftigt mit den Sortierverfahren.
Und wir waren also schon deutlich weiter als hier.
Das ist natürlich jetzt die erste Folie.
Wir haben uns einiges angeguckt.
Wir hatten, nachdem wir ja die einfachen Verfahren, was wir davor
schon angeguckt hatten, da hatten wir uns noch mit Bubble Sort
beschäftigt, mit der Korrektheit von Bubble Sort, bzw.
von Optimal Transposition Sort natürlich, der parallelen Variante.
Ich hatte Sie auch darauf hingewiesen, dass das für bestimmte
parallele Modelle ein optimales Verfahren sein kann.
Wir hatten dann Quicksort betrachtet, ein Verfahren, das Sie schon
lange kennen.
Und hatten gesehen, wie hier die Zeitkomplexität ist.
Hätte Ihnen dann auch das mittlere Verhalten kurz dargestellt, wie man
das nachweisen kann, dass wir hier auf N log N kommen, weswegen der
Name Quicksort auch wirklich berechtigt ist.
Und hatten dann uns mit Merge Sort beschäftigt, als eigentlich ein
Muster für eine ganze Vielzahl von Algorithmen, insbesondere wenn man
sie parallel ausführt, weil es dann eben darum geht, wie kann ich das
Mergen, also das Verschmelzen von zwei Listen eigentlich machen.
Das Schöne ist, dass ich eben hier viele, ganz nach dem Konker-Ansatz,
und zwar nach einer ganz strengen Anwendung, immer schön hälftig
aufteilen, viele Teilprobleme parallel bearbeiten kann, immer diese
Merge -Probleme bearbeiten kann.
Wir hatten gesehen, dass man das mit diesem Odd-Even Merge machen
kann, wo man die Elemente an den geraden und ungeraden Positionen der
beiden zu verschmelzenden Teilproben sich hernimmt und dann
entsprechend iterativ weiter bearbeitet und am Ende nur noch eine
kleine Zeile von Vergleichen ausführt, was dann rekursiv dazu führt,
dass wir dieses Bild haben von Vergleicherstrukturen für so ein Odd
-Even Merge und das halt mit Log N Stufen, in denen jeweils eine ganze
Reihe Vergleiche parallel ausgeführt werden.
Ich hatte Ihnen insbesondere letztes Mal auch das 0-1-Prinzip
vorgestellt, wesentliche Technik, um sich von der Korrektheit von
Algorithmen zu überzeugen, bei denen es also um Sortieren geht.
Und das ist halt eine ganz entscheidende Vereinfachung des Aufwandes,
um sich davon zu überzeugen, dass ein Verfahren richtig ist.
Man kann übrigens sogar noch die Anzahl der Folgen, die man betrachten
muss, reduzieren, weil sich einige dieser 0-1-Folgen überdecken.
Das heißt, wenn ich mir bestimmte 0-1-Folgen angucke, kann es sein,
dass damit schon eine gewisse Menge von anderen 0-1-Folgen abgedeckt
ist.
Das ist eine ganz interessante Tatsache.
Also man kann das sogar um den Faktor Wurzeln noch reduzieren, wenn
man sich das genauer anguckt.
Also das Wesentliche ist, wir können uns darauf beschränken, die 0-1
-Folgen zu betrachten.
Das hatte ich an hier gemacht, auch bei Tonicsort.
Wobei Tonicsort eben ein Sortierverfahren ist, auf so schon ziemlich
stark vorsortierten Folgen, aber eben nicht vollständig, sondern
dieses bitonische Aufsteigen und Absteigen zyklisch verschoben.
Wir hatten gesehen, dass man das dann einsetzen kann, nachdem wir uns
von der Korrektheit überzeugt hatten, um zwei Folgen zu mischen, bei
denen man einfach das bei Tonicsort verwendet und nur die erste Stufe
logisch etwas verändert, indem man die rechte Teilfolge einfach als
vertauschte oder gespiegelte Folge betrachtet.
Und wenn man die halt gespiegelt betrachtet, hätte man eine bitonische
Folge.
Das heißt, das bei Tonicsort kann hier für das Mischen von zwei Folgen
eingesetzt werden.
Und so kommt man dann auf das bei Tonicsort, das war hier am Ende bei
Tonicsort, dann auch Größenordnung Block Quadrat N, mit etwas mehr
Vergleichen als bei dem Odd-Even-Merge.
Ich wollte Ihnen eigentlich dadurch am Wesentlichen zeigen, welche
verschiedenen Ansätze das gibt, dass es also viele Varianten gibt für
parallele Sortierverfahren.
Was man hier auf jeden Fall sieht, ist, dass das hier deutlich
systematischer, also das ist einfach ein Muster, das sich immer
wiederholt.
Diese Vergleiche sieht man bei diesem Bildchen noch deutlicher, dass
man eben hier zunächst mal so eine Stufe hat, wo man Elemente mit
einem Abstand in Halbe miteinander vergleicht, dann Abstand in
Viertel, in Achtel und so weiter.
Also immer die Abstände der Elemente, die verglichen werden, geht um
die Hälfte runter.
Und es werden halt alle diese Elemente verglichen, anders als bei dem
Odd -Even-Merge.
Da war die Anzahl der Vergleiche etwas reduziert.
Aber es sah nicht ganz so hübsch systematisch aus, wie bei dem, was
wir beim Batonic Sort machen.
Und das nächste ist dann diese Folie gewesen, das war die letzte, mit
der ich mich länger beschäftigt habe letztes Mal.
Das Sortieren im zweidimensionalen Feld.
Und hier haben wir uns zunächst mal überlegt, wenn wir zweidimensional
sortieren, da müssen wir uns überlegen, wie wollen wir eigentlich die
Elemente anordnen.
Dazu muss man sich einfach überlegen, was ist eine sinnvolle
Sortiereinfolge.
Man kann sich irgendeine Einfolge hernehmen, muss dann dafür sorgen,
dass anschließend die Elemente auch wirklich in dieser Anordnung
aufsteigend sortiert sind.
Und das, was man eben standardmäßig macht, ist entweder zeilenweise
oder zeilenweise in Schlangenlinien.
Und wir hatten dann überlegt, dass wir diese beiden Fälle, man eine
sehr einfache, rundere Schalte bekommt, indem man einfach annimmt,
dass die Elemente an den beiden Ecken miteinander vertauscht werden
müssen.
Und damit die richtige Größenreihenfolge hergestellt ist.
Und dann hat man halt sofort eine untere Schranke von 2n-2, wobei n
die Kantenlänge des zweidimensionalen Feldes ist.
Also das ist eine ganz einfache untere Schranke.
Und jetzt zeige ich Ihnen eben dieses Verfahren LSO3-Sort, das ich
letztes Mal schon ganz kurz einmal gezeigt habe.
Ein Verfahren, das systematisch Folgen sortiert.
Im Prinzip wieder nach Merge Sort Prinzip.
Allerdings hier nicht in zweifaches Merge, sondern ein Vierfach-Merge.
Ich habe also vier Quadranten.
Diese wechseln wir auf den Pfeil.
Quatsch, auf den Stift, nicht auf den Pfeil, nach dem Stift.
Und Sie sehen, hier habe ich also diese vier Quadranten.
Eins, zwei, drei, vier, die jetzt jeweils vorsortiert sind in
Schlangenlinien.
Und die sollen verschmolzen werden zu einem in Schlangenlinien
sortierten Feld.
Also Annahme ist, wir müssen in Schlangenlinien sortieren, machen das
rekursiv und nehmen einfach an, wir haben schon die vier Quadranten
soweit sortiert.
Nun ist die Frage, wie kann man ein Merge machen mit vier Teilfolgen
auf so einem zweidimensionalen Feld.
Und dazu haben wir uns halt ein sehr schönes und ein sehr einfaches
Verfahren ausgedacht.
Es ist nicht das optimale Verfahren, um auf zweidimensionalen Feldern
zu sortieren.
Ich werde darauf später nochmal ganz kurz eingehen, was das optimale
Verfahren ist.
Aber es ist ein sehr einfach strukturiertes und trotzdem auch recht
schnelles Verfahren.
Also was machen wir hier?
Wir fangen an mit einem Perfect Shuffle in jeder Zeile des Feldes.
Wenn man ein Perfect Shuffle macht, wissen Sie, in jeder Zeile des
Feldes heißt das, ich nehme also hier die Elemente von der linken und
der rechten Hälfte her und habe dann halt hier jeweils im Prinzip ein
Element von links, rechts, links, rechts und so weiter, links, rechts.
Die sind einfach dann schön ineinander verschoben, ein bisschen
perfektes Mischen, die werden ineinander verschränkt.
Jetzt habe ich also nebeneinander immer Elemente aus der linken und
der rechten Hälfte.
Und das heißt, wenn ich mir anschaue, das was in so zwei nebeneinander
liegenden Zeilen drin ist, dann sehen wir, dass dort, das waren ja
Elemente aus den vier Quadranten.
Das ist eine Spalte aus dem linken Quadranten und eine Spalte aus dem
rechten Quadrant.
Das ist einfach die Idee, wir machen also im Prinzip, ist das so, wir
legen jetzt schon mal Elemente nebeneinander, aus jeweils linken und
rechten Quadranten, verschmelzen also das, eigentlich ist das jetzt so
eine Vorbereitung für ein Zweifachmört.
Wir haben jetzt in der ganzen Spalte eigentlich jetzt aus den vier
Quadranten Elemente drin liegen.
Und die Idee ist, dass wir das jetzt ausnutzen und sortieren jede
Doppelspalte, in der also Elemente aus den vier Quadranten drin sind,
in Schlangenlinien von oben nach unten aufsteigen.
Das ist, wir wissen, wie man das machen kann, zum Beispiel mit OETS,
man kann irgendein Verfahren nehmen.
OETS ist ein Verfahren, wissen wir, der arbeitet mit lokalen
Operationen.
Das kann man hier sicherlich anwenden.
Das heißt, die Operationen, die ich machen müsste, wären so, dass ich,
also ich mache mal jetzt hier normal das nebeneinander ein, ich müsste
also Vergleiche machen, die abwechselnd von links nach rechts laufen.
Das wäre ein Schritt, das wäre meinetwegen, wenn wir sagen, das ist
der OTT-Schritt, das erste Paar, 1, 2, die werden miteinander
verglichen.
Und in dem EVEN-Schritt würde ich also im Prinzip da einen Vergleich
haben, da einen Vergleich, da einen Vergleich, da einen Vergleich.
Das ist jetzt einfach so in den nebeneinander liegenden Doppelspalten
dargestellt, was in zwei aufeinanderfolgenden Schritten passiert bei
dem OETS, wenn man das so auf Doppelspalten ausführt.
Also das heißt, wir würden dort, wenn wir OETS machen, abwechselnd
Vergleiche machen in den jeweils nebeneinanderliegenden Elementen in
diesen Zeilen.
Und zwar einmal links nach rechts, also das Maximum nach rechts und in
der Zeile drunter Maximum nach links.
Schön schlangenlinienartig, alternierend aufsteigen, absteigen.
Und dann eben nach unten, jeweils am rechten und am linken Rand.
Muss ja schlangenlinienweit sein.
Das ist also einfach das OETS-Prinzip übertragen auf dieses Sortieren
in einer Schlangenlinie.
Und ich habe also einfach diese Reihenfolge, die ich dort haben
möchte, diese Schlangenlinienreihenfolge, guckt man sich an, und wie
mache ich da auch OETS?
Und dann kommt man auf genau diese Struktur, also dass man so eine
Schlangenlinie sortiert.
Und das Maximum soll dann eben da unten jeweils im Pfeil stehen, damit
klar ist, das ist aufsteigen, sortieren.
Jetzt haben wir etwas erreicht, dass diese Doppelspalten jeweils
sortiert sind.
Vorher waren sogar diese vier Quadranten schon sortiert.
Jetzt sind Doppelspalten sortiert.
Und jetzt kommt etwas, was so aussieht wie Magic, zwei Endschritte von
OETS.
xn ist die Kantenlänge meines Feldes.
Ich wende zwei Endschritte von OETS ein.
Zwei Endschritte reichen aus, um eine Folge der Länge 2n zu sortieren,
vollständig.
Hier habe ich aber eine Folge der Länge n².
Ich behaupte, mit zwei n Schritten kann ich das, was jetzt entstanden
ist nach diesem Sortieren in Doppelspalten, Schlangenlinien, dann ist
das Ganze, was rauskommt, vollständig sortiert.
Das ist zunächst mal nicht intuitiv klar.
Das heißt, ich gehe davon aus, der Sortiertheitsgrad, den ich habe,
der ist schon so groß, dass die maximalen Abstände zwischen nicht am
richtigen Platz befindlichen Elementen 2n sind.
Denn dann kann ich das in 2n Schritten tatsächlich hinbekommen.
Und das ist zuerst mal eine mutige Behauptung.
Wir werden es später sehen, dass man das mit dem 0-1-Prinzip sehr
einfach beweisen kann.
Aber das zunächst mal zu diesem Verfahren.
Drei einfache Schritte.
Perfect Shuffle.
Wissen Sie, wie das geht?
Einfach umordnende Elemente.
Das zweite, Doppelspalten sortieren, einfache Vergleiche.
Links, rechts, oben, unten.
Und schließlich nochmal wieder einfache Vergleiche.
Aber das eine Mal auf die Doppelspalten, das andere Mal auf der
gesamten Matrix als Schlangenlinie.
Also OITS auf diesem linearen Feld, das ihr so sich durch unser Feld
hindurchschlängelt.
Sodass wir am Ende dann tatsächlich ein vollständig sortiertes Feld
haben.
Ja, das ist also jetzt unser Verfahren.
Gucken wir uns erstmal an, was für einen Zeitaufwand das hat.
Wenn wir uns das jetzt überlegen, wie viel Zeit brauchen wir.
Der erste Schritt, Perfect Shuffle.
Das hatten wir bei dem Odd-Even-Merge so als, naja, das ist
eigentlich, braucht ja gar keine Zeit.
Wenn ich das auf einem zweidimensionalen Feld mache, braucht das schon
Zeit.
Ich arbeite nur mit lokalen Operationen.
Ich habe ja auf dem Feld nur hier meine direkten
Nachbarschaftsbeziehungen.
Also nur jeweils verbunden mit den vier direkten Nachbarn.
Da kann ich natürlich nicht beliebig die Elemente über das Feld hinweg
schieben.
Da muss ich sukzessive die Elemente miteinander verschränken.
Jetzt muss ich ja Elemente von der linken Seite, das ist hier die
linke Seite, das ist die rechte Seite, die muss ich nebeneinander
bringen.
Das heißt, ich muss das Element, das ist hier die Hälfte, hier ist
also links, da ist rechts.
Ich muss also das Element, was hier steht als erstes, das Element muss
an die zweite Position kommen.
Nachher soll hier ein Element stehen, eins von links, eins von rechts.
Also das erste Element hier, das was da steht, an der Position, das
muss anschließend hierhin kommen.
Wenn man sich das anschaut, dann mache ich hier einfach einige
Vertauschungen.
Lokale Vertauschungen, das sollen diese Doppelpeile andeuten.
Einfach nur lokale Vertauschungen.
Und dann wird natürlich das Element sukzessive nach dort
transportiert, nach dort transportiert, nach dort transportiert.
Und hier ist das erste, das alte linke Element.
Und das hier wäre praktisch dann, danach wäre hier also L1 und da
würde im Prinzip R1 stehen.
Wenn das hier dort R1 ist und das L1.
Das ist einfach eine Menge von solchen Vertauschungen.
Und das heißt, dieses Element wandert an die Position.
Das nächste Element wandert entsprechend auch hier rüber.
Und wenn Sie sich angucken, wie die Wege hier durch diese Vergleiche
oder diese Vertauschungen laufen, sehen Sie, dass ist genau das
Perfekte.
Da kann man sich leicht davon überzeugen.
Und ich brauche dafür N½-1 Takte, weil ich halt genau diese Distanz
überwinden muss.
Die Distanz von N½-1.
Nicht genau N½, dann wäre das R1 an die Position von L1 gekommen.
Wenn ich R1 und L1 verkaufe, das will ich ja gar nicht.
Ich will es neben das R1 kriegen und die Distanz ist gerade N½-1.
Und dann muss ich das OITS auf Folge Länge 2n anwenden.
Da wissen wir, dass das in 2n Takten immer wirklich ist.
Ich könnte sogar das mit einem Takt weniger machen, aber das ist jetzt
irrelevant.
Man kann das sogar noch etwas optimieren, weil man etwas weiß über die
Reihenfolge der Elemente, die da drin sind.
Und der Schritt 3 OITS, 2n Schritte von OITS, da steht ja gerade 2n,
also 2n Takte.
Und ich habe insgesamt 4,5n-1 Takte für diese 3 Schritte.
Das brauche ich also, also klein n, um n²-Elemente zu verschmelzen,
bzw.
4 Folgen zu verschmelzen, die jeweils n²-Viertel-Elemente haben.
Das also die Zeit, also 4,5n-1 Takte.
Und dann müssen wir später sehen, wie sich das dann bei einer
rekursiven Anwendung auf das Zeitverhalten auswirkt.
Aber das ist dann anschließend einfach nur eine übliche Anwendung
unserer Rekurrenzgleichen.
Also zum zeitlichen Ablauf, das ist glaube ich sehr einsichtig, dass
das genau diese Zeit ist.
Man kann das noch etwas reduzieren, aber das will ich jetzt hier
überschlagen.
Wichtig ist natürlich, sich anzugucken, warum ist das eigentlich
korrekt.
Und da muss man sich einfach Folgendes überlegen.
Wenn wir natürlich 0-1-Folgen betrachten, wir wollen es die Arbeit so
einfach wie möglich machen, also 0-1-Folgen, unten in dem grauen
Bereich 1n, im weißen Bereich jeweils 0.
Dann kann es unterschiedliche Situationen geben.
Auf jeden Fall ist es so, dass wir einige Zeilen haben werden, in
denen nur 1n stehen.
Und einige, in denen nur 0n stehen.
Und es wird eine Zeile geben, die eventuell 0n und 1n gemischt
enthält.
Denn diese vier Quadranten sind ja sortiert.
Wenn ich vier sortierte Teilfolgen habe, sind das erst 0n und dann 1n.
Und sie unterscheiden sich also durch die Anzahl der vollen 1-Zeilen
und durch die nicht sortierten Zeilen, in denen gerade der Übergang
von 0 auf 1 ist.
Und diese nicht sortierten Zeilen, in denen der Übergang von 0 auf 1
ist, die können auch noch unterschiedlich gerichtet sein.
Sie sehen hier, da geht das von 0 auf 1.
Auch wenn ich es so betrachte, kann ich es auch für Sie anders machen.
Hier geht es also von links nach rechts aufsteigend.
In dieser Zeile geht es von rechts nach links aufsteigend.
Hier ebenfalls von rechts nach links aufsteigend.
Da auch von rechts nach links aufsteigend.
Das ist ein wichtiger Effekt, den man sich genauer angucken muss.
Nach dem Schritt 2 habe ich jetzt zwei Situationen zu betrachten.
Schritt 2 war Sortieren der Doppelspalten.
Wenn ich die Doppelspalten sortiert habe, ich habe ja in meiner
Doppelspalte Elemente aus der linken und der rechten Hälfte, also
genau A, B, C und D, viele Einsen aus den ganzen Einszeilen.
Und dann habe ich eventuell noch weitere Einsen, weil ja hier diese
angefangenen Zeilen noch dazukommen.
Das kann sein, dass noch etwas dazukommt.
Das heißt, nehmen wir mal an, wir haben dieses E, die Anzahl der
Einszeilen, in...
Quatsch, wenn das E die Summe... Entschuldigung.
Das E ist die Summe dieser A plus B plus C plus D.
Die sind aufgeteilt auf zwei Zeilen.
Das muss ich in beiden Fällen betrachten, dass das E eine gerade Zahl
ist.
Dann habe ich diese Situation.
Ich habe hier, richtig schön, weil das gerade ist, kann ich die schön
aufteilen auf die zwei benachbarten Spalten.
Das sind jetzt die Einsen aus den vollen Einszeilen.
Und dann kann es sein, dass aus weiteren Zeilen, diesen nicht
vollständigen Einszeilen, noch eine Eins dazukommt.
Weil ich vier Quadranten habe, habe ich eben hier zwei weitere Zeilen,
in denen eventuell noch eine weitere Eins steht.
Bis zu vier.
Kann sein, dass gar keine auf da drin ist.
In der Situation, die wir hier haben, können Sie sich sofort angucken,
haben wir, egal welche Doppelspalte Sie sich anschauen, immer
mindestens eine Eins da drin.
Da tritt der Fall gar nicht auf, dass dort keine weitere Eins
dazukommt.
Also, die Höhe dieser vollen Einszeilen ist gerade die Hälfte von E.
Und da das jetzt maximal zwei Zeilen sind, in denen wir zwischen 0 und
4 Einsen haben, reichen 2N Schritte von OETS aus, um diesen Bereich
hier insgesamt zu sortieren.
Das ist eine Folge der Länge 2N, maximal Länge 2N, und von der weiß
ich, dass ich die mit 2N Schritten sortieren kann.
Der ganze Rest ist ja schon sortiert.
Das heißt, durch diese Überlegung mit den 0,1 Folgen, kann ich genau
mir angucken, wie groß ist der Bereich, in dem etwas unsortiert ist.
Und ich habe also hier nur einen Bereich, der maximal zwei Zeilen
umfasst, deswegen reichen die 2N Schritte aus.
Also das ist hier die einfache Konsequenz.
Natürlich weiß ich nicht, an welcher Stelle in meiner Matrix, in
meinem Feld, diese Unsortiertheit auftritt.
Deswegen muss ich eben das über das ganze Feld machen, aber ich weiß,
der Grad der Unsortiertheit, wenn ich das so bezeichne, das heißt, der
maximale Abstand zwischen den Elementen, die an der falschen Position
sind, der ist in diesem Fall 2N.
Das sind nur zwei Zeilen, die sortiert werden müssen.
Jetzt kommt der andere Fall, der ist ein bisschen komplizierter.
Wenn das ungerade ist, das E, dann klappt die Verteilung auf zwei
Spalten nicht so gleichmäßig, dann haben wir überall, also natürlich
auch wieder unsere Einsen, aber immer noch hier eine zusätzliche Eins
dazu, weil das E ja ungerade ist.
Also geht das nicht richtig auf.
Und jetzt kommen natürlich auch wieder 0 bis 4 Einsen dazu, aus diesen
angefangenen Einszeilen, aus den vier Quadranten.
Und das heißt, wenn ich jetzt 4 obendrauf lege, dann habe ich hier
einen Bereich von drei Zeilen, in denen Nullen und Einsen auftauchen
können, die noch nicht sortiert sind.
Wenn irgendwo 0 Elemente dazukommen, dann ist halt hier dieses hier
die Zeile, die noch nicht sortiert ist.
Wenn irgendwo 4 Elemente auftauchen, dann habe ich hier oben auch noch
eine Eins und Nullen daneben, also auch nicht sortiert, dann hätte ich
drei Zeilen, die sortiert werden müssen, da würden zwei Endschritte
nicht ausreichen.
Und nun muss ich mir das genauer angucken.
Was ist eigentlich, also wenn ich mir angucke, das E ist ungerade.
Warum ist das E ungerade?
Weil ich, ich muss ja angucken, ich habe dieses E ist die Summe von A,
B, C und D.
Das E kann nur ungerade sein, wenn ich eine, wenn also eines von A, B,
C und D ungerade ist, oder drei von denen ungerade sind.
Und was heißt es, dass das ungerade ist?
Oder gerade?
Das heißt, wenn das A gerade ist und das B ungerade, dann laufen diese
angefangenen Einszeilen in unterschiedlichen Richtungen.
Wenn die alle gerade sind oder alle ungerade, dann laufen die immer in
gleicher Richtung, diese angefangenen Einszeilen.
Aber das, was ich hier angedeutet habe, ist genau so ein Fall, dass
ich drei Richtungen habe, die laufen von links, also drei angefangene
Einszeilen, diese hier, die und diese hier, die laufen von rechts nach
links und die eine hier oben, der linken oberen Ecke, die läuft von
links nach rechts.
Das heißt, wir haben drei angefangene Einszeilen, die in der gleichen
Richtung laufen und eine läuft in der anderen Richtung.
Und jetzt nehmen wir an, es gibt eine Doppelspalte ohne zusätzliche
Eins.
Das tritt in diesem Beispiel hier nicht auf.
Damit irgendwo keine Eins auftaucht, müsste, also diese Zeile zum
Beispiel hier, müsste etwas weiter rechts die erste Eins haben.
Weil ich ja an den entsprechenden Stellen, hier sind nur Nullen, das
ist der Bereich mit Nullen, das sind Bereiche mit Nullen, das sind
Bereiche mit Nullen.
Damit ich also irgendwo einen Bereich habe, wo keine Eins dazukommt,
müssten diese Einsen hier weiter rechts liegen, als die erste Eins in
diesen angefangenen Einszeilen, die von rechts nach links laufen.
Wenn das aber so ist, dass diese Einsen weiter rechts liegen, dann
habe ich natürlich hier links davon, in dieser Zeile, nur Nullen
stehen.
Das heißt, nur drei andere Quadranten enthalten an diesen Positionen
zusätzliche Einsen.
Nämlich dort, dort und dort.
Das heißt, sobald ich eine Doppelspalte habe, ohne ein weiterer Eins
aus einer angefangenen Zeile, habe ich in allen Doppelspalten
höchstens drei Einsen stehen.
Wenn ich aber höchstens drei Einsen dort stehen habe, dann habe ich
nicht diese Situation, sondern dann habe ich die Situation, dass nur
in diesen beiden Zeilen noch Einsen auftauchen können.
Das heißt, ich habe nur zwei Zeilen, die nicht sortiert sind.
Perfekt.
Ich kann mit zwei Einsschritten sortieren.
Der nächste Fall ist, dass in jeder Doppelspalte mindestens eine
zusätzliche Eins steht.
Der erste war ja, ich nehme mal an, ich habe irgendwo keine.
Wenn das nicht der Fall ist, dann habe ich also überall mindestens
eine.
Wenn ich aber überall mindestens eine habe, dann habe ich hier
insgesamt Einsen stehen.
Weil überall mindestens eine Eins steht.
Und das heißt, die Unsortiertheit kann nur in diesem Bereich sein.
Die beiden darüber liegenden Zeilen.
Das sind auch wieder nur zwei.
Ich habe wieder die Situation, dass ich nur zwei Zeilen habe, in denen
Null und Eins irgendwie gemischt auftauchen.
Das heißt, auch hier reicht es aus, mit zwei N-Schritten zu sortieren.
Die zwei N-OTS-Schritte von Schritt 3 reichen aus, um vollständig
sortiert zu haben.
Das heißt, das Verfahren ist korrekt.
Wir haben nach diesen zwei N-Schritten eine sortierte Folge in unserem
zweidimensionalen Feld.
Und haben diese vier vorsortierten Quadranten erfolgreich gemischt zu
einer sortierten Folge.
Ich hoffe, dass das verständlich war.
Und ich glaube, Sie sehen hier, wie hilfreich es ist, sich auf Nullen
und Einsen beschränken zu können.
Wenn Sie da anders argumentieren müssten, über beliebige Folgen,
wünsche ich Ihnen viel Spaß.
Jetzt haben wir insgesamt also den Algorithmus LSO3-Sort.
Für N kleiner gleich 2 machen wir das Sortieren einfach durch einen
trivialen Algorithmus.
Sie können sich überlegen, wie viele Schritte Sie dafür brauchen.
Das geht also relativ einfach.
Das sind vier Elemente, die Sie sortieren müssen.
Ich möchte es wenigstens vergleichen.
Für N größer 2 wenden wir Rekursiv an.
Und das heißt, wir haben dann unsere übliche, also hier sage ich, N
kleiner gleich 4 Schritte.
Mit vier Schritten kriegen Sie das immer hin.
Wenn wir das jetzt Rekursiv anwenden, dann haben wir also hier diese
Abschätzung.
Das Verfahren angewandt auf die vier Teilfelder Rekursiv.
Danach sind sie sortiert.
Das mache ich parallel.
Deswegen T LSO3-Sort von N halbe.
Also auf einem N halbe Kreuz N halbe Feld.
Und danach noch 4,5 N.
Das Minus 1 habe ich hier weggelassen.
Ich habe also hier dieses N stehen.
Und da wissen wir sofort, naja, das ist ja entsprechend unserer
Rekurrenzgleichungskenntnisse dann eine Zeit, die ist kleiner gleich
tatsächlich 9N-14.
Kann man sich genau ausrechnen, dass das so ist.
Will ich jetzt gar nicht im Einzelnen Ihnen genau zeigen.
Das ist aber, kann man sich überlegen, dass das genau so hinkommt.
Dann haben wir hier 9N-14 oder Groß O von Wurzel aus Groß N.
Groß N ist ja Klein N Quadrat, also die Anzahl der Elemente, die
sortiert werden sollen.
Das heißt, wir können jetzt auf dem zweidimensionalen Feld in Wurzel N
sortieren.
Man kann dieses Verfahren, wenn man also genau die Vorsortiertheit der
einzelnen Bereiche sich anguckt, kann man das auf 7N verbessern.
Das ist schon, das ist also dann auch wieder etwas schneller.
Wir hatten gesehen, die untere Schranke, das Triviale ist 2N-2.
Wir sind also hier Faktor, naja, 4 bis 5 so etwa.
Größenordnung Faktor 4 sind wir weg von der trivialen unteren
Schranke.
Jetzt kann man, das werden wir gleich sehen, eine untere Schranke
zeigen von 3N.
Minus Klein O von N, also irgendein marginaler Term.
Das heißt, 3N ist tatsächlich eine untere Schranke für Sortieren auf
solchen zweidimensionalen Feldern.
Und da sind wir also nur noch ein Faktor etwas mehr als 2 weg von dem
Optimum.
Wir hatten schon mal so einen Fall bei der Auswirkung von Polynomen,
wo wir ganz eng dran waren, da sogar scharf auf dem Optimum.
Hier sind wir also relativ nah dran.
Und es gibt tatsächlich ein Sortierverfahren, das in 3N läuft.
Da gehe ich auch nachher nochmal drauf ein, nur kurze Bemerkung dazu,
dass dieses beste Sortierverfahren ist sogar veröffentlicht worden,
bevor wir uns den LSO3-Sortalgorithmus ausgedacht haben.
Und es gab gleichzeitig mehrere andere Sortierverfahren, die auch auf
zweidimensionalen Feldern gearbeitet haben, die auch ähnliche Zeiten
ausgekriegt haben, völlig unterschiedliche Ansätze.
Und dass das andere Verfahren in Zeit 3N gelaufen ist, war da gar
nicht so richtig klar geworden, weil die in der Veröffentlichung
darauf hingewiesen, oder da haben sie angenommen, dass sie auf einem
SEMD -Rechner arbeiten.
Wenn ich auf einem SEMD-Rechner arbeite und ich habe zum Beispiel
hier, ich möchte gerne solch einen Vergleich machen, dann muss ich
erstmal ein Element vom rechten Nachbarn lesen, dann muss ich die
Elemente vergleichen und ich muss das Maximum nach rechts schreiben.
Das sind drei Schritte.
Auf dem SEMD-Rechner.
Weil ich ja, es war so aufgeteilt, das sind die einzelnen Operationen.
Und so haben die das analysiert und kamen dann mit einer relativ hohen
Konstanten raus, aber bezogen auf den Aufwand, den man auf einem SEMD
-Rechner hat.
Wir haben gesagt, wir haben einen MEMD-Rechner, bei dem ich zum
Beispiel auch sowas machen kann, dass ich in übereinanderliegenden
Elementen einmal so und in den runterliegenden Zeilen so etwas machen
kann.
Das sind unterschiedliche Operationen.
Der eine liest von rechts, der andere liest von links.
Also insofern muss man genau aufpassen, was für ein Modell liegt
eigentlich dahinter.
Und weil die das so analysiert haben, das aber nicht so richtig
deutlich war, wenn man das so etwas oberflächlich gelesen hat.
Und dazu noch kam, dass die einen Beweis gemacht haben für die
Korrektheit, eine Argumentation für die Korrektheit, ohne Rückgriff
auf das 0-1-Prinzip, war dieser Artikel, in dem das veröffentlicht
wurde, nur sehr schwer wirklich zu lesen und zu verstehen und
nachzuvollziehen.
Die Korrektheit des Verfahrens.
Die haben übrigens dort eine andere Aufteilung gemacht, die haben dort
eine wesentlich feinere Aufteilung gemacht, die haben ein sogenanntes
S -Quadrat-Way-Merge gemacht, wobei S also ein Wurzel aus kleinen N
ist.
Also ein wesentlich feineres Merge gemacht.
Ein sehr interessantes Verfahren, ist optimal und auch schon vor der
Zeit veröffentlicht, als wir unser Verfahren veröffentlicht haben,
aber unser Verfahren ist von der Struktur her wesentlich einfacher und
auch nicht so weit weg von dem Optimum.
Also insofern muss man immer aufpassen, in welche Richtung man
argumentiert.
Also, ich hoffe, Sie haben das Verfahren verstanden, es ist relativ
einfach, Korrektheit kann man sich leicht überlegen über 0-1-Prinzip
und jetzt will ich Ihnen zeigen, warum 3N eine untere Schranke ist.
Und ich will Ihnen das zeigen, weil dabei auch wieder eine
Beweistechnik drin ist, die sehr interessant ist, die mein Kollege
Manfred Kunde entwickelt hat.
Und es geht also darum, dass wir ein zweidimensionales Feld haben, in
dem wir sortieren wollen, das heißt, jedes Element unseres Feldes
enthält ein Datum, das sortiert werden soll, also das in die richtige
Reihenfolge gebracht werden muss und wir haben eine gewisse Anzahl Z
von Zeilen, eine gewisse Anzahl S von Spalten.
Muss also nicht notwendigerweise quadratisch sein, kann auch irgendwie
rechteckig sein.
Wir wollen sortieren, deswegen nehmen wir an, wir haben eine geordnete
Datenmenge D und wir nehmen an, dass die Datenmenge groß genug ist.
Kommt wahrscheinlich erst auf der nächsten Folie.
Also ich nehme an, dass ich auf jeden Fall mindestens N² Elemente
habe, wenn auch ein bisschen mehr.
Ich nehme an, dass ich zu Beginn in jedem Feldelement ein Datum aus D
im Kommunikationsregister habe.
Also dieser Punkt soll das Kommunikationsregister andeuten, das ich
mit dem anderen vergleichen kann.
Und in jedem Takt kann jeder Prozessor die Inhalte seiner vier
Nachbarn lesen, kann beliebige Operationen ausführen und seinen
eigenen Speicherbereich verändern.
Die Inhalte der Kommunikationsregister nehmen wir an, seien
zeilenweise oder zeilenweise in Schlangenlinien zu sortieren.
Muss ja fast jetzt über alle beliebigen Algorithmen aussagen.
Und das sind jetzt die Einschränkungen für meine Algorithmen.
Wir wissen, die triviale untere Schranke ist s±z-2, das war dieses 2n
-2.
Wenn ich eben etwas von dort nach dort bringen muss, dann habe ich
genau dieses s±z-2 als Distanz zu überwinden durch lokale Operationen.
Das sind allein die Schritte, um das dorthin zu transportieren, sind
s±z -2.
Und jetzt wollen wir uns das nicht trivial angucken und nehmen dafür
an, dass wir mindestens zwei n²-Elemente haben.
Und zur Vereinfachung, bzw.
2 · s · z.
Zur Vereinfachung nehmen wir an, das sind gerade Elemente aus dem
Bereich –n² bis n².
Das heißt, ich nehme an, ich habe negative Elemente und positive
Elemente dort drin in dem D, über die ich argumentieren kann.
Und ich nehme an, dass meine Anfangsbelegung so ist, dass genau die
Elemente von 1 bis n² in meinem Feld drinstehen.
In irgendeiner Anordnung, irgendeiner Kommutation der Elemente von 1
bis n².
So.
Und die wesentliche Idee sieht jetzt so aus.
Ich betrachte einen gewissen Bereich meines Feldes, eine Jokerzone,
die jetzt hier blau markiert ist, und untersuche, wie die
Anfangsbelegung dieser Zone den Sortiervorgang beeinflusst.
Das heißt, ich schaue mir an einen bestimmten Bereich und schaue mir
an, wie dieser Bereich den Sortiervorgang beeinflusst.
Und die Idee ist folgende.
Ich möchte gerne einen schlechten Fall konstruieren für ein
Algorithmus.
Ich möchte zeigen, egal welchen Algorithmus ich wähle, ich kann eine
Eingabefolge konstruieren, die schlecht ist, also schwierig ist für
diesen Algorithmus, weil gewisse Informationen erstmal aus diesem
unteren Bereich, der hier angegeben ist, woanders hinwandern müssen,
damit dort etwas richtig passieren kann.
Das heißt, ich schaue mir an, wie beeinflussen die Elemente, die in
diesem blauen Bereich liegen, die Endposition der Elemente in der zu
sortierenden Folge.
Und ich möchte praktisch durch die Elemente in dem blauen Bereich
dafür sorgen, dass die Zeit fürs Sortieren möglichst lang ist.
Und das wird nun wie folgt gemacht, das werden Sie gleich sehen.
Wir nehmen also hier dieses dreieckige Bereich, sodass hier mindestens
zwei s-Elemente liegen.
s ist die Anzahl der Spalten, z ist die Anzahl der Zeilen.
Wenn ich hier mindestens zweimal Wurzel-s-Elemente als Kantenlänge
habe, dann habe ich also mindestens zwei s-Elemente dort in dem blauen
Feld.
Und zwei s-Elemente sind genauso viel wie Elemente, die in zwei Zeilen
enthalten sind.
Das heißt, ich muss mindestens so viele Elemente in der dreieckigen
Zone haben, wie ich in zwei Zeilen anordnen kann.
Das ist die Idee dahinter.
Und für die Anfangsbelegung nehme ich mal an, dass die Elemente in der
Joker -Zone größer sind als alle anderen.
Kann ich ja problemlos hinkriegen, das ist eine spezielle
Anfangsfolge.
Das macht ja etwas, was für beliebige Folgen gelten soll.
Das nehme ich also hier an, so beliebiges Sortierverfahren sort.
Und jetzt kommt hier noch eine weitere Annahme.
Ich nehme an, dass nach jedem Schritt jeder Prozessor genau ein
Element der zu sortierenden Folge enthält.
Also keiner kann sich die ganze Folge irgendwie reinschreiben.
Und dann machen wir jetzt folgende Überlegung.
Wie lange dauert es, bis Information aus diesem Bereich, aus der Joker
-Zone, an dieser Stelle hier oben, links oben, irgendeine Wirkung
entfalten kann.
In jedem Schritt mache ich eine Operation, bei der ich irgendwie
Elemente miteinander vergleiche.
Also ich lese etwas rechts oder ich lese etwas unten.
Und dadurch, dass ich etwas unten oder rechts lese, wird Information
nach links bzw.
nach oben bewegt.
Das heißt, sukzessive wandert die Information in diese Richtung, die
durch den Pfeil angedeutet ist.
Und irgendwann habe ich genügend Schritte ausgeführt, damit die
Elemente aus der Joker-Zone eine Wirkung entfalten können, auf das
Element hier oben, an der Position.
Jetzt muss ich mir nur angucken, wie weit ist diese Distanz.
Da muss ich mir diese Entfernung angucken plus die Entfernung.
Ich habe ein zweidimensionales Gitter, habe also einfach eine
Manhattan -Distanz, die Differenz der Koordinaten.
Das ist für alle Punkte, die auf dieser Linie hier liegen, die gleiche
Distanz.
Das heißt, das ist genau das, was ich mir angucken muss.
Und wie viel habe ich dort drin?
Zwei Wurzel S war dieser Bereich hier.
Das heißt, ich muss Z-2 Wurzel S, das ist dieses Stück, nach oben
wandern.
Und die horizontale Distanz hier, das ist gerade S-1.
Das heißt, nach Z-2 Wurzel S plus S-1 Takten, habe ich das erste Mal
eine Operation, bei der ein Element aus der blauen Zone mit involviert
sein kann.
Das vielleicht auf dem Weg dahin gewandert ist, durch diese
Vergleiche, die gemacht wurden.
Oder ich kann sagen, dass Informationen dorthin gewandert sein können.
Davor kann das, was da oben passiert, überhaupt nicht beeinflusst
worden sein, durch das, was in der blauen Zone passiert.
Und ich nehme an, dass in dem Takt, in dem das erste Mal Information
aus der blauen Joker-Zone eine Rolle spielt, ein Element A dort drin
steht.
Das muss nicht das Element sein, das zu Anfang dort drin stand.
Da sind ja schon alle möglichen Vergleiche gemacht worden oder alle
möglichen Operationen.
Aber in dem Takt, im Takt Z-2 Wurzel S plus S-1, steht dort ein
Element A drin.
Das stammt mit Sicherheit nicht aus der Joker-Zone.
Und jetzt schaue ich mir an, was passiert bis zum endgültigen
Sortieren.
Bis zum endgültigen Sortieren muss ja dieses Element irgendwo
hinwandern.
Das wird ja irgendwo hin sortiert durch die nachfolgenden Schritte und
ist dann irgendwann an der endgültigen Position angelangt.
Die kann irgendwo sein.
Und jetzt kommt die Idee mit der Joker-Zone zur Geltung.
Jetzt möchte ich dafür sorgen, dass diese Position, an die das Element
A am Ende bewegt wird, möglichst weit weg liegt von der Position, an
der das A war, als es von der Information aus der Joker-Zone
beeinflusst wurde.
Das heißt, möglichst weit weg von dieser linken oberen Ecke.
Ich habe zwei S-Elemente zur Verfügung.
Der maximale Ort, zu dem ich das bewegen kann, wäre also irgendwo da
rechts.
Weiter kann ich das nicht bewegen.
Wie kann ich das bewegen?
Dadurch, dass ich die Elemente aus der Joker-Zone so verändere in der
Größe, dass das Element nach rechts wandern muss.
Sogar nach rechts und noch in die Zeile weiter drunter.
Es könnte aber sein, dass diese Position hier, ich möchte das Ganze
nach rechts bewegen, also die Position soll nachher, und zwar sollen
kleinere Elemente davor kommen.
Ich möchte das Element einfach verschieben, durch kleinere Elemente,
und muss die Frage, in was für einer Zeile ist dieses Element an der
Position, wo es am Ende gelangt war, geht das hier aufsteigend oder
geht das absteigend?
Das heißt, ich mache ja Schlangenlinien-Sortierung, und dann kann es
sein, wenn ich jetzt kleinere Elemente dazu laufen lasse, dann wird ja
das Element weiter nach oben kommen, dann bekommt es eine höhere
Rangposition, und läuft dann aber erstmal nach links.
Und dann muss ich es ja erstmal hier ganz rum bewegen, bis es dann
irgendwann dort rechts hinkommt.
Das heißt, das wäre ein Fall, da muss ich das ganz rum bewegen, dazu
brauche ich diese 2S-Elemente, nicht ganz 2S, eigentlich reichen 2S-1
aus, aber immerhin, ich muss es eventuell über zwei Zeilen oder fast
zwei Zeilen hinweg bewegen.
Und deswegen brauche ich so viele Elemente.
Und das mache ich so, dass ich also die Elemente in der Joker-Zone,
oder ich suche jetzt eine Folge, bei der abhängig von dem Element, was
dort stand, halt die endgültige Position von dem A garantiert ganz
rechts ist.
Und dadurch weiß ich, wenn ich zunächst mal, wenn das A zunächst mal
hier oben links war, und anschließend ganz nach rechts gewandert ist,
wie es jetzt hier zu sehen ist, dann habe ich nach diesen Z-2-Wurzel-S
-S -1-Takten nochmal mindestens diese Distanz zu überwinden, also
mindestens S-1.
Und damit kann ich also dazu nochmal S-1 draufaddieren und bekomme
dann insgesamt, wenn ich das jetzt hier mir angucke als untere
Schranke, Z-plus-2-S-minus-2-Wurzel-S-minus-2.
Ja, das sind nochmal diese S-minus-1 dazugezählt, zu diesem
Anfangsweg, bis wir das Element oben links beeinflusst haben.
Und das heißt, das sind insgesamt Z-plus-2-S-minus-groß-O-von-Wurzel
-S, das ist dieses klein O-von-N, was ich im Prinzip ignorieren kann.
Marginal kleiner Term.
Das heißt, meine untere Schranke ist Z-plus-2-S.
Und wenn ich jetzt S-gleich-Z-gleich-N habe, dann ist die untere
Schranke 3-N.
Ja, und damit habe ich hier dann diese untere Schranke gezeigt.
Und wenn ich mir jetzt angucke, andere Verhältnisse von Z und S.
Wenn das S kleiner ist als Z, das heißt, mein Feld sieht im Prinzip so
aus.
Ich habe deutlich mehr Zeilen als Spalten.
Das Verhältnis zwischen den beiden ist 1 zu 2.
Dann habe ich auf einmal als untere Schranke 2-mal Wurzel, 2-mal N.
Minus-groß-O-von-Wurzel.
Also eine etwas kleinere untere Schranke.
Das heißt, da greift dieses Argument nicht ganz so stark, weil der Weg
bis hier nach rechts nicht so groß ist.
Dieser Weg hier ist einfach kleiner.
Und das heißt, ich habe hier etwas andere untere Schranke.
Und das Interessante ist, das S-Quadrat-Weg-Merge-Sort von Thomson
-Kung ist, egal welches Verhältnis ich nehme, immer das Optimale.
Also das war dieses von Thomson-Kung, das war das Verfahren, das ich
angedeutet habe.
Wir haben mit einem S-Quadrat-Weg-Merge ein Verfahren entwickelt.
Wie gesagt, das ist etwas sehr kompliziert dargestellt.
Und deswegen ist das nicht so richtig wahrgenommen worden.
Ist dann aber irgendwann tatsächlich, hat man das gemerkt.
Und es gibt auch inzwischen mehrere Verfahren, die in Zeit 3N laufen.
Nicht nur dieses von Thomson-Kung.
Und für SIMD hat man allerdings noch, wenn man sagt, ich muss auf
jeden Fall mit SIMD arbeiten, in jedem Takt, in allen Prozessoren im
gleichen Befehl.
Dafür kenne ich keine bessere untere Schranke.
Also es ist mir nicht bekannt, eine bessere untere Schranke als für
SIMD.
Und das beste Verfahren, nach meiner Kenntnis, liegt bei 6N.
Das heißt, da sind wir noch weiter weg.
Ich nehme aber an, dass man eigentlich für SIMD auch eine bessere
untere Schranke hätte zeigen können.
Ja, das also zu diesem zweidimensionalen Sortieren.
Wenn man nicht annimmt, dass die Elemente oder dass die Prozessoren in
jedem Takt nur ein Element der Folge speichern dürfen, dann ist es
sogar so, dass nur die triviale untere Schranke gilt.
Und dann kann man sogar auch diese untere Schranke erreichen.
Das geht aber auch deutlich über das hinaus, was ich Ihnen hier
erzähle.
Man kann also auf zweidimensionalen Feldern sehr, sehr interessante
Algorithmen entwickeln, die sortieren.
Und die dann diese Schranken noch verbessern.
Mir lag also vor allem daran, Ihnen nochmal zu zeigen,
zweidimensionales Sortieren reduziert die Laufzeit.
Nicht auf Log N, nur auf Wurzel N, weil ich da diese unteren Schranken
habe.
Ich kann dort sogar optimal sortieren, kann die Schranken erreichen.
Und wir haben hier ein interessantes Verfahren, um untere Schranken zu
zeigen, über diese Joker-Zone, bei der ich im Prinzip in der Lage bin,
also was ein Joker ist, wissen Sie ja, dass man erstmal etwas hinlegt
und dann nach Bedarf den Wert bestimmt, um etwas schlecht zu machen
für den Gegner.
Und genau das ist die Idee hier.
Dass ich eben die Elemente in der blauen Zone, in der Joker-Zone,
schlecht mache für den Algorithmus und dadurch braucht er mindestens
diese Zahl.
Okay, das also zu diesem...
Es gibt dann noch viele andere Verfahren, mit denen man mit anderen
Sortierordnungen arbeitet, also zeilenweise oder spaltenweise oder
spiralförmig oder was immer man machen will.
Man kann auch noch andere Strukturen betrachten, man kann ein Torus
betrachten, bei dem man also nicht ein einfaches kitterverbundenes
Feld hat, sondern wo das links nach rechts auch noch verbunden ist.
Man kann lineares Feld betrachten, man kann Kreise betrachten, sehr
viele verschiedene Strukturen, Bäume, man kann daraus sortieren und
man kann auch etwas betrachten, was ich Ihnen auch noch vorstellen
wollte, das ist ein Mesh of Trees.
Auch eine interessante Rechnerstruktur, die zwei Dinge miteinander
verbindet.
Einerseits die Vorteile einer Baumstruktur mit einer Tiefe von log n
bei zwei n Elementen und eine lokale Struktur, das heißt so ein
Gitter.
Ich habe also hier im Prinzip mein Gitter und habe die Elemente anders
verbunden.
Ich habe durchaus lokale Nachbarschaftsbeziehungen, wenn ich also hier
über die erste Stufe gehe, die beiden Elemente hier oben sind zum
Beispiel verbunden über einen Knoten eines Zeilenbaumes, genau über
diesen einen Knoten eines Zeilenbaumes, also ist das hier so eine Art
lokale Verbindung.
Ich habe also durchaus eine lokale Struktur, habe aber auch, wenn ich
den Baum nach oben laufe, habe ich hier eine Baumstruktur für die
Verbindung, kann also in Zeit log n Informationen über eine ganze
Zeile oder eine ganze Spalte austauschen, weil ich Spaltenwollne und
Zeilenwollne habe.
Und diese Struktur, die hat man also so Anfang der 80er entwickelt,
hat man sich hier ausgedacht.
Das war der Tom Leighton, derjenige, der das Verfahren Akamai
entwickelt hat.
Akamai ist also ein Verfahren, mit dem man in der Lage ist, im
Internet sehr effizient Informationen bereitzustellen.
Der Tom Leighton ist mittlerweile Milliardär, weil er sehr
interessante Ideen hatte, wie man effizient Informationen im Internet
bereitstellen kann.
Also fast jeder, der Informationen anbietet, setzt die Technologien
von Akamai an mittlerweile.
Also, nur als kurze Bemerkung, dass man auch als theoretischer
Informatiker, der sich mit Algorithmen beschäftigt, sehr gut
wirtschaftlich interessante Ideen entwickeln kann und umsetzen kann
und sehr viel Geld verdienen kann.
Was wird hier gemacht?
Hier wollen wir sortieren, auf dem Mesh of Trees.
Und hier verwenden wir jetzt, um eine Folge der Länge N zu sortieren,
viel zu viele Elemente, nämlich N-Quadratelemente.
Wir nehmen ein N mal N-Feld fürs Sortieren von N Elementen.
Und verteilen einfach diese N Elemente sowohl über die Zeilenbäume als
auch über die Spaltenbäume.
Ich verteile sie, X1 bis X4 in dem Fall, über die Zeilen- und
Spaltenbäume an die Prozessoren.
Und habe dann hier zum Beispiel in diesem Element die beiden Elemente
1 und 1, X1 doppelt drinstehen.
Hier steht jetzt drin das X1 und X2 und so weiter.
Und hier steht dann X1 und X4 drin.
Und hier unten dann halt entsprechend X4 und X4.
Das passiert nach dem ersten Schritt.
Verteilen an die, also über die Spalten- und Zeilenbäume heißt, ich
muss log N Schritte von der Wurzel bis zu den Blättern laufen.
Dann habe ich also in jedem Prozessor zwei Elemente drin liegen.
Ich kann die beide vergleichen, insbesondere auf ihre Größe.
Und wenn das Element, das über die Spalte kam, wenn das größer ist als
das Element, das über die Zeile kam, dann schreibe ich eine 1 dort
rein.
Ich muss ja irgendwie das festlegen, ich gucke mal an, ich vergleiche
die beiden Elemente und wenn das Spalten-Element größer als das
Zeilenelement ist, dann schreibe ich dort eine 1 rein, ansonsten eine
0.
Und dann sende ich diese Ergebnisse, die Nullen und Einsen, über
diesen Spaltenbaum zu den Spaltenbaumwurzeln.
Das heißt, ich nehme jetzt hier zum Beispiel hier diese, dieser ersten
Spalte, die Elemente, die dort stehen, das sind irgendwelche Nullen
und Einsen, die bewege ich nach oben und addiere sie dabei.
Also, ich addiere sie dabei, das heißt, ich habe anschließend oben in
der Wurzel dieses Baumes die Anzahl der Elemente, die größer waren,
oder die Anzahl der Vergleiche, bei denen das Element, das in dieser
Spalte verteilt wurde, größer war als die Zeilenelemente.
Ja, wenn es für A größer B, A ist Spalte, B ist Zeile, ich addiere sie
dabei, da stehen dann Einsen, das heißt, der Rang sei jetzt 1, 2, 3
oder 4 aufsteigend, wenn der Rang 4 ist, ist 4 das größte Element.
Wenn also 4 Einsen drin, wenn hier 4 Einsen drin standen, da eine
Eins, da eine Eins, da eine Eins, da eine Eins, dann war das Element
x1 größer gleich alle anderen.
Es kann natürlich nur dreimal größer sein, weil es ansonsten wäre es
ja größer gleich.
Dann sind da maximal drei Einsen drin, bei dem ersten steht garantiert
eine Null drin, weil das ja gleich sich selbst ist, also drei Einsen.
Das heißt, ich habe null bis drei Einsen da drin stehen.
Also mache ich das hier in Rangordnung 0, 1, 2, 3.
Und jetzt sende ich die Ergebnisse, also das habe ich gemacht, und
jetzt verwende ich die binäre Darstellung des Ranges, binäre
Darstellung des Ranges, ich habe also entweder 0, 0, 0, 1, 1, 0 oder
1, 1,
um rangrichtig durch den Baum nach unten zu laufen.
Das heißt, wenn ich zwei Einsen dort stehen habe, gehe ich zweimal
nach links.
Wenn ich von hier runter laufe, gucke ich durch die Laufrichtung, gehe
zweimal nach links, dann lande ich hier unten.
Zweimal eine Eins heißt Rang 3.
Wenn ich keine Eins dort hatte, dann waren alle anderen Elemente
größer, dann lande ich hier, dann gehe ich zweimal nach rechts.
Null heißt nach rechts laufen, Eins heißt nach links laufen.
Ich nehme also einfach die binäre Darstellung und nehme die als
Navigationshilfe durch den Baum.
Und anschließend gebe ich einfach den Wert von den erreichten
Prozessoren aus, also den Wert, der ursprünglich hier reingeschrieben
wurde, das war also der Wert von dem X1, das X1 steht ja hier drin,
gebe ich also den entsprechenden, über die Spalte ursprünglich
eingegebenen Wert, über den Zeilenbaum aus.
Wenn ich also Rang 3 hatte, wenn das hier das größte Element war, also
X1 das größte Element war, dann würde ich das an dieser Stelle
ausgeben, Rang 3.
Wenn es das kleinste war, dann wäre ich hier gelandet, würde es über
den Zeilenbaum ausgeben und wäre an der Stelle gelandet.
Das heißt, über das Ausgeben über die Zeilenbäume habe ich garantiert
die rangrichtige Anordnung auch an den Wurzeln der Zeilenbäume.
Und der Aufwand dafür ist relativ schnell abzuschätzen.
Ich habe für das Verteilen oder auch Aufsammeln über die Zeilenbäume
oder Spaltenbäume jeweils Aufwand Block N.
Ich mache einmal einen Vergleich innerhalb der Prozessoren.
Ich habe also viermal, ich muss erst einmal verteilen über die Spalten
und Zeilenbäume, damit die Elemente in die Prozessorelemente gelangen.
Dann muss ich den einen Vergleich machen und dann muss ich einmal die
Ergebnisse aufaddieren.
Dann muss ich runter wieder die rangrichtigen Prozessor anstoßen und
der muss über den Zeilenbaum ausgeben.
Das sind also nochmal diese drei Log N-Takte, also 4 Log N plus 1
Takte.
Damit habe ich dann in 4 Log N plus 1 Takten insgesamt sortiert.
Allerdings mit N² Elementen.
Ich habe 3 N² minus 2 N Prozessoren.
Wenn ich noch die ganzen Knoten in den Spalten und Zeilenbäumen
dazuzähle, sind es 3 N² minus 2 N Prozessoren.
Und das heißt, die Effizienz ist nicht allzu doll.
Weil ich mit N² Prozessoren nur eine Laufzeit von Log N erreiche.
Und wir wissen ja, dass N Log N das beste sequenzielle Verfahren ist.
Und müssen jetzt mit N² Elementen, naja, das ist viel zu viel.
Wir sollten maximal N Log N Elemente verbrauchen.
Es gibt andere Verfahren.
Es gibt ein Verfahren, das nennt sich Cold Sort.
Das läuft deutlich besser.
Ich will hier nicht zu viel Zeit drauf verschwenden, sondern
einsetzen, um Ihnen jetzt nur Sortierverfahren zu erläutern.
Aber man kann eben noch weitere Verfahren finden, die tatsächlich
parallel sortieren.
Es gibt optimales Verfahren, bei dem man mit N Prozessoren tatsächlich
in Zeit Log N sortieren kann.
Allerdings ist die Konstante bei dem Verfahren sehr hoch.
Das heißt, praktisch einsetzbar ist dieses optimale Verfahren leider
nicht.
Praktisch einsetzbar ist sowas wie unser LSO3 Sort oder das von
Thomson Coombe.
Oder vielleicht sogar das OETS.
Man muss sich eben genau angucken, auf welcher Struktur man gerade
arbeitet.
Und auch in der PRAM würde man also eher Odd-Even Merge Sort oder
Bitonic Sort einsetzen als diese anderen Verfahren.
Auch dieses Mesh of Trees hier mit N Prozessoren ist einfach zu viel
Platzaufwand.
Ich wollte Ihnen trotzdem diese Struktur darstellen.
Sie ist ganz interessant.
Im Prinzip ist das eine Struktur, die auf einer PRAM dafür sorgt, dass
man kein Concurrent Read und Concurrent Write braucht, sondern dass
man das im Prinzip verteilen kann über solche Baumstrukturen.
Man könnte das hier auch ohne diese Baumstrukturen als einen PRAM
-Algorithmus formulieren, bei dem man mit Concurrent Read und
Concurrent Write arbeitet.
Mit einer Summenregel.
Wenn ich eine Summenregel nehmen würde, dann würde ich alles
reinschreiben in eine Position mit Summenregel als Konfliktlösung und
hätte dann sogar in konstanter Zeit mit N²-Elementen sortiert.
Das geht in der Praxis eben leider nicht.
In der Praxis brauchen wir solche Baumstrukturen.
Hier haben wir einen Aufwand von Nog N.
Das sei dazu genug.
Also hatte ich gerade eben was zu gesagt.
Hängt also was mit Concurrent Read und Concurrent Write Strukturen
zusammen.
Und damit kommen wir ganz kurz eine Folie zur unteren Schranke für die
Anzahl der Vergleiche.
Die Frage ist, ginge es theoretisch besser als mit N-Nog-N-Vergleichen
zu sortieren?
Also das waren die Anzahl der Vergleiche bei Merge Sort oder auch bei
Quick Sort, im günstigen Fall und im mittleren Fall, oder auch bei
Heap Sort.
Heap Sort ist übrigens, von der Anzahl der Vergleiche her, das beste
Verfahren, das man kennt auf sequenziellen Rechnern.
Allerdings eine besondere Variante von Heap Sort.
Nicht die, die Ihnen vorgestellt wurde in den Grundlagen der
Informatik 1.
Aber die sind von der Größenordnung her alle im gleichen Bereich.
Abgesehen von Quick Sort, das im schlechtesten Fall N²-Elemente
braucht.
Und das, was wir uns überlegen müssen, ist einfach, wenn ich eine
untere Schranke mache, worüber argumentiere ich?
Und wir hatten ja gesagt, wir gucken uns allgemeine Sortierverfahren
an, bei denen wir nichts wissen, von vornhinein, über die Elemente,
die sortiert werden müssen.
Wir wissen nur, wir können sie in Bezug auf die Größe vergleichen.
Mehr wissen wir nicht.
Das sind dann die allgemeinen Sortierverfahren und wir wissen, dass
wir die nur über den Entscheidungsraum sortieren können.
Und wenn man annimmt, dass alle Listelemente verschieden sind, dann
weiß ich bei einem, wenn ich anfange mit der eingegebenen Liste, dann
kann ich hier irgendwelche Entscheidungen treffen und ich habe einen
binären Baum, bei dem ich irgendwann dann hier auf eine ganze Reihe
von Blättern komme und die Anzahl der Blätter, die ich hier habe, die
muss größer gleich N-Fakultät sein.
Weil ich N-Fakultät verschiedene Sortierreihenfolgen haben kann, N
-Fakultät -Permutationen einer Folge, das heißt, egal welche Folge ich
eingebe, ich muss immer auf die richtige sortierte Reihenfolge kommen,
das heißt, ich muss jede beliebige Permutation ausführen können, durch
das Sortieren und damit habe ich mindestens N-Fakultät-Blätter in
meinem Entscheidungsraum.
Es kann sein, dass bei einem Verfahren, das ausgeführt wird, sogar
mehr als diese N-Fakultät rauskommt, dass man also mehrfach der Pfade
durchläuft, bei dem ich auf die gleiche Folge komme, dann hätte ich
einen ineffizienten Entscheidungsraum.
Weil ich brauche eben mindestens diese N-Fakultät.
Und wenn ich mir so einen Baum angucke, sage ich intuitiv sofort, das
geht ja hier noch irgendwie weiter, so irgendwie ein binärer Baum,
dann sage ich, naja, dann ist doch eigentlich klar, dass die Länge der
Wege hier log von N-Fakultät sind.
Es ist nur die Frage, welche Struktur hat denn der Baum.
Wenn das ein vollständiger binärer Baum ist, dann ist es sofort klar,
der muss Log N-Fakultät haben als maximale Fahrtlänge oder auch
mittlere Fahrtlänge.
Also die Anzahl der Vergleiche im schlechtesten Fall ist ja die
maximale Fahrtweglänge, die Anzahl der Vergleiche im Mittel ist die
mittlere Weglänge.
Wenn ich jetzt sagen will, was ist eigentlich die untere Schranke für
die Anzahl der Vergleiche im schlechtesten Fall, also für die maximale
Weglänge, muss ich über alle möglichen Entscheidungsbäume
argumentieren.
Und jetzt kann man sich genau überlegen, was passiert, wenn ich einen
Baum habe, bei dem die Pfade, die hier so durchlaufen, sich um maximal
k oder irgendwas unterscheiden.
Ich habe also irgendeinen Pfad, der hat eine Länge x und ein anderer
Pfad, der hat eine Länge x-k.
Also k sei das Maximum der Unterschiede.
Und dann kann man zeigen, wenn das k größer gleich 2 ist, dann kann
ich den Baum so umbauen, kann die Struktur so verändern, dass ich den
Abstand um 1 reduziere, dass ich dann anschließend k-1 als maximale
Differenz habe in der Fahrtlänge.
Das heißt, ich kann, egal welchen Entscheidungsbaum ich mir hernehme,
ich kann den Baum so verändern, dass ich auf eine maximale
Fahrtlängendifferenz von 1 komme, ohne dass das Verfahren inhaltlich
besonders verändert wird.
Und das heißt, eine untere Schranke kann sich beziehen auf, oder man
kann eben auch zeigen, dass diese Vergleichung schlecht ist.
Also es ist klar, wenn die maximale Wegdifferenz k-1 ist, dann habe
ich bei der maximalen Weglänge den bestmöglichen Pfad.
Und für diese Bäume ist es auch so, dass die mittlere Weglänge dann
auch der bestmögliche Pfad ist.
Und das kann man sich genau überlegen.
Will ich nicht im Einzelnen durchführen, sondern ich sage Ihnen
einfach, man macht das über diese Überlegung, indem man einfach zeigt,
wenn die Differenz größer ist, kann man das reduzieren auf einen Baum,
der diese maximale Fahrtlängendifferenz von 1 hat.
Das ist ein fast ausgeglichener Baum.
Und für diese fast ausgeglichenen Baum ist tatsächlich die maximale
und die mittlere Weglänge halt in Log N-Fakultät natürlich.
Und wenn ich mir Log N-Fakultät anschaue, dann ist das Omega von N mal
Log N.
Das kann man sich überlegen auf verschiedene Art und Weisen.
Unter anderem über die Stirling-Formel.
Auch darauf will ich nicht im Einzelnen eingehen.
Das sind also einfach Überlegungen für diese Abschätzungen.
Man kann das sich sehr einfach abschätzen.
Also im Prinzip Log N-Fakultät.
Ich kann Ihnen hier etwas hinschreiben.
Log N-Fakultät ist natürlich kleiner gleich Log N hoch N.
Da werden Sie sofort zustimmen, dass das der Fall ist.
Log N-Fakultät ist das Produkt von 1 bis N.
Das ist sicherlich kleiner gleich Log N hoch N.
Und das ist aber gleich N mal Log N.
Ja?
Dem werden Sie sicherlich auch sofort zustimmen.
Und natürlich ist das Log N-Fakultät auch größer gleich Log Produkt
von, sagen wir mal einfach Produkt.
Nehmen wir einfach mal hier ein Teil raus.
N-Halbe.
Das ist größer gleich.
N-Halbe hoch N-Halbe.
Ja?
Nehmen wir einfach von N-Halbe an.
Schreibe ich nur mal N-Halbe mal N-Halbe und so weiter.
Reduziere einfach die zweite Hälfte dieses Produkts.
Und das ist aber gleich N-Halbe mal Log N-Halbe.
Das ist ganz einfach.
Ganz grobe, ganz ganz grobe Abschätzung.
Aber da sehen Sie sofort, N-Halbe mal Log N-Halbe ist natürlich Omega
von N-Log-N.
Und das hier war das N-Log-N, hier ist natürlich eine Groß-O von N-Log
-N.
Damit haben wir das Log N-Fakultät sehr einfach abgeschätzt.
Zwischen N-Halbe mal Log N-Halbe und N mal Log N.
Eine sehr einfache Abschätzung.
Man kann das genauer machen.
Brauchen wir hierbei nicht.
Also, das ist die untere Schranke für Sortieren.
Jetzt wissen wir, wir brauchen mindestens N-Log-N-Vergleich.
Jetzt kommt ein spezielles Sortierverfahren, das wie folgt arbeitet.
Ich will einfach sortieren durch Dosen werden.
Ich gebe einfach jedem von Ihnen eine Dose.
Da steht auf jedem eine Zahl drauf.
Von in diesem Fall 1 bis 5 oder 1 bis 6.
Und ich nehme eine Folge, die hat nur Zahlen 1 bis 6.
Aber die ist bedienlich lang.
Eine sehr lange Folge.
Und ich sortiere jetzt folgendermaßen.
Ich stelle Ihnen also die Dosen hin.
Nimm meine Folgelemente, schaue mir also irgendein Element an und
werfe dieses Element dann in die entsprechende Dose rein.
Wenn es eine 5 ist, werfe es in die Dose 5.
Wenn es eine 1 ist, in die Dose 1 und so weiter.
Dazu schaue ich mir natürlich jedes Element nur einmal an.
Aha, das ist Element 4 in Dose 4.
Und anschließend nehme ich meine 6 Dosen her, nehme sie der Reihe nach
und leere sie aus.
Ich nehme also jedes Element aus der ersten Dose, alle aus der
zweiten, alle aus der dritten und so weiter.
Und da ich das in der Reihenfolge 1 bis 6 mache, habe ich sie
anschließend alle sortiert.
Und wenn ich das sogar noch so mache, dass ich die Reihenfolge genau
dabei aufrechterhalte, die Reihenfolge, in der ich die Elemente aus
meiner Ursprungsfolge genommen habe, also wenn ich hier meine sehr
lange Folge habe und da tauchten an vielen Stellen das Element 2 auf.
Und ich schreibe die genau in dieser Reihenfolge, hier das Element,
das, das und so weiter, ich schreibe die schön der Reihe nach in meine
Dose mit Aufschrift 2 rein.
Dann kann ich die natürlich anschließend auch genau in der Reihenfolge
wieder rausholen.
Das heißt, ich kann die also sortieren, in Bezug auf die Werte 1 bis
6, in dem Fall, oder 1 bis K, und habe sogar die Reihenfolgen, die
vorher aufgetaucht waren in meiner Folge, aufrechterhalten.
Und ich habe jedes Element nur zweimal angeschaut.
Oder in der Hand gehabt.
Einmal angeschaut, reingeworfen, einmal rausgeholt.
Das heißt, ich habe insbesondere keinen einzigen Vergleich von
Schlüsseln vorgenommen.
Ich sortiere völlig ohne Vergleich.
Ich habe nur zwei Operationen pro Element.
Ich habe also ein sehr, sehr schnelles Verfahren.
Lineare Zeit für Sortieren.
Allerdings habe ich eben auch eine ganz andere Information von
vornherein gehabt.
Ich wusste, es sind Elemente von 1 bis 6.
Ich habe mir die Dosen hingestellt und kann entsprechend sortieren.
Das heißt, wenn ich weiß, ich habe nur einen beschränkten Umfang der
Elemente, die ich sortieren muss, und werfe die da einfach sukzessive
rein, dann ist das alles relativ einfach.
Aber wenn der Bereich zu groß ist, dann wird das aufwendig.
Das heißt, dass hier die Daten mit Gleichgewicht, dass die
ursprüngliche Reihenfolge nicht verändert wird, kann man also auch im
Prinzip machen, habe ich schon gesagt.
Man kann auch noch anders sortieren, man kann auch einen Radix Sort
nehmen.
Ich habe beliebige Zahlen, ich weiß nicht, welche tauchen eigentlich
auf.
Aber ich habe, meinetwegen, irgendwelche 16-Bit-Zahlen.
Um das einfacher zu machen.
Dann würde ich einfach zunächst mal nach der ersten Position
sortieren.
Dann würde ich nach der zweiten Position sortieren.
Und das mit zwei Dosen machen.
Dann nach der dritten Position und so weiter.
Hätte ich also 16-mal jeweils so 0,1 Sortierungen zu machen.
Natürlich muss ich immer innerhalb das dann dabei eine richtige
Reihenfolge behalten.
Und dann hätte ich im Prinzip 16-mal linearen Aufwand.
Das ist immer noch konstant.
Allerdings, wenn die alle verschieden sind, dann habe ich maximal 2
hoch 16 verschiedene Elemente.
Und das heißt, dann hätte ich, wenn das 2 hoch 16 N ist, hätte ich
gerade Log N solche Dosen.
Und ich müsste aus Log N Dosen etwas rausholen.
Dann hätte ich Log N mal N als Aufwand.
Das kennen wir schon.
Das heißt, man muss aufpassen, was man macht.
Wenn man etwas weiß, was die Unsicherheit über die zu sortierenden
Elemente deutlich reduziert.
Dann kann man das ausnutzen, kann spezielle Sortierverfahren machen
und kann in linearer Zeit sortieren.
Und das tritt in der Praxis durchaus häufig auf.
Und dann sollte man das auch verwenden.
Also nur, dass Sie wieder sehen, genau wie beim Auswerten von
Polynomen.
Da hatten wir gesehen, wenn wir die Koeffizienten kennen, können wir
schnell Polynome auswerten.
Weil wir dann anders daran gehen können, wenn wir die Koeffizienten
vorher kennen.
Wenn wir das ausnutzen.
Hier können wir, wenn wir wissen, was ist der Zahlenbereich, dann
können wir eventuell auch deutlich schneller sortieren.
Okay, das war alles, was ich Ihnen zum Sortieren erzählen wollte.
Man hätte darüber noch viel mehr erzählen können, auf allen möglichen
anderen Strukturen Sortierverfahren machen.
Insbesondere in Bezug darauf, wie kann ich sortieren, wenn viele
meiner Elemente im Hintergrundspeicher liegen.
Da muss man sehen, dass man die Anzahl der Zugriffe auf den
Hintergrundspeicher reduziert.
Und Sie wissen, dass Zugriffe auf den Hintergrundspeicher sehr viel
Zeit brauchen.
Einfach weil dort die Zugriffszeiten einfach hoch sind.
Und da muss man sehr genau das Speichermanagement machen, um
tatsächlich sortieren zu können.
Da hat ja vor kurzem mein Kollege Peter Sanders hier am KIT einen
Weltrekord aufgestellt in Bezug auf das Sortieren von sehr riesigen,
wirklich sehr sehr großen Datenmengen.
Durch sehr effizientes Ausnutzen von parallelen Rechnern, aber auch
durch sehr effizientes Speichermanagement.
Also das ist ein Punkt, wo noch immer sehr viel daran gearbeitet wird.
Und ich hoffe, dass ich Ihnen jetzt einiges in dem Beispiel an
Prinzipien präsentieren konnte.
Insbesondere eben 0-1-Prinzip und dann, wie man so auf verschiedenen
Strukturen geeignet arbeitet.
Jetzt kommen wir zu Selektionsverfahren.
Einfacher als sortieren.
Wir wollen nicht insgesamt sortieren, wir wollen nur das größte
Element haben einer Liste.
Also das größte oder kleinste oder fünftgrößte oder was immer.
Das hatte ich ja schon mal definiert.
K von S gleich SJ mit J aus N.
Das heißt, wenn es das K-größte ist, dann gibt es K-1 Elemente, die
kleiner gleich sind.
Ich habe das jetzt richtig gemacht.
I aus N, SI, die Menge aller Indizes, bei denen SI größer als SJ ist.
Oder SI ist gleich SJ, aber die Position von I ist größer als J, ist K
-1.
Das heißt, in der sortierten Reihenfolge ist mein Element SJ hier
irgendwo angeordnet.
Und es sind genau diese K-1 Elemente größer als das SJ.
Das steht hier, SI ist größer als SJ.
Oder sie sind in einer anderen Position.
Dann ist das das K-größte Element.
Wenn ich mir diese Folge anschaue, die hier als Beispiel angegeben
ist, ist das größte Element offensichtlich die 27.
Das sechste größte Element, muss man kurz mal durchgucken, 27, 7, 6,
dann haben wir die 4, dann haben wir 3 und 3.
Das sechste größte Element ist die 3.
Und das neunte größte Element in dem Fall ist die 1.
Und das elfte größte ist auch die 1.
Aber wir haben hier drei Einsen drin.
Also das ist einfach diese Anordnung.
Ganz einfach, Spezialfall ist der Median, der ist am schwierigsten zu
bestimmen.
Ob ich also jetzt das größte oder kleinste bestimme, hat den gleichen
Aufwand.
Zwei größte oder zwei kleinste, auch gleicher Aufwand, relativ
einfach.
Aber die Media, das ist relativ schwierig, das mittlere Element
wirklich zu bestimmen.
Das heißt, ich würde ein Element angucken, bei dem die Hälfte der
Elemente größer ist.
Und wenn ich also den Median habe, einer Folge der Länge 5 in dem
Fall, hier, wie bei dieser Folge, ist das offensichtlich die 3, das
drittgrößte Element.
Folge der Länge 5, 5 durch 2 ist 2,5, nächstgrößere Zahl ist die 3.
Dann habe ich hier also das dritte Element.
In diesem Fall brauche ich das mittlere Element, da habe ich auch 5
Elemente.
Das drittgrößte Element in dem Fall ist die 1.
Und hier habe ich 4 Elemente, da muss ich das zweitgrößte Element
nehmen, das ist in dem Fall die 5.
Und so kann man also den Median definieren.
Sie wissen, dass der Median ungleich dem Mittelwert ist.
Das ist ganz wichtig, das klar zu machen.
Wenn ich also von mittleren Studienzeiten rede, dann ist es besser,
den Median zu nehmen, um zu sagen, mindestens die Hälfte der
Studierenden ist in der Zeit tatsächlich fertig.
Wenn ich den Mittelwert nehme, kann es sein, dass einige wenige
Langzeitstudierende den Wert nach oben schieben.
Und wenn ich jetzt selektieren will, kann ich das auch
unterschiedlicher Art und Weise machen.
Wir wollen also jetzt das k-größte Element bestimmen, vielleicht auch
den Median.
Das kann ich so machen, wenn ich das k-größte Element bestimmen
möchte, dass ich nacheinander das größte, zweitgrößte, drittgrößte
usw.
bestimme, bis ich das k-größte bestimmen kann, dadurch, dass ich die k
-1 größeren rausgenommen habe.
Das ist aber ein Aufwand.
k-1 mal Maximum bestimmen, k-1 mal lineare Aufwand.
Oder, wenn das k größer als 1,5 ist, nehme ich immer das Minimum.
Einfach von einer anderen Richtung angeguckt.
Das ist für das zweitgrößte vielleicht noch in Ordnung.
Für das drittgrößte, wenn ich den Median bestimmen will, hätte ich auf
einmal n,5 mal n Aufwand, wäre ein quadratischer Aufwand.
Also die Anzahl der Vergleiche dafür wäre im schlechtesten Fall
quadratisch.
Wenn ich den Median z.B.
bestimmen möchte.
Mit dem Verfahren.
Sicherlich schlecht, denn ich kann ja einfach sagen, ich sortiere
einfach, dann kann ich anschließend, egal welche Rangordnung mich
interessiert, ich nehme mir einfach das entsprechende Element raus.
Habe keinen Aufwand mehr.
Und da ich ein n log n sortieren kann, ist also der maximale Aufwand,
den ich treiben muss, für Selektion n log n.
Das Interessante ist, dass man das besser machen kann.
Ich will ja eigentlich gar nicht alles sortieren.
Und es ist tatsächlich so, man kann in linearer Zeit den Median
bestimmen.
Ja, also geht es besser, kann ich sofort beantworten.
Es geht.
Und ein einfacher Ansatz, den können wir uns ganz schnell noch
angucken.
Sind wir gleich fertig.
Quick Select.
Quick Sort kennen Sie.
Bei Quick Sort habe ich einfach nur immer bestimmt, habe ich also
irgendein Element hergenommen, das Pivot-Element, dann in meine Folge
entsprechend partitioniert und musste dann in beiden Folgen
weitermachen, beim Sortieren.
Wenn ich Quick Select mache, dann partitioniere ich auch und
anschließend gucke ich einfach nach, wo muss ich weitersuchen nach dem
Cart -größten Element.
Also, das Cart-größte Element kann bereits dieses Element sein.
Das ist der Fall Nr.
3.
Dann ist nämlich dieses Element C bereits das Cart-größte Element.
Wenn in diesem Bereich der größere der Elemente, die größer gleich
sind, wenn das mehr als K Elemente sind, dann weiß ich, das Cart
-größte Element liegt auf jeden Fall in diesem Bereich.
Links daneben.
Da muss ich nur da weitermachen.
Ich weiß, das kann gar nicht.
In dem Bereich liegen der kleinere.
Ich muss also nur in einer Hälfte weitermachen.
Und wenn es der andere Fall ist, wenn hier links daneben weniger sind,
na ja, dann ist das Cart-größte Element irgendwo in diesem Bereich
hier.
Dann muss ich da weitersuchen, aber nicht mehr nach dem Cart-größten,
sondern nach dem K-Betrag von S-größten Element.
Das heißt, in jedem Fall muss ich nur in einer der beiden Folgen dann
weitersuchen.
Und wenn ich das analysiere, dann habe ich also hier anzugucken, das
Maximum der Vergleiche, die ich machen muss, um in einer der beiden
Teilfolgen weiterzusuchen.
Das können aber im Prinzip, weil ich ja nicht weiß, wo das Element C
hinkommt, kann das eine beliebig große Folge sein.
Und ich bekomme, wie bei Quicksort auch, für den schlechtesten Fall,
nur eine Reduktion der Liste um Länge 1.
Dann habe ich leider n².
Wenn ich aber jedes Mal optimal aufteile, dann habe ich ja nur den
Aufwand für n½, plus linearen Aufwand für die Partitionierung und
Aufwand für n½ plus Partitionierung.
Dann habe ich genau so eine Formel.
T von n ist dann gleich so in etwa T von n½ plus O von n.
Und da wissen wir, das liegt in O von n.
Also ganz einfach.
Das heißt, mit Quickselect habe ich ein bestes Verhalten in der Zeit,
das heißt also nicht mittlere, sondern bestes Verhalten, in linearer
Zeit.
Und tatsächlich auch im Mittel, und das ist etwas, was man in der
Übung machen könnte, das war diesmal nicht mehr drin, aber kann man
sich leicht überlegen.
Die Überlegung, die ich gemacht hatte auf der einen Folie für
Quicksort, kann man hier für Quickselect machen und kriegt raus, das
Verhalten liegt insgesamt in O von n.
Das heißt, da habe ich ein mittleres Verhalten, das linear ist.
Also eine Verbesserung.
Und das nächste Verfahren, was ich Ihnen in der nächsten Woche
vorstellen werde, ist ein Verfahren, bei dem wir diese Partitionierung
so machen, dass der schlechte Fall niemals auftritt.
Das heißt, wir werden so Partitionieren oder so Elemente aussuchen,
als Pivot-Elemente, dass ich garantiert immer einen festen Bruchteil
meiner Folge wegwerfen kann.
Und das ist dann das Verfahren, das hier auf der nächsten Folie kommt.
Das ist dieses Bild.
Ich werde also wissen, dass ich entweder den Teil rauswerfen kann oder
den Teil rauswerfen kann, also etwa ein Viertel der Elemente
rauswerfen kann, bei jedem Rekursionsschritt von dem Klick-Select.
Und wenn ich das machen kann, dann habe ich immer einen gutartigen
Fall bei der Rekursion und komme insgesamt auf lineare Zeit.
Das ist also das Verfahren dann, was man hier als lineare
Medienalgorithmus bezeichnet.
Das war's für heute.
Vielen Dank.