Video 7-11: Java's Sortierverfahren

0:05 Was wir uns im nächsten Kapitel, im letzten Abschnitt von diesem dieser Einheit noch anschauen wollen, ist, wie das in der Praxis funktioniert und wie es äh dort gemacht wird. Ich hatte Ihnen ja jetzt gerade vorgebeten, wir haben eine ganze Reihe von Algorithmen kennengelernt, die alles sortieren, die alle etwas unterschiedliche Eigenschaften haben. Welche welche nimmt man denn in der Praxis? Ähm, das darum geht's in diesem Abschnitt und äh insbesondere kommen Sie selten in die Verlegenheit ein Sortieralgorithmus selbst bauen zu müssen. Alle Software Frameworks, die ich so kenne, haben irgendeine Sortierfunktion mit eingebaut. Manchmal ist sie vielleicht nicht bestmöglich, aber meistens ist sie zumindest ganz okay. Das heißt, in der Praxis heißt Sortierealgorithmus implementieren, einfach das passende schon äh existierende aufrufen. Ich denke trotzdem ist es wertvoll, dass sie diese Algorithmen da dahinter kennen aus zwei Gründen. Einerseits wollen sie wissen, was passiert und wie teuer das ist. Wenn Sie also wissen, welcher Algorithmus dahinter steckt, können Sie äh ohne ohne blind raten zu müssen oder alles mit Laufzeit Experimenten unterfüttern zu müssen, abschätzen, ob das für ihre äh für ihre Anwendung gut genug ist oder eben nicht.

1:21 Ähm, das andere ist, dass es auch eine eine Spielwiese ist, um Entwurfsmuster einzuüben, die für andere neue Probleme, für die es noch keine Algorithmen in den Bibliotheken gibt, einzuüben auf einem Problem, was auch schnell verständlich ist und wo wo man die Lösungen äh leicht ausprobieren kann. Äh insbesondere gibt's also dieses Entwurfsmuster, dem dem auch Merchsort und Quicksort folgen, diese Divide and Conquer Idee, dass man versucht die Eingabe in mehrere Teile auch zu teilen und die unabhängig voneinander zu lösen. Das ist so das äh dominierende äh [räuspern] Entwurfsmuster für Sortier Algorithmen, was aber viel viel breiter anwendbar ist. Und letztendlich muss natürlich irgendjemand auch diese Implementierungen schreiben. Jetzt können Sie sagen, die die was ich C oder Java äh Bibliothek, wenn ich hier so umgucke, ist für die meisten dieser Programmiersprachen wahrscheinlich wahr, dass die Implementierungen älter sind als äh die Hörerschaft. Ähm bei manchen ist es nicht so, wenn ich gleich noch drauf zu sprechen komme, gerade Java, ähm sind sie alle ähm älter als die Implementierung.

2:32 Der Punkt ist aber auch ähm ob das jetzt eine gute Sache ist oder nicht. Es werden ständig neue Software Frameworks gebaut. ähm gerade was irgendwelche Front-End Frameworks angeht und oft bauen die dann noch mal eine Sortiermethode, die ein bisschen speziell ausnutzt, welche Umgebung es da gibt. Das heißt, es ist gar nicht so selten, dass jemand mal eine neue Sortiermethode schreiben muss und oft wird da relativ plump abgekupfert von Implementierung, die es schon gibt, ob das nun für die Umgebung passt oder nicht.

3:09 Bevor wir dazu kommen, ähm Grundwissen in Java, ähm hatte ich eben schon gefragt. Äh ich habe bisher nur vier Antworten eingeloggt, also ähm dürfen Sie noch mal noch mal kurz Ihren Beitrag leisten. Äh und wenn Sie wenn Sie können, dann geben Sie den vollqualifizierten Namen der Klasse an. Den müssen Sie theoretisch ja immer als Import Statement schreiben. Das war jetzt der Hinweis, dass es nicht Java Lang ist. Es gibt das eine Paket Java.lang, dass sie nicht importieren müssen. Kennen Sie, ne? Das sind Dinge wie String und so weiter drin. Ähm, da hat man sich hat man sich gesagt, da jedes Mal port Statement zu schreiben ist bisschen zu viel des Guten.

4:18 Also, wenn Sie wenn Sie das noch nie benutzt haben oder es einfach nicht auswendig wissen, dann schreiben Sie das. Weiß ich nicht. auch okay.

4:29 Es geht mir ja mehr darum zu sehen, ob ich Ihnen das noch mal in Erinnerung rufen sollte oder eher nicht, weil sie es eh wissen.

4:47 Gut, tippen Sie fertig. Wir können ja mal ähm die Antworten uns anschauen. Der Punkt ist, die werden eh ein bisschen unübersichtlich. Sofern sie nicht exakt den identischen String tippen, wird das wahrscheinlich einfach mehrmals hingeschrieben. Es gibt einige Antworten, die im Wesentlichen heißen äh noch nicht benutzt. Ähm gibt's das Comfor Sord bin ich mir gar nicht. Kann sein, dass das auch geht. Es gibt wahrscheinlich nicht nur ein Einstiegspunkt dazu. Es gibt mindestens, wenn Sie das Collections Framework kennen, da gibt's noch mal ein Collections Source.

5:21 Ähm, also das hier ist so die ähm mustergültige Variante. Java Util Arrays ist eine Klasse mit allen möglichen statischen Methoden als Hilfsmethoden, insbesondere den Sortiermethoden. Äh werde ich gleich auch noch mal zeigen. Natürlich können Sie auch die ARX 4J benutzen.

5:45 Da gibt's natürlich dann auch mehrere Verfahren, nicht nur den Quick. Sort, sondern den Merch. Sort und all die anderen. Die Namensgebung ist so ein bisschen na gut. [schnauben] Ähm, gut.

6:05 Also, die Frage war denkbar ungeeignet, um Gefühl dafür zu bekommen, wie viele von Ihnen die Methode schon kennen. Ähm, in aller Kürze, das ist ein Auszug aus dieser Klasse Java Util Arrays.

6:18 Äh, da gibt's eine ganze Reihe von Methoden, die alle Sort heißen, die überladen sind mit verschiedenen Parametertypen. Es gibt erstmal für alle primitiven Typen eine Implementierung. Das kann Java einfach nicht anders. Also selbst wenn die intern dann das gleiche tun, die könnten ja z.B. versuchen, den gleichen Code aufzurufen. Mal auf können tun sie nicht wirklich, können sie nicht wirklich. Äh, aber selbst wenn Sie das versuchen würden, müssten Sie eine eigene äh Signatur anbieten für alle primitiven Typen. Das sind diese hier. Äh schockierenderweise ist Boolian Array gar nicht dabei. Na ja, können sich überlegen, wie man das sortiert. Äh und dann gibt's noch einen Aufruf für Object Arrays, also alle Referenztypen.

7:02 Ähm und da gibt's die Variante mit und ohne Comparator tatsächlich gibt's kein comparable Array, wie das die ALX for J Library macht. Die ALX vor ich das J alles mit Java Albth Edition. Es gibt kein mit comparable Array, sondern es gibt diese generische Variante, wen wir im nächsten Kapitel auch noch mal kurz drauf eingehen. Java Generics und Typ Parameter. Äh das das ist so das Interface nach außen. Es gibt aber tatsächlich noch mehr. Ähm, es gibt auch alle Methoden noch mal als eine Kopie, in der Sie einen Bereich angeben könnt aus einem Array, dass wir nur den Bereich L bis R so sortieren. Und dann gibt's noch für quasi alle eine Methode mit parallel davor, also eine Implementierung, die versucht mehrere Kerne auszunutzen. Ist eine ganze Menge Holz. Ich glaube auch, die Klasse hat irgendwie eine ganze Menge Codezeilen.

8:06 Äh, jetzt weiß ich doch nicht mehr auswendig ähm wie viele am Ende das waren, weil das äh Java Utils Arrays tatsächlich gar nicht die Implementierung enthält, sondern das nur weiter dedigert.

8:27 Äh für die Verwendung müssen Sie das alles ja gar nicht wissen. Sie rufen einfach sort auf mit ihrem Array und eventuell mit dem Bereich und dann tut es. Wir wollen uns natürlich jetzt doch ein bisschen anschauen, was da dahinter steckt, denn wir haben jetzt diese ganzen Algorithmen gelernt. Was machen denn jetzt die Implementierungen in Java? Und das Schöne ist, ähm weiß ich, wie viel Sie über die über das äh Ökosystem der Java Welt wissen und die Historie und all das ist manchmal auch kompliziert. Ähm was ist Java? Java ist die Programmiersprache und die Java Runtime Library ist diese Sammlung von paar tausend Klassen, 4000 irgendwas hatte ich gesagt am Anfang, glaube ich, gell? ähm die sozusagen bei Java mitgeliefert werden, wenn man das normale Java ausführt. Und für beides sozusagen den Compiler und die Virtual Machine und auch diese Runtime Library gibt's eine Referenzimplementierung, also eine eine verfügbare Implementierung, das ist Open JDK, die ähm nicht die einzig mögliche Implementierung sein soll, aber eine eine die sozusagen im Zweifel Details aus der Spezifikation von der Sprache, die es ja auch noch gibt, also ein langes Dokument, wo beschrieben ist, was Java erlaubt und was nicht und was die ganzen Klassen sein sollen. Da ist es in Text beschrieben, halbwegs äh formal, aber wo das noch lücken lässt, soll die Referenzimplementierung sozusagen diese äh diese Uindeutigkeiten ausräumen.

9:55 Gleichzeitig ist Open JDK aber auch die Implementierung, die man fast immer verwendet, weil sie mittlerweile ähm als Open Source gepflegt wird unds keine keine ernstzunehmende proprietäre Alternative gibt. Früher war das lange, da gab's Oracle, die Java entwickelt haben, nachdem sie Sun aufgekauft haben. Äh war mal ein Spinoff von der Stanford Uni, die Java ursprünglich gegründet haben. Dann gab es eine proprietäre Implementierung, die immer so ein bisschen besser war als Open JDK, die Open Source Variante. Mittlerweile arbeiten die alle zusammen in der Code gleichen Codebase und alles, was sozusagen mal Secret Source bei Oracle war, ist jetzt in der Open Source Implementierung.

10:42 Das Schöne an Open Source ist, man kann reingucken. Also lassen Sie uns das machen. Ähm ein bisschen größer machen. Also, sie finden, es gibt ein einen GitHub Account JDK. Ähm, nee, das ist wahrscheinlich Quatsch, das ist das Repo, ne? Äh, zu kurz hier. Open JDK ist der Gitubername und JDK ist das Open JDK Repository. Das ist ein bisschen umfänglich, weil da doch einiges drin ist. Wenn Sie das suchen, dann suchen Sie immer nach Source und dann Java Base. Da sind so die Hauptklassen drin und Share Class und dann hier Java util. Das sind also diese ganzen, wenn wenn wir ähm z.B. Spel mal nach Java Lang gehen, dann sehen Sie die ganzen Klassen, die Sie bestimmt besser kennen. Na ja, die ganzen Box Types. Ich suche jetzt nach String, da muss ich ein bisschen scrollen. Ähm, da ist String. Da sind die also alle drin. Und natürlich gibt's dann auch hier Java Util Arrays, sehen Sie hier oben.

11:51 Und die Klasse hat so ein paar Zeilen. Lad, lad lad. Ähm, okay. Fast 10.000 Zeilen, nur diese davon ist wahrscheinlich dreiviertel Java Doc, aber gut. Ähm, Gitab kann ja mittlerweile ganz gut hier auch so eine Summary anzeigen. Äh, leider ohne Typen. Das heißt, alle Sortfunktionen heißen gleich. Äh, die sehen aber auch fast alle gleich aus. Fast alle sehen so aus. Sort, dann was auch immer, ein kurzer Check der Parameter und dann wird ein Aufruf weitergeleitet an andere Klasse und das ist alles, was Sie davon sehen in dieser Klasse. Also alles interessante passiert in dieser anderen Klasse, die natürlich vom Namen her schon so ein bisschen was suggeriert.

12:47 Und die hatte ich auch vorbereitet. Da ist sie. Genau. Äh, ich bin hier mal zu einer Implementierung gesprungen äh für Long Arrays. In sieht genauso aus.

12:59 Da sehen Sie, da passiert wieder so ein bisschen was und dann wird's wieder weitergeleitet. Also, die ganze Implementierung ist ein bisschen verschachtelt, hat viele ähm Ecken und Kanten und Details und ähm man kann sich da natürlich durchhangeln.

13:16 Okay, Sold Operation war nicht das Richtige. Man kann sich theoretisch durchhangeln. Ich hätte jetzt gerne mal den eigentlichen Patitionierungscode gezeigt. Äh können wir vielleicht gleich noch machen. Bisher habe ich Ihnen ja eigentlich gar nichts dazu gesagt, welche Algorithmen davorkommen. Insbesondere welcher Sortieralgorithmus wird da verwendet. Der Name mit Dual Pivot Quicksort so heißt die Klasse. Aber ich sage Ihnen schon mal, das ist ein bisschen, das ist einerseits richtig, andererseits irreführend. Die eigentliche Antwort ist, es werden ganz viele Algorithmen verwendet und da wird je nach je nach Typ und auch je nach Eingabe unterschieden, welcher dafür am besten geeignet ist. Ähm durchaus einer der ähm am häufigsten da verwendete von denen, die implementiert sind, ist äh diese Dual Pivot Quicksot, der also zwei Pivots verwendet statt einem. Ansonsten tut der ähnliches wie die Quicksot Varianten, die ich eben gezeigt hatte. Aber wir machen in jedem Partitionierungsschritt mit zwei Pivots drei Teile. Alles kleiner, alles dazwischen, alles größer.

14:20 Ähm, das machen wir aber nur für primitive Datentypen, also immer nur für für Zahlen und na ja, Character sind letzlich auch Zahlen eigentlich nur für Integer, wenn man so möchte.

14:33 Ähm, die Geschichte dahinter ist auch ganz interessant. äh werde ich gleich noch ein bisschen was zu sagen. Äh 2009 würde ich vermuten ist ist jünger als die meisten. Ähm da ist das in da hat das Eingang in diese Entwicklungsversion von Java gefunden und mit Java 7 wurd es dann deployed. Der andere große Algorithmus ist für Referenzobjekte. Wann ich Objekte vergleiche, da möchte ich in aller Regel einen stabilen Algorithmus, während hier Quicksort nicht stabil sortiert, sehen sich Duplikate und so weiter. Ähm und da kommt eben Timsort zum Einsatz. Das ist Tim Peters, das einzige offizielle Bild, das er online hat. Äh, der Algorithmus stammt eigentlich aus der Python Welt, wurde aber für ganz viele andere Frameworks portiert und so auch nach Java. Witzigerweise im gleichen Jahr, was aber glaube ich reiner Zufall ist, hat nichts mit zu tun. Das sind so die beiden Hauptalgorithmen. Äh, es gibt dann noch eine Reihe von anderen, insbesondere hatte ich eben diese Parallelen Algorithmen ja schon gesagt. Ähm, dafür gibt's noch mal eine andere Variante und es gibt für die kleinen Zahndatentypen einen nicht vergleichsbasierten Algorithmus, der schneller ist, der ausnutzt, dass es nur ganz viele ganz wenige verschiedene äh Zahlen überhaupt gibt von diesem und se z.B. Byte gibt's nur 256 verschiedene Werte. Wenn ich also ein Byte Array sortieren will, dann benutze ich einen ganz plumpen Algorithmus, der zählt, wie oft kommt jede dieser 256 Zahlen vor? Und dann generiere ich ein neues Array mit so und so viel Vorkommen von jeder Zahl. Das ist auch sortieren, geht aber nur, wenn das Universum so klein ist.

16:20 Das passiert also da. Ähm, ich hatte ja schon erwähnt, dass ich mit mit diesen Dingen einige Zeit verbracht habe, gerade mit den Java Algorithmen. Äh, für diesen Dual Pivit Quicksot habe ich von durch Zufall ähm als das dann deployed wurde, nicht 2009, das hat noch mal ein paar Jahre gedauert, äh erfahren und damals wurde das einfach nur angepriesen als ah, da gab's jetzt diesen neuen Algorithmus und der ist viel schneller. Cool. Ähm, mich hat dann sofort irgendwie die Frage gekitzelt, warum ist das denn so? Und so als Followup, warum wurde der eigentlich erst jetzt entdeckt? Wir sortieren ja schon seit Jahrzehnten. Irgendwer sortiert schon seit Jahrzehnten und selbst Java ist nicht so jung. Die hatten auch vorher schon andere Algorithmen, warum denn jetzt plötzlich was Neues? Und natürlich vielleicht kann man es ja auch noch besser machen. Ähm hat mich da einige Zeit beschäftigt. Wenn Sie die Antworten lesen wollen, können Sie meine Doktorarbeit schauen.

17:21 Da ist sie. Der zweite Algorithmus Timsort hat mich auch beschäftigt. Ähm sortieren lässt dann irgendwie nicht ganz los. Der hat eine andere Geschichte. Der war schon 10 Jahre im Einsatz äh in Python, insbesondere, aber wie gesagt auch in vielen anderen Frameworks. Ähm, um eine lange Geschichte kurz zu machen, hat aber wiederholt für Ärger gesorgt in einer bestimmten Weise. Besonders schön ist diese Geschichte, würde ich aus Zeitgründen abkürzen. Da gab es ein Bug, der im Wesentlichen dazu führen konnte, dass man die Sortiermethode aufruft. Hier Javaut arrays. Source und dann fliegt eine Exception. nicht so gut. Ähm war ein subtiler Bug, aber tatsächlich ein algorithmischer Fehler, der in diesem Algorithmus ähm lange Zeit geschlummert hat. Es braucht eine relativ spezielle Eingabe, um den auszulösen. Ähm, das wurde entdeckt und auch einen Fix vorgeschlagen, wie man das Problem behebt. Python hat den richtigen Fix implementiert. Java dachte, ah, wir machen nur so ein Patch und dann haben sie sich damit noch mal aufs Gesicht gelegt. Ähm, da gab es einen noch subtileren Bug, der wieder dazu führen konnte, dass die Sortiermethode eine Exception wirft. Am Ende haben sie ihn dann behoben, aber es stellt sich raus, Timsort hat in dem ganz speziellen Sinne Overhead, den es nicht haben müsste.

18:44 Dafür müsste ich mehr ausholen. Ähm habe ich mich entschlossen aus Zeitgründen nicht zu machen. Es gibt da ein fundamentales Problem und das haben wir dann tatsächlich äh lösen können mit einer anderen Methode. Hier haben wir PowerSort genannt, weil es da um Zweier Potenzen geht und mittlerweile ist ist Power Sort auch das, was in Python verwendet wird und ein paar anderen Bibliotheken, aber bisher nicht in Java. Aber ähm müssen wir noch überzeugen äh endlich die sinnvolle, also diese Historie aufzugeben und den sinnvollen Fix für dieses Problem zu implementieren. Ähm an der Stelle dazu könnte ich sehr viel mehr sagen, aber ich ähm sehe so ein bisschen die Prioritäten für die Vorlesung anders. Deswegen folgendes Angebot. Ich kann dazu gerne mal einen einen extra Vortrag halten und ein bisschen mehr in diese Themen einsteigen. Die erste Frage, warum ist diese Dual Pivit Quicksort schneller? Und die zweite Frage, was ist das Problem mit Timsort oder was ist die Lösung? Beides äh wenn das wenn es da Interesse gibt, also es ist ähm hat natürlich dann mit der Vorlesung nichts zu tun, ist auch kein Prüfungsstoff. Das wäre sozusagen reine ähm reines Entertainment, Belustigung, Bereicherung, wie auch immer. Ähm, können Sie mir einfach mal Rückmeldung geben, wenn es da Interesse gibt, können wir das gerne mal versuchen, irgendwo einen Termin zu finden. Äh, das ist auch ja nicht zeitkritisch, können wir auch irgendwie verschieben in die Vorlesungsfreie Zeit, weil da natürlich auch vielleicht viele weg sind.

20:17 Ähm ja, lass lassen Sie mich mal wissen, was Sie denken. Ähm sozusagen mein mir blutet das Herz nicht mehr dazu in die Vorlesung zu packen, aber umgekehrt soll es ja hier nicht um mich gehen, sondern darum, dass sie die wichtigen Dinge lernen. Und da muss man manchmal auch die Lieblingsthemen ein bisschen kurz halten.

20:42 Ähm ein paar Pointer, falls Sie das interessiert, was jenseits von Java so verwendet wird. Das ist durchaus anders. Teilweise in C++ gibt's ein ähm es ist weniger eindeutig als in Java, was jetzt die Implementierung ist. Da gibt's mehrere. Die Standard Open Source Variante, die man auf Linux überall auch haben würde, verwendet so einen klassischeren Quicksort, nur ein Pivot mit ein paar Tricks, um den Worst Case besser einzuhegen. Und ansonsten den Pingpong Merch Ser den sich vielleicht erinnern, im Wesentlichen genauso wie auf der Folie war. erstaunlich wenig extra ähm Spielchen mit so einem bisschen Sternchen dran. Wenn wenig Speicher da ist, dann haben sie eine clevere Methode für Merchen, die keinen Zusatzpuffer braucht, aber die verwenden Sie dann nur, wenn wirklich der Platz knapp ist. Äh zu Python hatte ich schon gesagt, verwendet Timsord bzw. mit dieser Power Sword Merch Policy ähm ist am Ende vom Tag eine Art von Merch Sort, aber ein bisschen ungewöhnlich.

21:43 Äh, wie gesagt, vielleicht ja da ein ander mal mehr. Ähm, Rust habe ich noch als ein Beispiel rausgepickt von einer etwas moderneren Sprache, wo es auch sehr viel ähm sehr viel Engagement und Enthusiasmus von Open Source Entwicklern gab, da tatsächlich relativ neue äh Ideen reinzubringen. Ähm, ist von den gleichen zwei Entwicklern. Einer davon ist Orson Peters, der diesen Vortrag im im im Winter gehalten hat, den Sie auf YouTube auch sehen können, wenn Sie mögen, wo er ein bisschen über Performance Engineering spricht. Ähm, die haben zwei für Rust zugeschneiderte, zugeschnittene Varianten entwickelt. Ist auch wieder am Ende Merchort und Quicksort, aber noch ein bisschen ähm weniger weniger nah an den Varianten, die man so auf eine Folie packen kann. auch relativ umfangreich im Code.

22:44 Damit kommen wir zum Ende zum vom Sortierkapitel. Da habe ich hier noch mal aus den Folien von Ctrick und Wayne eine Übersicht über die die klassischen Sortierverfahren und ihre Eigenschaften in ein paar Kategorien. In place war hier so definiert, dass wir logarithmisch viel Zusatzplatz erlauben. Das heißt, sowas wie eine Rekursion von Quicksort äh ist damit erlaubt. Ähm obwohl es natürlich ein bisschen zusätzlichen Speicher zum Array braucht. Stabil hat man drüber gesprochen, gleiche Elemente bleiben und dann die äh Komplexität im Best Average und worst Case. Ja, und sie sehen, es gibt sozusagen keinen Eintrag, der komplett quer durch die Bank überzeugt, außer diesen untersten natürlich, aber das ist kein echter, das ist sozusagen der Wunsch, das hätten wir gerne. Äh, man kommt recht nahe an diese Dinge. Sie führen auch online Sachen suchen. Es gibt ähm es gibt eine Implementierung, die heißt Wiki Sort. Die kommt vielleicht noch am nächsten an diese Sachen ran. Ist aber trotzdem Faktor 2 bis Faktor 4 langsamer als so ein Standard Quicksort. ist aber dafür stabil und in place, sogar mit konstantem Zusatzspeicher.

23:57 Ähm insbesondere, wenn man aber kombinieren will mit im Wesentlichen der optimalen Anzahl Vergleiche, das ist ein offenes Problem. Wir wissen nicht mal, ob das möglich ist oder ob das nicht möglich ist und deshalb keiner einen findet. ist alles bisschen offen.

24:15 Für die meisten praktischen Szenarien werden Sie nach der Tabelle eine sinnvolle Vorauswahl treffen können, falls Sie die Verlegenheit mal kommen. Äh, deswegen damit dann auch der Abschluss dieses Kapitels.