Video 7-6: Optimierungen für Mergesort

0:03 Im nächsten Abschnitt will ich ein paar Optimierungen vorstellen, also kleine Verbesserungen von Merch Sort, soll das hier heißen, die in der Praxis immer wert sind, umgesetzt zu werden und auch in den typischen Implementierung so verwendet werden. Äh, die sind jedes für sich genommen nicht besonders kompliziert. Das ist einfach so ein bisschen gesammeltes Erfahrungswissen über die Zeit, in der Merch Sort verwendet wurde. Aber es sind so ein paar clevere Ideen, die nicht nur bei Merch Sort hilfreich sein können. Das heißt, betrachten Sie die nächsten ähm paar Folien so ein bisschen als Inspiration. Was kann man so tun, um einen Basisalgorithmus, wie in irgendeinem Lehrbuch steht, in der Praxis noch ein bisschen besser zu machen? Äh höchstwahrscheinlich sind die ganz gut übertragbar. Es gibt viele ähnliche Algorithmen, wo ähnliche Tricks dann auch hilfreich sind.

0:55 Ähm, ein Kommentar noch zum zum Speicher, den man verwendet. Wir haben bisher beide Runs in einen äh Pufferspeicher kopiert, dieses Auxiliary Array und äh dann das Ergebnis zurückgeschrieben in das Array, in dem wir die Ausgabe haben wollten. Ähm ja, den den Teil ähm würde ich jetzt erstmal noch ausklammern. Man kann auch mit der Hälfte vom Zusatzspeicher auskommen. Im Grunde müssen Sie dafür nur einen Run wegkopieren. Also unsere ursprüngliche Eingabe sitzt hier in dem Array A, wo wir sie auch am Ende wieder haben wollen. Dann habe ich ein Auxiliary Array für die erste Hälfte. Die kopiere ich jetzt da rein. Dann ist dieser Platz hier frei und ich kann da rein anfangen, meine Merches zu machen. Also, ich gucke mir die Elemente hier, die kleinsten von diesem Run an und von diesem und das kleinere der beiden wandert jetzt hier in die Position da. Jetzt könnte man sich Gedanken machen, ob nicht vielleicht irgendwann man äh hier diesen Teil vorne gefüllt hat und in diesen hinteren Run reinrennt. Das kann aber nicht passieren. Ich habe dafür gar nicht genug Elemente. Also sollte das passieren, dass dieser schraffierte Teil, den ich jetzt als Ausgabepufer verwenden möchte, komplett voll läuft und diese Eingabe hier hinten noch nicht verarbeitet ist, dann bin ich im Best case von Merchsort.

2:32 Dann war nämlich die ganze Eingabe hier schon kleiner als diese und ich kann diese diesen Rest von dem zweiten Run in dem Extremfall den ganzen einfach stehen lassen, wo er ist, ist sogar noch besser. Also da passiert nie was ähm was gefährliches. Man hat immer genug Ausgabepuffer, um alle Elemente unterzubringen, die man schreiben möchte. Wenn ich hier den Puffer äh wenn ich sozusagen mit dem Schreiben weiter hier rüber gewandert sein sollte zu irgendeinem Zeitpunkt, dann werde ich die Elemente, die da vorher standen, im zweiten Run auch schon bewegt haben. Wir haben gar nicht genug Elemente, um Ärger zu produzieren. Ähm man kann, hatte ich vorhin auch schon mal an gestutet, dass man auch merchen kann ohne überhaupt großen Zusatzpuffer mit cleveren Tricks. Nehmen Sie das mit als beim Sortieren ist vieles möglich, aber es ist teurer und lohnt sich in der Praxis nicht. Aber man könnte grundsätzlich kann man das machen. Äh braucht uns erstmal nicht weiter zu interessieren. Also den Teil wen sie nicht wissen.

3:38 Äh diese formale Definition vielleicht vielleicht lohnt es sich den Begriff einmal zu nennen. In Place heißt halt ohne viel Zusatzspeicher und äh Leute streiten sich eigentlich immer gerne drum, was das genau heißt. Ähm, meistens ist der der Knackpunkt, ob man jetzt linear viel Zusatzspeicher braucht oder deutlich weniger. Und hier haben sie jetzt gesagt, formal ist es für uns logarithmisch viel Speicher. Äh, das erlaubt dann so Dinge wie einen Rekursionsstack, den Merchsort ja auch braucht. Äh dazu da würde ich mich jetzt nicht dran aufhängen wollen. Inplace ist einfach die Idee, dass man im Wesentlichen deutlich weniger als linear viel Zusatzspeicher braucht.

4:36 Also in aller Regel ist klein O von N. Wenn Sie das erreicht haben, dann kann man auch noch mehr machen. Das ist der schwierige Teil.

4:49 eine andere Beobachtung von Merchsort, die in diesem ähm quadratischen Bild mit den rekursiven Aufrufen auch schon ganz klar war. Man verbringt sehr viel Merch Schritte damit, winzige kleine Schnipsel von diesem Array zu verschmelzen und das funktioniert. Das ist okay. Ist aber relativ teuer für das, was wir da machen. Deswegen lohnt sich in der Praxis für kleine Eingaben nicht Merch Sort zu verwenden, sondern sowas wie unseren Insertion Sort aus dem primitiven Sortierkapitel zu verwenden. Der hat einfach keine rekursiven Aufrufe. Der benutzt nicht dieses hin und her kopieren. Für sehr kleine Eingaben ist der schneller. Und jetzt könnten Sie sagen, das ist ja völlig irrelevant. Wann sortiere ich denn nur zehn Elemente? Das ist doch Quatsch. Aber sie müssen bedenken, dass wir einen Dividing Con Algorithmus haben, der zwar mit einer großen Eingabe losläuft, aber nach ein paar mal zer Hackstücken auch immer bei kleinen Eingaben ankommt und tatsächlich ganz viele von Aufrufen hat, die auf einer kleinen Eingabe laufen. Das heißt, selbst wenn die Eingabe eigentlich groß ist, nach rekursiven Aufrufen, ist sie immer auch klein irgendwann. Deswegen lohnt es sich diesen Basisfall ein bisschen zu optimieren. Im Code ist das sehr einfach. Sie prüfen einfach, wenn sie mit low and nah genug beieinander sind, dann machen wir statt dem normalen Merchsorten einen Aufruf zu einem anderen Sortierverfahren.

6:17 Sieht dann so aus, ähm noch mal eine andere Art Merchort zu malen. Ähm der Abbruch hier erfolgt schon bei diesen 10 Elementen. Die werden dann eben mit Insertion Sort sortiert. Das heißt, ich habe deutlich weniger rekursive Aufrufe dadurch. Das ist so die Hauptersparnis. Konzeptionell ist das Bild das gleiche wie vorher, nur dass jetzt ähm der Abbruch schon bei zehn Elementen passiert.

6:46 Eine zweite Optimierung, die ähm an die Sie vielleicht selbst gedacht hatten, als ich Ihnen versucht hatte klarzumachen, dass mit nur dem ersten Runkopieren nie was Schlimmes passieren kann. Da hatten wir diesen diesen besonderen Fall, dass ich diesen halben diesen ersten Run wegkopiere und dann der Fall, dass alle Elemente hier in diesem ersten Bereich aus diesem wegkopierten Runs stammen und ich den zweiten Run gar nicht bewegen musste. Wenn das der Fall ist, dann war dieses Element hier das größte im kle im linken Run kleiner als das kleinste Element im zweiten Run. Das ist ein Vergleich, den kann ich machen. Wenn ich das mache, bevor ich anfange mit dem Kopieren, dann muss ich gar nichts machen, denn dann ist die Eingabe schon sortiert. Das ist also ein ganz ganz günstiger ähm Zusatzcheck, einziger extra Vergleich, der aber, wenn er äh für den unwahrscheinlichen Fall, sagen wir mal, dass der so ausgeht, dass wirklich alles links schon kleiner ist als alles rechts, dann spare ich mir das ganze Merch. Also, wenn der eintritt, hilft er ganz viel, weil er den kompletten Merchritt umgehen kann. Ähm lässt sich auch im Code unfassbar kompakt schreiben, weil man einfach dann den Merchauffruf überspringt mit einem frühzeitigen Return.

8:11 Das klingt auch nach was, was vielleicht ähm oft nicht nichts tut, dann ist es ein bisschen overhead, weil man ein extra Vergleich hat, aber wenn es eben äh zuschlägt, dann kann es ganz viel helfen. Und da werden wir im letzten Kapitel noch mal ein bisschen drauf zurückkommen. Ähm man hat diesen Fall tatsächlich sehr oft, wenn die Eingabe schon fast sortiert ist. dazu dann ähm mehr Details am Ende.

8:50 Ein anderer cleverer Trick, dem ich den Namen ähm Pingpong Merch Sort geben würde, weil der glaube ich ähm etwas einprägsamer ist. Der Name ist auch nicht von mir. Das ähm habe ich selbst so gelernt und er ist bei mir hängen geblieben. Insofern gehe ich aus, dass das vielleicht auch bei Ihnen passiert. Wenn Sie sich ähm erinnern, wie wir das mit diesem Auxiliary Array gemacht hatten, jeder Merchit hat die zwei Runs, die wir jetzt merchen wollen, zuerst wegkopiert und dann zurück in die Position gemergedt, wo wir äh die Ausgabe haben wollten. Und was wir in der Rekursion dann aber machen, ist ja die linke Hälfte rekursiv sortieren und die rechte Hälfte rekursiv sortieren. Dafür haben wir beide Hälften wegkopiert und zurückgemerged, um sie danach für den endgültigen Merch wieder wegzukopieren und zurückzumergen. Das ist eigentlich ein bisschen doof. Was man stattdessen machen könnte, ist dieses ähm das rekursives Sortieren umdefinieren, dass es nicht in Place A sortiert, sondern ich sortiere von A nach AUX.

10:02 Ist das die richtige? Genau. Also, bewegen mit einem Sortieraufruf die Daten von einem in das andere Array. Wenn ich dann in meinem rekursiven Aufruf die Rolle der beiden Arrays vertausche, dann macht die gleiche Art von da nach da sortieren genau das, was ich eh möchte. Das heißt, ähm ich sortiere die linke und rechte Hälfte von A in das Auxiliary Array. Äh sieht so aus, als würde ich das genau andersrum machen, gell? Geht so rum.

10:52 Okay, noch mal denken, wie rum ist das? Also, ich sortiere rekursiv das Auxiliary Array. Wie kommen denn die Daten da rein? Sind die von Anfang an da drin?

11:05 Okay, das steht hier. Also, es ist schon ähm am Ende sind die Daten in A und ich gehe davon aus, ich habe einmal vor dem ersten Aufruf sowohl AUX als auch A mit den Daten befüllt. Das heißt, es ist egal, mit welchem ich anfange. Und die Idee ist aber, dass am Ende, nee, ich ändere meine Meinung ein drittes Mal. Der wichtige Punkt ist ja, dass Merch die Daten am Ende in das Auxiliary Array schreibt. Da liegen am Ende die sortierten Daten. Also, sie sehen, ist ein ganz einfacher Algorithmus, der auch ähm einen überhaupt nicht verwirren kann mit wie man die Reihenfolge äh baut. Also was was man auf jeden Fall im Code testen will. Konzeptionell ist die Idee, dass man diese rein die Rolle der beiden Arrays immer hin und her tauscht, dass man die Daten ping pong hin und her mercht von einem in den anderen. Äh die ist konzeptionell einfach. Man muss nur aufpassen, dass man die richtige Semantik wählt.

12:13 Das spart insbesondere die ganzen Kopierschritte, also spart massiv an Array Schreib und Lesezugriffen, was wir vorher mit diesen 6nlog nen. Können Sie überlegen, was das jetzt geworden ist. Ähm, spart aber keinen Zusatzspeicher. Ich brauche jetzt wieder diesen diesen Platz für die komplette Eingabe zweimal. diese Optimierung, dass ich nur den einen Runkopiere, die kann ich damit nicht kombinieren.

12:45 Dann habe ich noch einen letzten Kommentar zu Merchsort, der Merchsort noch mal so ein bisschen auf den Kopf stellt und wir werden das nur, ich möchte es nur ganz kurz anteasern, aber ich denke, es ist wertvoll, dass Sie die Idee einmal gesehen haben. Wir haben Merchsord als einen rekursiven Algorithmus beschrieben. steht ja hier auch noch mal äh dankswerterweise auf der Folie. Das heißt, ähm ich habe immer diese diesen Overhead der Rekursion und ich brauche auch dafür ja Zusatzplatz, um den Rekursionsstack zu realisieren. Also, das ist zwar versteckt und äh normalerweise kein großes Thema, aber in Java ja durchaus manchmal schon, wenn man nicht aufpasst. Da ist der der Stackplatz manchmal gar nicht so groß. Ähm hat also einen gewissen Overhead. Könnte man das nicht irgendwie loswerden? Äh dazu vielleicht einfach noch mal können auch dieses Bild hier nehmen. Wenn man sich dieses Bild anschaut, so rein rausgezoomt optisch ist das Muster, was da passiert eigentlich sehr vorhersehbar.

13:45 Ich habe hier diese zwei kleinen Runs. Also, ich habe überall diese ähm Basisfälle von kleinen Runs, die ich hier jetzt mit den Search Sort sortiere, aber darum geht's mir nicht. Aus diesen zwei kleinen benachbarten Runs wird die nächst größere Einheit von Runs und aus denen wird dann wieder die nächst größere. Und sie sehen auch, wie das hier so ein äh so ein gewisses optisches Muster hat. Worauf ich hinaus will, ist das ist nicht so chaotisch, dass man dafür eine Rekursion braucht. Man kann eigentlich vorher schon vorher sagen, was wann gemergedt werden muss.

14:31 Und das ist die Idee von ähm dem iterativen oder Bottom Up Merch Sort. ähm manchmal unbequem, dass man hier für den Cstack Platz braucht und manchmal ist es auch hilfreich, dass man anfangen kann zu sortieren, ohne die Gesamtlänge der Eingabe zu kennen. Da werden Sie mich jetzt vielleicht bisschen ähm an der Stelle müssen Sie mir entschuldigen, dass es ein Vorg ist aus auf das nächste Kapitel, wo wir über Listen reden, die nicht mehr als Array realisiert sind. Äh, wir werden sehen, dass man Merch auch auf denen genauso ausführen kann und da ist es durchaus möglich, dass man vorher gar nicht weiß, wie viele Elemente da noch kommen. Äh, sie müssen außerdem bedenken, dass manche von diesen Methoden erfunden wurden auf in der Zeit, in der das Hauptspeichermedium Magnetbänder waren, wo man also nur durchspulen kann und sequentiell lesen kann, während irgendwo in die Mitte der Eingabe springen. Heißt, ich muss das Ding umspulen und das dauert.

15:24 Äh, also auch dafür war das dann praktisch. Auch da war nicht klar, wie groß die Eingabe ist vorher. Die Idee für Merch Sort ist, die gleichen Merches zu machen für diesen Bottom up Merch Sort, aber die Reihenfolge ein bisschen zu tauschen. Also wie eben im Bild schraffiert, kann ich erstmal diese benachbartten Pärchen von einzelnen Elementen alle verschmelzen. Das hätte der rekursive Merchsort auch getan, aber zeitlich anders angeordnet. Wenn ich das alles gemacht habe, dann weiß ich jetzt, meine Eingabe hat jeweils Paare, die schon sortiert sind. Also, sie hat Runs der Länge 2 überall. Wenn ich das eh weiß, dann kann ich auch jeweils zwei davon nehmen und die zu einem Run der Linge 4 verschmelzen, ohne überhaupt noch mal reinzugucken. Das weiß ich einfach. Ich habe es ja gerade so hergestellt. Das heißt, ich habe einen nächsten Durchgang, wo ich immer Runs der Linge 2 zu einem Run der Länge 2 Runs der Länge 2 zu einem Run der Linge 4 verschmelze.

16:28 Danach weiß ich, die Eingabe besteht aus lauter Runstänge 4. Das heißt, ich kann den nächsten Durchgang machen und die zu acht verdoppeln und so weiter. Und sie sehen, ich musste dafür gar nicht wissen, wann das Ende ist. Sobald ich irgendwann am Ende angekommen bin, sagt die Eingabe: "Ah, jetzt ist übrigens vorbei." Dann sage ich: "Okay, dann höre ich jetzt auf und fang von vorne an mit dem nächsten Durchgang." Aber ich musste nicht vorher planen, wie viele dieser Paare ich äh generieren muss. Das meinte ich mit, man muss das N kennen.

16:58 Und im Code sieht das dann äh auch wieder ähm erstaunlich kompakt aus. Wir haben eine äußere Schleife über die Größe der Runs, die wir jetzt ähm schon vorfinden. Am Anfang eins, das heißt, ich fange an mit den einzelnen Elementen als ein Run jeweils. Ich höre auf, wenn die Runlänge größer ist als n, dann ist es nämlich nur noch ein Run und in jedem Schritt verdopple ich die Größe. Dann habe ich eine Schleife, die durch das Array einmal durchgeht, aber in Sprüngen der Länge size. Ähm, also zweimal size, weil ich immer zwei auf einmal verarbeiten kann. fang am linken Rand an und springe solang ein bisschen hier subtiler Schritt ist, wann ich aufhören muss. Da reicht's eben aufzuhören, wenn ich keine wenn ich höchstens [räuspern] einen Run am Ende noch habe. Das war hier in dem Beispiel so gewählt, dass die Eingabe eine zweier Potenz lang ist. dann passiert das nicht. Wenn man hier noch ein einzelnes Element gehabt hätte, dann wäre da irgendwie noch so ein einzelnes Element rumgelegen, was immer nicht mit aufgenommen wird.

18:11 Und erst in dem letzten Schritt hätte ich dann noch mal einen ganzen Merch gemacht, um das Q da irgendwo einzusortieren. Macht aber auch nichts. Also, der Code kommt damit wunderbar zurecht und jeder innere Aufruf ist eben zwei Runs der Länge size zu einem der Linge zweimal size verschmelzen. auch da wieder um den Randfall für die letztten Merch zu händeln, kann man kompakte Formel schreiben.

18:42 Also typischerweise ist das langsamer als der alte Merchsort mit den rekursiven Aufrufen. Das hat wahrscheinlich hauptsächlich mit Cash Lokalität zu tun. von der Anzahl ähm von der Anzahl Operationen, die äh dieser Algorithmus ausführt, ist der hier wahrscheinlich besser.

18:59 Aber äh auf moderne Architektur ist eben die Speicherhierarchie wichtiger in dem Fall. Sprich, ist nicht die das Mittel der Wahl in den meisten Fällen, aber sie sollten so im Hinterkopf behalten, dass man Merchsort auch nicht rekursiv umsetzen kann und dann auch ähm nicht wissen muss vorher, wie groß die Eingabe ist, während der rekursive Algorithmus, der springt in die Mitte. Das macht nur Sinn, wenn ich weiß, was n ist.

19:36 Okay, dann ähm ist ein guter Zeitpunkt für unsere Pause und für Fragen zu Merch Sort, wenn Sie noch welche haben. Ah, okay. Okay, lassen Sie mich einen Kommentar noch anbringen. Ähm, das passt gut in das Merchort Kapitel rein. Ähm, lassen Sie uns das noch anhängen. Da geht's um die Frage nach dem stabilen sortieren.

19:56 Äh, was hat's damit auf sich? Wenn wir eine ganze Tabelle von Objekten haben, wo ich also die Zeilen sortiere mal nach einer einen nach mal nach der anderen Spalte, kann ich z.B. hier ähm diese Liste von Studies sortieren nach Namen. Das heißt, jetzt sind die sortiert nach den Namen und danach sortiere ich sie nach Section. Äh, das ist aus dem amerikanisches System, wo man äh manchmal die Vorlesung, wenn sie zu groß sind, mehrmals hält und dann in verschiedene Räume aufteilt, äh haben wir hier glücklicherweise meistens entweder groß genuge Räume oder äh klein genug die Kohle. angenommen macht das hier nach diesem A zu sortieren, dann wäre es ja schon irgendwie nett, dass jetzt die Sortierung innerhalb von einer Section noch äh die Sortierung von vorhin aufrechter erhält, aber das passiert nicht unbedingt. Äh sie können den Code ähm aus der Bibliothek dafür ausprobieren. Wenn man nicht aufpasst, passiert es nicht. Dann zerstört dieser zweite Sortiervorgang nach dieser Spalte mit den vielen Duplikaten die Sortierung in der ersten Spalte, selbst unter denen, die den gleichen Eintrag da haben.

21:12 Und ähm wenn man das nicht möchte, dann möchte man eigentlich stabil sortieren. Das heißt, Elemente, die gleich sind bezüglich des Kriteriums, nachdem wir jetzt sortieren, behalten die ursprüngliche Reihenfolge, die sie in der Eingabe hatten. Das bedeutet, insbesondere alle Studies in Section A hier müssen die Reihenfolge in der Eingabe behalten. Das heißt, die Sortierung nach Namen. Das ist ganz oft natürliche implizite Annahme, die man hat, wenn man sortiert. Man möchte das oft und ähm kriegt das aber nicht automatisch mit den Algorithmen, die man sich fürs Sortieren so überlegt, wenn man nicht aufpasst. Ähm, mit Merchort ist es aber tatsächlich so. Ähm, noch ein Beispiel dazu, mit Merchsort ist es tatsächlich so, dass man, wenn man das nicht ähm kaputt spielt, im Merchritt ein stabiles Sortierverfahren bekommt. Also Merch hätte dieses Problem nicht, hätte die Reihenfolge nicht verändert. Äh, kann man induktiv beweisen, indem man sich anschaut, was im Merch passiert und was dann äh über die Rekursion passiert.

22:19 Aber das sozusagen ein wichtiger Pluspunkt für Merch Sort, wo wir auch sehen werden, ähm, dass der nicht von allen Algorithmen ohne weiteres erreicht wird.

22:37 Der Kern, um Merch stabil zu machen, ist, dass man hier den passenden Vergleich macht. Da darf man das nicht durch ein kleiner Gleich ersetzen. Können sich überlegen, warum das dann ausreicht. Ähm, um das zu zu in Beispiel zu zeigen, lohnt es sich Duplikate sozusagen zu markieren nach der Reihenfolge, wie in der sie in der Eingabe kam, während der Algorithmus aber nur den Buchstaben sieht und dann einfach zu schauen, was passiert. Und für Merch müssen wir einfach denen, die im linken Run kommen, Priorität geben. Also, wenn Elemente gleich sind, dann nehme ich das vom linken Run, weil das links in der Eingabe stand. Das ist alles. Mehr muss man bei Merch nicht tun. ist nicht kompliziert, aber es ist eine Eigenschaft, die eben Merchsort besonders auszeichnet.