Video 12-1: Forschungsvortrag Teil 1: Java's Dual-Pivot Quicksort

0:03 Ja, ich freue mich, dass ich Ihnen noch ein bisschen, dass wir noch ein bisschen Zeit übrig haben, etwas aus der Forschung zu erzählen. So sortiert man heute ähm zumindest in Java. Äh ich will ein bisschen Kontext geben, der gar nicht unbedingt mit sortieren so sehr zu tun hat und dann schauen wir uns konkret die zwei großen Sortieralgorithmen an, wie auch schon angeteasert, die in in der Java Library zum Einsatz kommen und die beide nicht besonders alt sind. Das ist der vielleicht weniger ähm übliche Teil. Also erster Kontext war natürlich ähm wie schon angesprochen, sortieren hat mich irgendwie nicht mehr losgelassen und sowohl dieser Quicksort, der in Java drin ist, als auch ähm die Merch Sort Variante äh hat das so ein bisschen ähm beidseitig Spuren hinterlassen. Aber lass uns noch einen kleinen Tick weiter ausholen. Warum machen wir überhaupt ich als eine Person, sowohl hier diese Vorlesung als auch Lehre? Äh, das ist eine deutsche Erfindung, die Sie sicher kennen. Das das humbsche Bildungsideal ähm aus in einer Weile her jetzt mittlerweile äh besteht im Prinzip darin, dass man Forschung und Lehre als Einheit begreift, plus dass man auch Forschungsfreiheit sehr ähm breit definiert und dass die Universitäten dementsprechend das auch unterstützen sollen. Was heißt Universität? Das ist gar nicht äh Zufall, dass es so ähnlich klingt wie Universum. Das ist einfach das lateinische Wort für das ganze. Also die Uni Uni heißt eigentlich so, weil der lateinische Begriff Universitas Magistrum et Skolarium die Gesamtheit der Lehrer und Schüler bezeichnet oder Studenten bezeichnet und ähm irgendwann hat man es verkürzt auf Universität, aber das ist wo herkommt. Frage.

2:03 Äh, also die die Frage war, steht Universität für die Gesamtheit der Felder? Das ist heute sicher so. Ich weiß nicht, ob das ähm gut 200 Jahre ist es auch nicht beliebig lange zurück. Wenn man noch weiter zurückgeht zu den ersten Universitäten, ist ja die Breite der Fächer auch so ein bisschen fragwürdig. Ähm, meines, ich kenne nur diese diese äh Herleitung. Ähm mag aber sein, dass es nicht die einzige ist. Ja, wie oft bei so Begriffen? Ähm, man kann sich ja trotzdem fragen, sollte Sie das überhaupt noch interessieren heutzutage? Und ich denke, es gibt gute Gründe, warum auch bei der Wahl des Studienorts ähm das eine Rolle spielen kann, wo interessante Forschung passiert aus diversen Gründen, teilweise auch einfach nur indirekt, ähm weil sie da auf Leute treffen, die für zumindest ein Thema sehr motiviert sind. Ob sich das dann auf die Lehre durchschlägt, bleibt die Hoffnung, aber oft ist das, glaube ich, schon so. Na ja, und äh hier ist es natürlich Eulen nach Athen tragen. Sie sind ja schon da an der Univ an der Universität.

3:04 Sie kennen vielleicht dieses Bild. Wenn nicht, dann schauen Sie im Gang, im Mehrzweckgebäude hängt das in groß. Können Sie ein bisschen gucken, äh was die Informatik so ausmacht. Vor allem ist spannend, dass die Informatik immer noch ähm mehr Kraftfach geteilt ist. Da gibt's diesen Theorieteil, der fast Mathematik ist. Es gibt diesen Engineering Teil, wo es drum geht, Dinge zu bauen, die dann funktionieren und es gibt einen großen Anwendungsteil. In anderen Disziplinen, wie sagen wir den Naturwissenschaften, hat sich das irgendwann in strikt getrennte Fachbereiche aufgeteilt. Wir haben ja hier keinen Maschinenbau oder so dergleichen, aber das ist letztlich angewandte Physik in äh am Ende vom Tag, aber eben angewandt mit einem bestimmten Ziel. und die Reine für Sie, die als Naturwissenschaft verstehen möchte, was die Welt dem zusammenhält und so weiter, ist ein eigener Bereich. In der Informatik ist das nicht so. Wir sind immer noch beides in einem, sowohl die ähm die theoretischen Überlegungen, was ist Berechnungen, was was kann man überhaupt machen, äh was kann man nicht machen, als auch wie baue ich jetzt ein konkretes System, um irgendeine Aufgabe zu lösen?

4:07 Äh, ich verorte mich natürlich als theoretischer Informatiker schon eher in diesem ähm lillannen Teil der Grundlagen, aber die Distanz in der Informatik zwischen Grundlagen und Anwendung ist teilweise sehr sehr gering.

4:24 Neben dem, was ich Ihnen heute vorstelle, interessieren mich Datenstrukturen, die wenig Platz brauchen und äh bisschen was wer wir auch zu dem letzten Punkt sehen. Also Algorithmen, die die den West dem Worst Case versuchen, ein Schnippchen zu schlagen. Ähm und äh das das ist ein schöner Teil in der Informatik, dieses diese Gesamtheit, dass wir Theorie und Praxis immer noch unter einem Hut haben und dass die Distanz wirklich kurz ist, werden Sie gleich sehen. Zumindest in diesem Teil. Sortieralgorithmen sind relativ schnell in der Praxis zu finden. Und an der Stelle ein Begriff, der schon auftauchte, ist diese Idee adaptiv sortieren, dem worst case ein Schnippchen schlagen. Was kann das beim Sortieren konkret heißen? Ähm, wenn meine Eingabe komplett zufällig ist, dann gibt's nichts, was ich ausnutzen kann. In vielen Anwendungen hat die aber so eine gewisse Vorsortiertheit und das sind so ein paar Beispiele, wie das aussehen kann. Ja, wir werden später noch einiges mehr zu diesem ähm zu diesen Runs sehen, wo man also schon Segmente in der Eingabe hat, die schon sortiert sind.

5:31 Äh für viele von diesen Dingen, das ist so ein bisschen jetzt äh 30 Jahre zurück, hat man sich theoretisch überlegt, wie kann man damit bestmöglich umgehen, aber die haben wenig Einfluss in der Praxis gehabt. Und zumindest beim Sortieren ist meine äh meine Idee immer, wenn ich irgendein cleveres Verfahren habe, das vielleicht irgendwie dem Worst Case ein Schnippchen schlagen will, dann muss es schon besser sein als irgendein plumper ander anderer Algorithmus. Und wenn die Unterhaltung am Ende zwischen den Sortieralgorithmen so ist, dass dieser clevere adaptive Algorithmus, jetzt weiß ich genau, was ich tun muss und dann bin ich ganz schnell. Äh und Quicksal sagt, das ist aber schön, ich bin schon fertig, dann bringt es alles nichts. Also die ähm der der Spielraum, um aus diesem cleveren Vorgehen Kapital zu schlagen, ist beim Sortieren sehr gering, einfach weil das Problem einfach ist und relativ schnell zu lösen ist selbst im Worst Case. Quicksot ist natürlich im Worst Case quadratisch, wissen Sie für die Klausur, aber in der Praxis eben nicht, weil man mit Randomisierung diesen Worst Case niemals sieht.

6:37 Was auch ein bisschen angeklungen ist als Kontext in der Vorlesung, ist zwei Extreme, die ich hier ein bisschen sehr kontrastiert darstelle, die sind in der Praxis auch nicht ganz so ähm krass im Widerspruch. Auf der einen Seite können Sie Algorithmen als Engineering Disziplin betreifen. Wir wir bauen was auf einer Maschine, wir testen das auf den Eingaben, die uns gerade interessieren und dann ähm machen wir den hier und hoffen, dass das sich verallgemeinert. Die andere Welt ist die Theorie der Algorithmen, in die wir dann auch eingetaucht sind. Also, ich hatte Ihnen nah gelegt und die Kilonova Aufgaben sind so ein bisschen auf der linken Seite. Wenn es die Tests besteht, ist alles gut und mehr interessiert uns theoretisch an der Stelle nicht. Die andere Welt war, wir beweisen worst case groß Schranken. Haben wir viel gemacht. Und das Schöne daran ist natürlich, wenn die bewiesen sind, dann gelten sie immer und da gibt's nichts dran zu rütteln und wenn die gut genug sind, dann ist das auch perfekt.

7:33 Aber manchmal ist das ein sehr pessimistischer Blick auf die Welt und wenn man seine Algorithmen optimiert mit dem schlimmstmöglichen Szenario, kann das eventuell eine schlechte äh schlechte Maßzahl sein. Also schöner wäre da eine Brücke zu schlagen und das ist das, was ich auch in der Vorlesung schon mit mit Algorithm Science betitelt hatte. Also die Idee aus beiden Welten Dinge zu kombinieren, zwar Messungen zu machen, aber vielleicht nicht nur Laufzeit, die so schwer kontrollierbar ist und sehr spezifisch für eine Eingabe und Maschine ist, sondern etwas etwas abstrakteres, z.B. beim Sortieren. Vergleiche zählen hilft schon bisschen, ist wenigstens nicht maschinenabhängig. Und der zweite Teil ähm genauer hingucken als den worst case, wo immer das Sinn macht. Und wenn das gut geht, hat man dann eine Vorhersage, die so ein bisschen zwischen den Welten interpoliert.

8:27 Wir schauen uns speziell Beispiele aus der Java Bibliothek an. Warum? Na ja, weil sich da viel getan hat. Äh die Geschichte kennen Sie im Prinzip schon. Es gibt diese zwei Algorithmen aus unerfindlichen Gründen beide im Jahr 2009 endgültig aufgenommen äh äh designed und in ähm kurz darauf aufgenommen hat nur zwei Jahre gedauert für den Quicksorder und das ist eher ungewöhnlich, dass sich bei so elementaren Algorithmen so viel noch rausholen lässt, dass sich die Bibliotheken da äh beeinflussen lassen, was zu ändern. Die beiden Beispiele will ich Ihnen kurz vorstellen. Das erste ist der Dual Pivot Quicksord in Java. Ähm, ein bisschen die Historie zu der Implementierung von Quicksot Java vorher will ich gar nicht im Detail besprechen. Äh, was ich an der Stelle nur sagen möchte, da gab's so einige Entwicklung sehr früh und da gab's noch mal ein bisschen Ideen Dinge zu verbessern in den 90er Jahren und dann war eigentlich die Sache gegessen und ist nicht mehr viel passiert und sogar der gleiche Algorithmus ist in in der C Library und in der Java Library gewesen damals und in allen möglichen anderen Bibliotheken hat man wesentlichen die gleichen Ideen verwendet und dann gab es auf einmal irgendwie diese ähm Neuerung in Java jetzt zwei Pivots statt einem zu verwenden und hat relativ schnell den ein Einstieg gefunden in die Deployen Libraries.

9:57 Warum macht man sowas? Da muss es schon gute Gründe geben und in dem Fall sind einfach die Laufzeiten relativ dramatisch ähm und sprechen für diesen neuen Algorithmus. Also hier sind die beiden ähm Implementierung aus den Bibliotheken und die diese Laufzeiten hier, die sind normalisiert, ne? Das ist die Zeit geteilt durch n log n. Sie wissen, sortieren sollte ungefähr n log n Zeit brauchen asymptotisch. Das heißt, wenn ich dadurch teile, will ich eigentlich eine gerade Linie sehen. Und das sehen wir auch. Wir sehen aber zwei Linien und eine ist viel höher. Da ist zwar ein bisschen hier die Achse abgeschnitten, also nicht äh wundern, aber 9:7 ist relativ dramatisch, wenn man in dem Bereich vom Sortieren um schaut, da noch mal 10 % irgendwo Laufzeit rauszuholen, erwartet man eigentlich nicht. Also irgendwas ist da passiert und ähm die Frage, warum dieser neue Algorithmus schneller ist, war dann die Frage, die mich umgetrieben hat. Witzigerweise, die äh Maintainer von der Bibliothek fanden das gar nicht so wichtig. Die haben gesehen, der neue Code ist schneller.

11:01 Sie haben sehr gründlich und auf sehr vielen Eingaben getestet und haben ihn überall für gut befunden. Und warum das jetzt besser ist, das fand sie keine Frage, die jetzt ein nachtswach. Das ist vielleicht so die Seite der Engineering Teil und der ähm der Strukturwissenschaftler in mir fand das sehr unbefriedigend. Dementsprechend habe ich mir das genauer angeguckt und man kann ja erstmal rauszoomen und die Frage stellen, was ändert sich denn da überhaupt? Klassischer Quicksort, so wie wir sie auch wir es auch besprochen haben, verwendet ein Pivot, dann vergleiche ich alle Elemente mit diesem Pivot und sie sind entweder kleiner oder größer. Nehmen wir an, die sind alle unterschiedlich, also es gibt keine Duplikate jetzt erstmal. Und dann muss ich die eben umsortieren, so dass die kleinen links, die großen rechts sind, das Pivot in der Mitte und dann mache ich rekursiv weiter. Quicksot in einer Minute. Die Details, wie man das hier dann schnell macht, kennen sie ja mittlerweile sind natürlich schon auch spannend, aber eigentlich ja alles, da hat sich nicht viel getan seit der 60er Jahre, um ehrlich zu sein.

12:04 Was passiert, wenn ich jetzt zwei Pivots habe? Eigentlich gar nicht viel. Ich wähle eben zwei Pimos und habe dann jetzt drei mögliche Klassen für die Elemente. Kleiner als beide damit, dazwischen und größer. Und ich muss diese drei Klassen voneinander trennen. Äh, das ist äh mit diesem Dutch National Flag, das ist eine eine Programmieraufgabe von dem Dikra, über den wir ja vorhin gesprochen haben, der dann auch diesen Grafalgorithmus entworfen hat. Ähm von ihm stammen Bücher zum Programmieren lernen und da ist dieses diese genau diese Aufgabe, man hat Elemente an drei Farben und möchte diese umsortieren, damit sie entsprechend der der niederländischen Flagge angeordnet sind, hat er als Programmieraufgabe dargestellt.

12:47 Also ist auch grundsätzlich nicht schwierig zu machen, wie man das ähm wie man das ganz effizient macht und ohne zusätzlichen Speicher ist ein bisschen interessant. Deswegen schauen wir uns das kurz an. Und das ist tatsächlich die Neuerung in dieser Java Implementierung von dem Dual Pit Quicksort.

13:11 Okay, wir machen ähm ich ich zeige Ihnen hier den Code. Das ist der Quicksot, wie wir ihn ungefähr gesehen haben in der Art von Pseudo Code. Ähm wie wir es auch besprochen hatten, arbeitet der sich von außen nach innen in die durch die Eingabe mit so zwei ähm zwei Indizs, die aufeinander zulaufen. Wenn Sie sich erinnern, war genau was wir auch gemacht hatten. Und es ist im wesentlichen symmetrisch von links nach rechts. Und ich habe eben diese zwei ähm Indizes K und Gann. Passt ganz gut auf Deutsch mit kleiner und größer. Das ist aber irgendwie Zufall, weil das aus dem aus den Originalquellen stammt, die sicher nicht Deutsch sind. Vielleicht äh vielleicht passt es auch auf Russisch, wie auch immer. Ähm, die Invariante, die dieser Algorithmus aufbaut, ist die kleinen Elemente sind links und werden und das das K läuft über diesen kleinen Bereich der, also den den Bereich der Elemente, die kleiner sind und das G läuft über den Bereich der Elemente, die größer sind und dann, wenn sie sich treffen, sind wir fertig. So hatten wir das gesehen auch. Was macht dieser Dual Pivot Quicksort? erstmal viel viel wirrer Code.

14:19 Äh, es gibt jetzt drei Indics, das ist klar, weil ich brauche irgendwie auch drei Bereiche und zwei davon fangen links an, einer fängt rechts an und äh die laufen auch aufeinander zu und diese Zeig, dieses dieser Index L, der wird so ein bisschen hinterher geschleppt. Der trendt dann noch die kleinen und mittleren, aber man muss schon sagen, das ist irgendwie gar nicht so aufgeräumt wie das linke und dass das schneller sein soll, ist erstmal nicht irgendwie einsichtlich.

14:54 Ich denke, der um ein bisschen Zeit zu sparen, erkläre ich Ihnen die Algorithmen nicht so richtig. Äh, ich möchte nur auf eine Sache hinweisen. Äh, wir haben im Grunde diese zwei Indizes K von links, Gs, die aufeinander zulaufen und gewisse Elemente das erste Mal entdecken und dann fragen, welche Farbe hat dieses Element? Und da gibt's einen eine witzige Asymmetrie in diesem Algorithmus. Wenn ich ein Element mit diesem grünen Zeiger erreiche, dann frage ich zuerst, ob es kleiner als das kleine Pivot ist. Wenn ja, es ist klein. Ansonsten muss ich noch einen zweiten Vergleich machen, um die anderen beiden Fälle zu unterscheiden. Und was hier in den Blättern steht, ist jeweils, was ich tun muss. Ich lass gleich die Animation einmal durchhüpfen, aber ich möchte es nicht ganz im Detail besprechen. Ähm, während wenn ich ein Element aus diesem von der rechten Seite erreiche, dann frage ich zuerst nach dem größeren Pivot. Ganz witzig. Warum würde man das machen?

15:48 Also das äh wieder wie wie das funktioniert ist. Wir fangen auf der linken Seite an. K hat sozusagen den Vorrang, dann klassifizieren wir hier dieses Element. Wenn das ein mittleres ist, dann lassen wir es einfach stehen und laufen eins weiter. Weil es ein kleines ist, tauschen wir es nach links und laufen mit beiden Positionen eins weiter. Und für den dritten Fall machen wir jetzt erstmal nichts, sondern übergeben die Kontrolle an den blauen Zeiger von der anderen Seite. Und jetzt macht er eben sein Ding. Ähm, der kann die großen überspringen und wenn er ein kleines findet, dann haben wir so eine so eine dreifach Rotation. Jedes Element hüpft an eine andere Stelle. Äh so funktioniert das. Und wenn sich die Dinger irgendwann, wenn sich die Hauptzeiger K und Groffen haben, dann sind wir fertig. Da habe ich diese Invariante hier unten aufgebaut. Okay, Details davon sind gar nicht so wichtig. Ich werde nachher noch witzig was äh dazu sagen, was da dann weiter passiert ist.

16:43 Lassen Sie uns ganz kurzen Blick drauf werfen, wie viele Vergleiche dieser Algorithmus braucht. Und ähm wenn man sich das so anschaut, es ist ja irgendwie symmetrisch zwischen der Wahl der Pivots. Ähm die präzise Analyse verwendet eine Rekursionsgleichung, die wir im Detail nicht besprochen haben. Hier ähm sehen sehen effiziente Algorithmen. Äh wir wir es reicht zu analysieren, was ein Partitionierungsschritt an Kosten hat und den Rest macht die Rekursion. Äh das dann einfach eine mathematische Lösung. Was macht ein Pitionierungsschritt pro Element? Na ja, entweder brauche ich zwei Vergleiche, wenn ich in diesem unteren Teil lande, oder ich brauche nur einen Vergleich, wenn ich in dem oberen Bereich lande. Habe ich Glück gehabt. Wie viele brauche ich also im Durchschnitt? Ja, ähm wenn diese äh Eingabe zufällig gewählt ist, sind auch die Pivots zufällig, aber es ist ein kleines, ein großes, ich vergleich die. Das heißt, das P1 ist immer kleiner, aber wir sollten im Wesentlichen ähm annehmen, dass es gleich viele von den kleinen, mittleren und großen gibt. Das ist auch im Durchschnitt das, was passiert. Und dann habe ich also für ein Drittel der Elemente einen Vergleich und für zwei Drittel der Elemente zwei Vergleiche.

18:00 Gibt im Schnitt 5 drittel. hier noch mal ausgerechnet. Äh, aber das ist falsch. Das ist nicht, was hier passiert. Und ohne ähm auszurechnen, was genau passiert, können Sie erkennen oder begreifen, warum das falsch ist. Das ist systematisch zu äh pessimistisch, denn hier passieren Korrelationen zwischen diesen zwei Dingen, die sich ändern. Wenn ich eine Eingabe habe, wo aus irgendwelchen Gründen das kleine Pivot relativ groß ist, das heißt, ich habe viele von den kleinen Elementen, dann habe ich natürlich mehr Elemente, die hier in diesem linken Teil landen als im Durchschnitt. Ich habe aber dann auch mehr Elemente, die von dem grünen Zeiger erreicht werden und für die ist gerade dieser kleine Teil günstig.

18:49 Das heißt, in dem Fall habe ich weniger als diese fün drittel Vergleiche, weil ich viele Elemente habe, die nur einen Vergleich brauchen, mehr als im im üblichen Fall. Und das passiert aber auch umgekehrt, wenn das große PO ungewöhnlich klein ist, dann habe ich viele große Elemente, die werden aber dann auch von dem blauen Index erreicht und da sind die großen günstig. Das heißt, ich kann in beiden Fällen nur gewinnen, wann immer meine Pivots irgendwie schlecht sind, ist es eigentlich gut für mich. Sparvergleiche.

19:20 Das ist eine kuriose Eigenschaft mit diesem Algorithmus und ähm das sorgt dafür, dass man im Durchschnitt deutlich mehr als ein Drittel der Elemente mit nur einem Vergleich klassifiziert.

19:31 Und ähm die genaue Rechnung dazu ist ein bisschen länglich. Und da ich jetzt hier eigentlich keine Stochastik und Analyse machen möchte, äh ignorieren wir den Teil. Das ist dann äh was mich lange beschäftigt hat und was einem Spaß machen kann oder auch nicht. Ähm können wir ander mal kann ich ander mal mal mehr zu sagen für die, die das interessiert. Äh für hier schauen wir uns einfach die Ergebnisse an. äh die Variante, die in der Bibliothek verwendet wird, die wählt die Pivots, wie wir es auch besprochen hatten, nicht einfach zufällig, sondern wählt fünf Elemente und nimmt dann hier diese zwei mittleren nahliegende sinnvolle Sache, die man da machen kann, wenn man zwei Pivos braucht. Und dann kann man vergleichen. Also die Anzahl Vergleiche, die diese beide ein beiden Algorithmen haben, die sind durchaus so, dass dieser neue Algorithmus ein bisschen was spart. Eben durch diese Asymmetrie, die ich gerade vorgestellt hatte, hat man tatsächlich weniger Vergleiche als im alten Quicksort, aber es sind auch nur knapp 3 % weniger und die Laufzeit war 10 % besser. Das so ein bisschen seltsam, nicht?

20:43 Und äh wenn man schon dabei ist, kann man natürlich auch andere Dinge zählen statt Vergleiche. Ich könnte auch Schreibzugriffe auf das Array zählen, das ja auch irgendwie Kosten, die verursacht werden. Und da ist plötzlich der neue Algorithmus viel viel schlechter als der alte. irgendwie klar, weil der hier macht nur diese Swaps, die immer paar zwei Element an die richtige Stelle bringen. Ähm, dann dachte ich, na ja, vielleicht schauen wir ganz genau hin und das ist ja, das heißt am Ende ist es kompiliert zu Java Bytecode und man kann präzise zählen, in Erwartung werden genauso viel Java Bytecode Instruktionen ausgeführt für diese zwei Implementierungen. Und das Ergebnis am Ende ist, der neue Algorithmus macht viel mehr davon. Die sollten langsamer sein. H na gut, moderne Prozessoren sind kompliziert. Die machen sowas wie eine Sprungvorhersage für bedingte Sprünge und haben eine Pipeline ähm, die sozusagen neu befüllt werden muss, falls ich mich vertan habe und die der Code woanders weitergelaufen ist, als ich vorher gesagt habe. Details dazu. Ähm K Sie werden lernen, was Pipeline Execution ist in irgendeiner technischen Informatik. Und die Analyse dahinter äh ist so ein bisschen äh komplizierter.

21:56 Das sind hier so Peace drin, weil irgendwelche Integrale sich dazu auswerten. Also unter einem gewissen Modell diese Branch Mispredictions zu analysieren, kann man das ausrechnen. Und wieder ist der neue Algorithmus schlechter. Das ist also auch nicht was bleibt. Na ja, man kann noch äh die Anzahl Zugriffe auf den Speicher nehmen oder die Cashmes, wenn Sie wollen. Und da ist tatsächlich der Unterschied. Da ist dieser neue Algorithmus deutlich besser. Intuitiv, weil er mit den zwei Pivots schneller Fortschritt macht, also die Eingabe schneller in kleine Teile zerlegt, die dann in den Cash passen, so auf äh erste Ernährung.

22:38 Also indem wir uns da einfach alle alle Optionen angeguckt haben, was man so an Kosten haben kann in diesem Algorithmus, kann man durch Ausschlussverfahren quasi sagen, es äh kann eigent diesen Speicherzugriffen liegen. Und das ist auch eine Erklärung, warum vielleicht vor 30 Jahren das anders war, weil sich die Gewichte, was wie teuer ist, in den Rechnern verschoben haben und gerade die Speicherhierarchie ist da so ein bisschen stärkerer Bottelnck geworden als vor 30 Jahren, als dieser klassische Quicksord engineiert wurde.

23:12 Okay, das ist so die Quicksort Geschichte bis zu dem Zeitpunkt, wo ich sie dann verlassen habe. Und dann habe ich noch ganz was Neues für Sie. Eine Komitorin von ihnen hat in ihrer Bachelorarbeit die neue Version analysiert, die Java mit äh Version 23 deployed hat, wo sie den Partitionierungsalgorithmus noch mal völlig auf dem Kopf gestellt haben. Alles, was ich Ihnen vorhin gezeigt habe mit den grünen und blauen Zeigern ist nicht mehr und diese Asymmetrie mit den Vergleichen gibt's nicht mehr. Und die neue Version ist nach allem, was wir so analysiert haben, eigentlich überall noch schlechter. Wir haben also ähm neues Rätsel. Warum diese neue Version jetzt besser ist als die alte neue Version, wissen wir nicht. Vielleicht hat jemand ja eine Idee und hat Lust, das sich anzuschauen. Gut, zu diesem Algorithmus kann man noch viel mehr sagen. Ähm, ich belasse es bei bunten Bildchen. Ähm, genug zu Quicksword.