Video 12-2: Forschungsvortrag Teil 2: Powersort

0:02 Machen wir ein Wechsel zu dem anderen großen Sortieralgorithmus, nämlich Merch Sort und speziell Timsort in der Variante, wie sie Python verwendet. Ähm, sie wissen natürlich, wofür wir sortieren, verwenden. In Python, für die, die da ein bisschen schon was mit gemacht haben, werden sie wissen, gibt's zwei Möglichkeiten zu sortieren. Äh, beide verwenden aber am Ende den gleichen Code unter der Haube. Und was hieß unter der Haube? Äh Python ist ja unter den Programmiersprachen noch ein relativ junges Kind. Erst Anfang der 90er Jahre dazu gekommen. Äh initial ähm offiziell von Gido Van Rossum bestätigt, haben sie einfach genommen, was in der CBibliothek drin war und haben sich um sortieren nicht gekümmert. Deswegen steht da Q Sort, so heißt bis heute die Sortier Funktion in der CBibliothek. Äh, dann haben sie ein anderen Coreveloper engagiert, Tim Peters, der sich das sehr eingebracht hat und dem Algorithmen und gerade sortieren immer schon irgendwie am Herzen lagen. Der hat daran gedoktortt und noch mal gedokt und auch dann äh Forschungsarbeiten als Inspiration da einfließen lassen.

1:12 All diese ähm ersten Implementierung waren keine stabilen Sortierverfahren. stabil kennen Sie noch ähm ist diese Eigenschaft, dass Elemente, die gleich sind, in der relativen Reihenfolge gleich bleiben und die ursprünglichen Implementierungen hatten das nicht und das hat die frühen Benutzer von Python unfassbar genervt. Da gab es mehr und mehr Bug Reports, wo dann Leute sagten, was macht den ihr hier für eine Sortierfunktion, die nervt total, die sortiert nicht richtig. Tat sie natürlich schon, aber eben nicht stabil. Und dann wurde irgendwann Stabilität als Kriterium in die Spezifikation aufgenommen. Und zu diesem Anlass hat Tim Peters diesen Algorithmus, der dann nach ihm benannt wurde, was er übrigens äh nicht gut findet und was so ein Insider Joke bei den ähm Cordelopern war, der dann irgendwie außer Kontrolle geraten ist. Und jetzt steht er als diese äh wenig wenig bescheidene Person da, die diesen Algorithmus nach sich benannt hat, aber so war es eigentlich nicht. Na, jedenfalls hat es sehr viel Spaß dran gehabt, diesen Algorithmus äh zu entwerfen, der dann jetzt in Python lange lange verwendet wurde. Äh, ich werde gleich noch mehr dazu sagen, was das dann unter der Haube ist.

2:25 Und ähm es gab ein eine Komponente von diesem Algorithmus, die so etwas problematisch ist. Dazu gleich noch ein paar Details und die ist mittlerweile ersetzt durch ähm eine Lösung, die wir gefunden haben äh in der Zeit, als ich als ich Postock in Waterl war. ähm und die die dieses Problem schön löst und mittlerweile in verschiedenen Python Implementierung vorkommt und wir sind so ein bisschen am Arbeiten, die wir anders auch unterzubringen, wo Timsort verwendet wird. Äh noch mal zur Erinnerung, stabil sortieren hatte ich eben schon gesagt, ist dann relevant, wenn man eine Liste von Daten nach mehreren Kriterien sortiert, z.B. erst nach vor nach Vornamen und dann nach Nachnamen, dann hätte ich gerne, dass alle Simpsons immer noch nach Vornamen sortiert sind. Und das ist genau, was auch in vielen Anwendungen eben verwendet wird. Deswegen möchte man stabil sortieren in so einem allgemeinen Verfahren, was Objektes sortiert.

3:23 Welchen Sortieralgorithmus würden Sie verwenden, wenn Sie einen stabilen Sortieralgorithmus brauchen? Gute Klausurfrage. Ähm, können Sie im Hintergrund behalten. Ja, Merchord natürlich. Genau. Ähm, tatsächlich gibt's so so ein bisschen Tradeoff, hatte ich auch in der Vorlesung schon angedeutet. Äh, Quicksot ist in der Regel schneller und ist auch in place, das ist gut, aber eben nicht stabil. Merch ist fast so schnell, aber nicht ganz und braucht extra Speicher für den Puffer beim Merchen. Äh, ist aber dafür stabil. Das heißt, irgendwie gibt's so ein ähm Situation, wo man sich zwei von drei Sachen aussuchen kann, aber nicht alle drei zusammen. Und in Python ist eben die Optimierung so, dass ich eh alles als Objekte modelliere. Also Speicherparen ist sozusagen schon der Zug ist abgefahren. Dementsprechend ist die Wahl auf Merch Sort gefallen und Timsord ist am Ende vom Tag Merchsort, aber in der seltsamen Art und Weise. Von dieser Folie sozusagen möchte ich nur mitnehmen, dass es mehr zu Timsort zu sagen gibt, als ich Ihnen heute vorstellen werde. Und diese drei letzten Punkte sind auch spannend und sozusagen dann ähm gebührt Tim Peters die ähm die Ehre oder die der der die Anerkennung für diese anderen Teile. Äh die sind aber unverändert geblieben oder nicht Teil von der Geschichte von heute. Das heißt nur so erwähnt, da gibt's noch ein paar andere cleverere Tricks und die sind nach wie vor da drin und funktionieren gut. Was wir uns anschauen werden, ist nur dieser erste Teil.

4:59 Merchort kann ähm entweder bottom up oder top down implementiert werden, wie wir es besprochen hatten. Aber das ist nicht die einzige Option. Ich kann es auch von links nach rechts machen. Was soll das denn heißen? Na ja, kommen wir gleich zu. Ähm die Idee oder der das Ziel an dieser anderen Art Merch so zu machen ist vorsortierte Runs zu verwenden, auszunutzen. Sehen Sie das Bild von ganz am Anfang. Und runere von von I bis J im Eingabearray, in dem die Eingabe schon aufsteigend oder absteigend sortiert ist. Wenn wir das machen wollen, also solche Runs ausnutzen, dann muss ich mir Gedanken machen, wie ich die in welcher Reihenfolge danach verschmelze. Die Frage stellt sich bei normalem Merchsort nicht, weil das durch die Rekursion einfach gegeben ist. Aber hier äh haben wir mehr Freiheit und wir sollten die ausnutzen. Das ist so der Punkt. Und diese Entscheidung, was wir da tun, das das nennen wir Merchge Policy. Das ist der Teil, wo ähm es ist eine Änderung gab.

6:00 Timsort sieht sonst grob so aus. Äh, das ist so eine Art Python Code. Ähm, müssen Sie können Sie einfach als Pseudo Code lesen. Ähm, wir haben einen Stack von Runs, eine Tod-Do Liste und ähm wir finden immer den nächsten Run in der Eingabe, packen den auf die Tod-Dohl Liste. Diesen Run müssen wir irgendwann mit den anderen verschmelzen, aber wie man so macht, man packt erstmal auf die Tod-Do Liste, kann man später noch uns drum kümmern. Ähm und das später sind gewisse Regeln für die Längen der Runs auf dem Stack. Und wenn diese Regeln sagen, wir müssen was tun, dann machen wir das. Z.B. gibt's die erste Regel, die sagt, wenn der oberste Run länger ist als der dritte auf dem Stack, dann verschmelzen wir den zweiten und dritten Run. Logisch, oder? Also, ich fand es nicht. Wenn das nicht der Fall ist, gehen wir übrigens zur nächsten Regel und falls die auch nicht anwendbar ist, prüfen wir noch die dritte Regel. Und wenn keine von denen anwendbar ist, dann machen wir ein F lens und machen eben jetzt keinen Merch und gehen dann weiter und erkennen den nächsten Run der Eingabe.

7:10 Aus finde ich durchaus äh unintuitiven Gründen funktioniert diese Art von Regeln hier ganz gut. Insbesondere haben sie das folgende Ziel gehabt, dass äh wenn ich auf diesem Stack von oben nach unten gucke, die Länge dieser Runs exponentiell größer wird. Ganz konkret ausgedrückt als hier diese Ungleichung. Ein Run hier ist größer ist ähm von unten geschaut. Ein Run hier ist größer als die zwei, die oben drüber liegen zusammen. Das ist dann sowas wie Fibonacci Zahlen und die wachsen exponentiell. ähm Details nicht wichtig. Das heißt aber, wenn das gilt, dass der Stack in der Höhe begrenzt ist und das wollte man haben logarithmisch in der Anzahl der Elemente in der Eingabe, damit man dafür nicht viel viel Overhead hat.

8:00 Warum genau diese Regeln? Na ja, äh da hat Tim Peter sich öffentlich zu geäußert und gesagt, da habe ich eigentlich nicht viel drüber nachgedacht, ich habe bisschen rumprobiert, die haben funktioniert und habe ich es dabei belassen.

8:16 Tatsächlich ähm was er dahinter, was er gerne wollte war, dass man eben einen kleinen Stack hat, dass es ganz gut funktioniert, falls die alle gleich lang sind, dann sollte es so ähnlich ausgehen wie äh Standard Merch Sort und es sollte bitteschön einen Endlock and Worst Case haben. Es ist immer noch Merch Sort. Äh, da ist ein Sternchen dran, nicht ohne Grund.

8:36 Erstes Problem, sie erinnern sich an diese Inviariante von eben. War gerade auf der Folie, diese Fibonacci Zahlen, die gilt leider nicht. Ist aufgeflogen, als ein Team von Verifikationsforschern versucht hat, ihr neues Tool, das Java Code formal verifizieren kann, zu testen an einem nicht ganz langweiligen Beispiel. Und sie dachten, eine Sortierfunktion aus der Library ist auch ein gutes Beispiel. Lass uns mal beweisen, dass die sortiert und sie haben es probiert und probiert und wie diese Systeme so sind, kriegt man immer neue Lemmers, die man dann wieder beweisen soll und die führen zu neuen Lemmers, die man wieder beweisen soll und das hat irgendwie kein Ende gefunden, bis sie gemerkt haben, da ist tatsächlich ein algorithmischer Bug dahinter und diese Invariante, die gilt nicht ganz, die gilt fast, aber nicht wirklich, die kann man verletzen und das hatte durchaus dramatische Konsequenzen, zumindest potenziell, denn Auf Basis dieser Innariante kann ich berechnen, wie groß dieser Stack jemals werden kann, wenn die Invariante gilt. Und dann kann ich meinen Stack als Fixed Size Array Stack implementieren. Das ist die schnellste Variante für ein Stack. Ist also eine gute Idee, aber keine gute Idee, wenn der Stack größer werden kann, als dieses Array groß ist. Und ähm wie das dann ebeno ist, die Implementierung in Python ist C. Da passiert, merkt man nicht mal, dass man oben rausläuft. Es gibt einfach ein Stack Overflow und kann zu beliebigem Code ausführen führen. In Java hatten sie Glück, weil es nur passieren kann, wenn sie mehr als zwei Petterbite Arbeitsspeicher haben. Da gab's wahrscheinlich nicht so viele Maschinen, wo das passiert ist. Das gleiche Problem gab's aber in der Java Bibliothek auch und aus ähm Detailgründen passiert es da schon deutlich früher. Ähm durchaus realistisch, dass das mal passiert. In Java gab es keinen beliebigen Code, aber eine Exception, auch nicht unbedingt, was man von der Sortier Bibliothek erwartet.

10:31 Äh, dann haben sie sich auch noch ein Patzer erlaubt und den echten Fix, den es dafür gibt, sie nächste Folie nicht direkt implementiert, sondern so ein Patch. Lass uns einfach den Stack bisschen größer machen und das ist noch mal um die in den noch mal um die Ohren geflogen. Man kann diese Regeln retten, indem man eine vierte hinzufügt, die noch einen Stack weiter nach unten in ein Run weiter unten in den Stack guckt und dann gilt tatsächlich diese Invariante und auch die anderen Eigenschaften, die man gerne hätte. Aber nur, um zu beweisen, dass der Algorithmus im Worst Case nicht mehr als NLOG N Vergleiche braucht, braucht man ein zehnseitiges Forschungspaper mit tiefer Matte. Und das ist vielleicht nicht ganz was so ein einfaches Sortieralgorithmus äh Analyse, wie das aussehen soll. Die Rekursion für Merch Sort haben wir hier im ersten Semester gemacht. Das ist Master Theorem und sonst nichts. Also irgendwas hängt da schief.

11:28 Es kommt noch mehr oder kommt noch schlimmer. Auch mit dieser Variante macht Timsort diese Merch Policy manchmal dummes Zeug. Was ich damit meine ist, man kann Eingaben bauen, wo immer und immer wieder ein sehr langer Run, also sehr lange sortierte Liste, um ein Element erweitert wird und die ganzen Daten werden dafür einmal gelesen und einmal geschrieben, um ein Elementfortschritt zu machen. Und das muss hier nicht sein. Ich kann anders die äh die Runs gruppieren und habe viel weniger Aufwand insgesamt. Timsort zieht das nur nicht, weil diese vier Regeln halt doch irgendwie nicht der Weisheit letzter Schluss sind. Äh wissen wir zumindest jetzt. Also ich kann damit 50% mehr Aufwand haben, als ich haben müsste. Und an der Stelle ähm habe ich mich erinnert gefühlt an ein Spruch von so ein paar Software Engineering Kollegen If you're riding a dead horse get off. Was immer einfach klingt, wenn man so Techdept angeh hat, ist es manchmal gar nicht so einfach zu entscheiden, wann ist das Pferd jetzt wirklich tot und wann muss ich das System neu implementieren. Aber zumindest für diesen Algorithmus sah es so aus, als seid ihr einfach hinüber.

12:42 Also lassen Sie uns den ersetzen und das ist dann was bei Powersord passiert ist. Ich drücke ein bisschen aufs Tempo. Ähm, die Aufgabe, die dahinter steckt, die Lösung für mich war im Wesentlichen besser zu abstrahieren, was wollen wir hier eigentlich für ein Problem lösen und dann eine Lösung zu suchen, die irgendwie äh verstehbar und intuitiv ist, wenn man auch genügend sozusagen passende Theorie drauf werfen muss. Für die Frage, die wir uns hier stellen, ist wir haben runs in der Eingabe und wir wollen entscheiden, in welcher Reihenfolge wir die verschmelzen. Und es gibt so ein paar Constraints, insbesondere, wenn das stabil sein soll, können Sie überlegen, dann darf ich nur benachbarte Runs merchen. Können Sie überlegen, das kann man immer die Stabilität kaputt machen, wenn ich irgendwas anderes tue. Also in jedem Schritt kann ich zwei Runs nehmen, die nebeneinander sind und die zu einem verschmelzen. Und das machen wir so lang. äh guck until dann, bis wir nur eine lange Liste haben. Und alles, was ich damit machen kann, ist letztlich ein binärer Baum über diesen Blättern von Runs. Also ist die Frage äquivalent dazu, welchen Baum sollte ich denn wählen? Was ist der beste Baum?

13:53 Was heißt beste? Ähm, um uns das Leben ein bisschen einfacher zu machen, nehmen wir einfach die Größe von all diesen Zwischenergebnissen. Das ist etwa der Aufwand an Daten, die ich schreiben muss und damit halbwegs proportional zu den Kosten.

14:13 Die Modellierung von dem Problem hilft insofern als dass wir jetzt eine klare Frage haben gegeben, diese Blätter mit gewissen Längen. Was ist der bestmögliche Baum?

14:21 Ähm, ich will eventuell nicht den bestmöglichen Baum, sondern nur einen guten, weil ich will den schnell finden. Sonst erinnern sich an die Unterhaltung, sagt Quicksot, ist ja schön, du hast deinen Baum gefunden, ich bin schon fertig mit sortieren. Also, es muss schnell gehen. Äh, dankwerterweise ist dieses Problem äquivalent zu einem wohl äh untersuchten Problem, nämlich der Suche nach einem optimalen Vinieren Suchbaum. Klassisches äh Problem, was man erklärt, wenn man dynamisches Programmieren lehrt, sehen Sie in effiziente Algorithmen. Äh damit kann man das optimal lösen und man kriegt auch eine untere Schranke und so weiter. Da kann man also, wenn man das auf die richtige se die richtige Weise anguckt, eine ganze Menge von existierenden Forschungsergebnissen einfach anwenden. Man muss nur die Verbindung erkannt haben. Außerdem gibt es dazu ähm weniger bekannte Forschungsergebnisse. sind so ein paar äh Heuristiken, die nicht den bestmöglichen Baum finden, aber einen guten sehr sehr schnell. Und gut ist sogar, ich kann nicht besser als H werden für was von diesen Runlängen, von diesen Längen der Runs abhängt und ich werde mit dem H+ 2 erreichen. Das heißt, ich bin sehr nah an der bestmöglichen äh Lösung dran. Es gibt vielleicht eine, die ein Ticken besser ist, aber eigentlich interessiert mich das gar nicht.

15:37 Und die Methode dafür ist auch relativ einfach. Ähm, die kann man als eine einfache rekursive Methode beschreiben. Ist ähm als der ersten Paper von Kurt Mehorn gewesen, bekannter deutscher Algorithmiker, ähm der das sehr einflussreiche Sachen gemacht hat, auch nach diesem, aber insbesondere auch äh dieses Ergebnis ähm geht auf ihn zurück. Und im Grunde ist die die Idee, wir versuchen den Baum, den wir bauen, so nah wie möglich an einem balossierten Baum zu halten mit ein paar Abstrichen, wo es nicht geht. Und seine Methode war rekursiv der einzige Teil, der noch sozusagen übrig war, den ich dann noch äh bauen musste, war wie bauen wir diesen Baum ohne Rekursion und dazu diese Anschauung. Hier sind ein paar Runs und hier ist ein perfekter perfekt balancierter binärer Baum. Eigentlich würden wir gerne entlang von dem Merchsort machen. Das wäre dann Topdown Merch Sort. Äh das exakt machen ist ungut, weil z.B. hier dieser Schnitt in der Mitte, der würde diesen schönen langen Run hier zerteilen und dann würden wir nicht ausnutzen, dass der schon sortiert ist. Wir wollen also nur schneiden, wo es wirklich auch eine Grenze zwischen den Runs gibt, hier diese Lücken.

16:53 Aber der binäre Baum sagt halt, ich will aber hier schneiden. Das heiß, wir müssen irgendwie zu diesem Baum hinrunden. Das ist, was ich vorhin sagte. Und der Mechanismus dafür ist der folgende: Wir verbinden die Mittelpunkte der Runs mit so einer blauen Linie und lassen die nach unten sinken, bis sie auf einem der grünen Balken aufsetzt. Und damit setzt diese Linie auf dem höchsten auf. Damit ist diese Lücke, die zu dieser Linie, zu diesem blauen Strich entspricht, ist der letzte Schnitt, der letzte Merch. Das ist sozusagen mein mein Schnitt, der diesen in der Mitte ersetzt und entsprechend die anderen in tieferen Rekursionsschritten.

17:35 Die Höhe von den grünen Balken oder genauer die Zahlen, die da dran stehen, das ist die das Level der Rekursion, auf dem ich diesen Merch machen möchte. Diese Zahl, die kann man berechnen mit einer Zweierpotenz. Deswegen sind es die Powers, die Runboundary Powers und deswegen heißt das ganze Power Sort.

17:57 Der Baum, der dann tatsächlich fürs Merchant verwendet wird, der sieht dann so aus und orientiert sich eben in einem gewissen Sinne bestmöglich an diesem grünen Baum. Das besonders hilfreiche an dieser Art das zu definieren, man kann da andere Sachen machen, aber der Punkt hier ist, ich muss für diese blaue Zahl, für die Power von zwei Runs nur wissen, wo diese beiden Runs liegen. Der Rest ist vollkommen unabhängig vom Rest der Eingabe. Das heißt, insbesondere, sie nennen sich an Timsort, wir laufen einmal von links nach rechts durch die Eingabe und finden die Runs so sukzessive. Ich kann also entscheiden, was die nächste Run Power ist, ohne dass ich den Rest der Eingabe gesehen habe. Das ist der große Vorteil. Okay, damit haben wir jetzt auch Power Sort zusammengebaut. Hier noch einmal als Animation, wieder der Algorithmus abläuft. Sie erinneren sich bei Timsort hatten wir diese vier Regeln, wie der Stack aufgebaut sein soll. Bei Powerord ist es eine Regel.

18:52 Die Power Level im Stack sind strickt aufsteigend. Das ist alles. Wir fangen am mit so einem Dummy äh Eintrag für den ersten Run an. Dann finden wir den nächsten Run und bestimmen diese Power mit Linie darunter sinken lassen, bis er auf dem grünen Balken aufschlägt. Äh, dann packen wir den auf den Stack. 3 ist größer als null, also alles gut in Variante erfüllt, kein Merch. Wir finden das nächste Ding, die zwei oben drauf. Das ist aber jetzt nicht mehr aufsteigend. Die drei ist fehl am Platz. Also machen wir einen Merch, der die drei verschwinden lässt. Ja, die drei entspricht ja genau diesem diese Grenze hier. Das heißt, die muss weg. Merch weg ist er. Jetzt ist die Invariante wieder hergestellt. Der Stack ist schön aufsteigend von unten nach oben. Also können wir weitermachen. Das ist alles ma das noch mal. Auch hier passiert wieder das gleiche, ne? Die ein ähm muss die zwei verschwinden lassen, damit es wieder aufsteigend ist.

19:53 Und so machen wir weiter, bis wir das Ende vom äh Array erreichen. Und dann am Ende macht man einfach noch einmal von oben nach unten paar Weise die merches und dann haben wir es sortiert. Und das ist jetzt, das müssen Sie jetzt an der Stelle glauben, weil wir nicht Zeit haben, da genauer reinzugehen. Das simuliert genau das, was man auch machen würde mit diesem rekursiven Algorithmus von Kurt Mehorn, der äh diesen H+ 2 Garantie für die Kosten hat.

20:25 Falls Sie sich fragen, wie man diese blauen Zahlen konkret berechnet, dann ist es hier auf der Folie. Äh, das Balken runtersinken ist natürlich nur so eine Anschauung. Was dahinter steckt, ist aber letztlich eine eine kleine ähm Übungsaufgabe mit Binärdstellung von diesen Zahlen. Letztlich kann man das mit ein bisschen Tricks und Bitschubsen ganz effizient berechnen. Äh möchte ich nicht genauer drauf eingehen. Ich möchte nur einen Punkt noch hervorheben. Ein großes Problem von dieser alten Policy war ja, dass wir den Stack versucht haben in der Höhe zu begrenzen und das ging so kolossal schief und auch der endgültige Beweis, dass das dann doch geht, sind Seiten um Seiten von komplizierter Argumentation für diese neue Policy die Invariante ist die Powerwerte sind strikt steigend.

21:10 Das heißt, ich kann nie mehr Runs auf dem Stack haben, als es verschiedene Werte für diese Power Zahlen gibt. Und man kann sich leicht überlegen, dass Powern Powerzahlen immer zwischen 0 und log n aufgerundet sind, einfach weil das der Worst Case ist zwei Runs der Länge 1 an der dummen Stelle gelegen und können Sie sich ähm aus der Formel oder aus dem Algorithmus folgt es auch direkt. Das heißt, ich habe nur log aufgerundet + 1 viele verschiedene Werte für Powers. Damit kann es auch für den Stack nie mehr Einträge geben als das äh Beweisende mit drei Knubbeln statt einem Forschungspaper.

21:53 Das ist im Wesentlichen, was ich ih zeigen wollte. Ich habe noch ein paar äh Messdaten sozusagen als Beweis, dass es nicht nur clean ist, sondern äh auch gut funktioniert. Ähm nachdem was ich ihn gezeigt habe, mit diesen 50% Mehraufwand für Timsort, ist glaube ich klar, dass es Beispiele gibt, wo das für Timsort schlecht ausgehen muss. Aber auch wenn man sich so typische Beispiele anschaut, ähm also Eingaben, die irgendwie nach einem gewissen zufälligen Modell generiert sind, dann ist bei vielen von den Eingaben, sowohl bei den Merch Kosten, also diesen Kosten für den Baum, als auch bei den Anzahlvergleichen, äh Powersort hat eine deutliche Verbesserung, teilweise hier bis zu 10 20% besser. Eine andere Art, die Eingaben zufällig zu bauen, äh hat ein ähnliches Beispiel. äh Laufzeiten hängt dann davon ab, wo genau und was sie messen. Das sind die Effekte äh weniger dramatisch, aber manchmal substanziell.

22:51 Das ist die Geschichte von Power Sort. Ähm, Timsort ist nach wie vor in der Praxis die Methode, die am meisten verwendet wird, um stabil zu sortieren. Und ich möchte auch weiterhin diesen Algorithmus Timsort nennen, weil da doch deutlich mehr dazu gehört als nur diese Merch Policy. Es gab diesen einen Part, diesen Teil von Timsort, der wirklich nicht besonders viel Lieber erfahren hat auch vom vom Schöpfer selber und ähm den Teil ersetzt Power Sort und damit ist, denke ich, diese Geschichte auch äh zufriedenstellend behandelt und ich wir verstehen, warum es besser ist äh und so weiter und so fort. Äh, wie gesagt, Timsort wird in all möglichen Software Bibibliotheken verwendet und teilweise ähm fehlt da einfach nur jemand, der genügend Detail Liebe und bisschen Zeit mitbringt, um den Switch zu Power Sort zu machen. Die Änderungen im Code sind oft sehr einfach und es ist halt in den Entwicklerkreisen oft so, wenn man dann sagt, hier gibt's eine bessere Lösung und die ist meistens ein halbes Prozent schneller und manchmal 20, dann haben die andere Prioritäten. Das sind andere Sachen einfach dringender. den Bug in irgendeinem Produktionscode fixen ist äh wichtiger. Es ist nicht so, dass da Gründe dagegen sprechen, den Wechsel zu machen. Ähm, aber jemand muss die muss die Arbeit übernehmen. Machen wir Stück für Stück. Haben auch teilweise Komiton von ihnen schon erfolgreich getan. Z.B.

24:12 in Nampai ist von einem unserer Masterstudies die Implementierung, die dann auch in Pandas letztlich verwendet wird. Ähm, Swift ist noch am laufen. Wenn Sie eine eine beliebte Sprache haben, wo Sie gern äh tüfteln, dann können Sie sich mal überlegen, ob Sie das auch machen möchten.