Thomas Kahle
Ich denke etwas über das Sortieren nach, zunächst von Puzzleteilen und dann unter Einbeziehung von Langsamkeit.
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Automatisch generiertes Transkript (nicht geprüft)
Ja, hallo zusammen. Hier ist der Eigenraum zum vierten Mal. Freue mich, dass ihr da seid.
Ich bin Thomas, ich bin Mathematiker und ich frage mich schon so ein bisschen, wie ihr
das hier hört. Es gibt diesen Podcast jetzt auf Spotify und sogar auf YouTube. Ich bin
da ganz plump und will meine Reichweite vergrößern und da habe ich neulich festgestellt, dass
YouTube die zweitgrößte Suchmaschine der Welt ist. Ihr könnt euch denken, was die größte
Suchmaschine der Welt ist. Und es gibt tatsächlich Leute, die Podcasts auf YouTube finden. Das
ist natürlich nicht die beste Art und Weise, Podcasts zu hören. Wer mich kennt oder viel
Podcasts hört, der weiß vielleicht, dass die beste Art und Weise eine Podcast-App ist.
Und das würde ich euch auch empfehlen, eine Podcast-App zu verwenden. Bei vielen Handys
zum Beispiel ist schon eine dabei. Und es gibt auch in den diversen App-Stores noch
bessere. Ich selbst benutze Overcast, was eine App für iOS ist. Und wenn ihr die benutzt,
dann merkt ihr sich, was ihr schon gehört habt und schlägt euch auch immer neue Folgen
vor, wenn sie dann erscheinen. Und es ist alles ziemlich komfortabel. Also, wenn ihr
diesen Podcast auf YouTube entdeckt habt, dann freue ich mich sehr, dass ihr jetzt auch
dabei seid und würde mich noch mehr freuen, wenn ich euch dann im RSS-Feed auf einer Podcast-App
begrüßen könnte. Da sucht ihr dann einfach nach Eigenraum und zum Beispiel könnt ihr
dann die Show Notes direkt sehen in den meisten Apps oder sogar Kapitelmarken nutzen.
So, das aber nur zur Vorrede. Nachdem es letzte Woche ja etwas länger und fast schon
ein bisschen politisch war, möchte ich euch diese Woche eine Geschichte über Ordnung
erzählen. Und die wird hoffentlich auch nicht so lang. Ich habe übrigens neulich gelernt,
dass es sowas wie pränumerische Mathematik gibt. Pränumerische Mathematik ist sozusagen
der Matheunterricht in der Kita. Ich denke eigentlich, dass Zahlen eine ziemlich primäre
Erfahrung sind. Hatten wir ja schon in der früheren Folge dieses Zählen, wenn man nicht
so viele Zahlen kennt. Ich habe ein Gummibärchen, ich habe zwei Gummibärchen, ich habe viele
Gummibärchen. Ihr erinnert euch vielleicht. Aber naja, am Anfang fängt man in der Mathematik
irgendwie auch an mit Sortieren. Ich glaube, pränumerische Mathematik, da geht es um so
Farben und Formen. Und das scheint der Matheunterricht in der Kita, ich kenne mich da nicht so aus.
Ich habe mal in der Kita Matheunterricht gegeben, aber da ging es auch wirklich um Gummibärchen
und Teilbarkeit. Aber es geht auch pränumerische Mathematik. Naja, also da muss man irgendwie
so Sachen sortieren. Sortieren erinnert mich an Puzzle, ich mache gern Puzzle. Puzzle kennt
ihr ja, das ist so ein kaputtes Bild. Man kauft von Ravensburger ein kaputtes Bild und
obwohl man es gerade gekauft hat, ist es schon kaputt. Und da muss man es reparieren, obwohl
man es selbst nicht kaputt gemacht hat. Und da gibt es ja so verschiedene Strategien.
Die meisten Leute, die sortieren erstmal den Rand raus. Das mache ich auch. Es gibt auch
total Sinn, denn wenn man irgendwie die Randteile erstmal hat, erstmal sind die Randteile leicht
zu finden. Und wenn man die hat, dann kann man erstmal so eine Art eindimensionales Puzzle
lösen. Das macht einfach die Randteile in die richtige Reihenfolge. Und wenn man dann
noch ein Bild hat, ist es meistens leicht, die irgendwie zuzuordnen, in welcher Reihenfolge
die kommen. Puzzle mit Bildern sind beliebt. Es gibt aber auch Puzzle ohne Bilder. Neulich
hatte ich so einen Puzzle, das hieß Krypt. Ich sage es mal nicht von welcher Firma, aber
ihr findet das schon. Das hatte den Slogan für Dauerpuzzler, Durchhalter und Dranbleiber
und alle, die nie aufgeben. Und der Witz an dem Puzzle war, dass es komplett einfarbig
war. Dafür hatten aber die Teile in ganz interessante Formen. Da gab es so verschiedene
Bereiche in dem Puzzle. Also dass in einem Bereich die Teile immer eine bestimmte Eigenschaft
hatten oder in bestimmte Richtungen ausgerichtet waren. Aber die waren eben alle schwarz in
meinem Fall. Aber was für eine Mathematik steckt eigentlich jetzt so im Puzzlen? Sagen
wir mal, man hat jetzt so einen Puzzle vor sich und vielleicht hat man jetzt auch schon
den Rand gepuzzelt und will jetzt irgendwie effizient vorwärts kommen. Also eigentlich
will man sich ja die Zeit vertreiben mit so einem Puzzle, aber man will ja doch effizient
vorwärts kommen. Das ist wie so ein kleiner Widerspruch. Aber also sagen wir mal, man
hat jetzt so einen 1000-Teile-Puzzle vor sich. Übrigens wusste der, dass die meisten Puzzle
nicht die richtige Anzahl Teile auf der Schachtel stehen haben. Denn wenn man jetzt mal 1000
nimmt, dann hat es ja gar nicht so viele Teile. Versuchen wir mal die Teile von 1000 kurz
zu bestimmen. Ja, ich habe jetzt mal kurz 4 für euch gemacht. Also 1000 ist ganz einfach,
das ist nämlich einfach 2 hoch 3 mal 5 hoch 3. Das ist die Primfaktor zur Legung. Also
8 mal 5 mal 5 mal 5. 5 mal 5 ist 25 und 5 mal 25 ist 125 und 125 mal 8 ist 1000. Also
es stecken nur 2 in und 5 drin. Das heißt also, wenn man den Rand jetzt könnte man es zum
Beispiel in 50 mal 20 oder so. Also ausgehend davon, dass alle Teile zumindest auf so einem
rechteckigen Muster basiert. Also das ist ein Produkt von zwei Zahlen, ist die Anzahl Teile.
Und dann klappt das meistens nicht. Dann sind es irgendwie 1008 Teile oder irgendwie eine andere
Zahl. Obwohl 1000 ja auch 40 mal 25 ist, was ein schönes rechtwinkliges Format ergeben könnte.
Also es ist vielleicht bei tausender Puzzlen okay, aber hunderte Puzzle stellen einen da schon von
eine schwierigere Herausforderung. Denn ein 2 mal 50 Puzzle ist vielleicht nicht so interessant.
Oder irgendwie jedenfalls anders. Aber das nur am Rande. Also zurück zu unserem Puzzle sagen wir,
wir haben die 1000 Teile vor uns oder 1008. Und die meisten Leute fangen jetzt irgendwie an zu
sortieren. Ich mache das auch so. Und die Frage, die ich mir gestellt habe ist, warum funktioniert
das? Warum ist sortieren bei einem Puzzle so eine effiziente Methode um vorwärts zu kommen? Und das
hat damit zu tun, dass es einfacher ist, zwei 500 Teile Puzzle zu lösen als 1000er Teil. Das kann
man sich auch leicht überlegen mit so einem Modell. Also mal so eine Überschlagsrechnung oder so ein
kleines Denkmodell. Sagen wir mal, man geht irgendwie so vor, dass man sich an irgendeiner Stelle von dem
Puzzle befindet und jetzt das passende Teil dazu sucht. Also ich habe mir genau überlegt, ich will
jetzt hier sagen wir den Rand habe ich fertig und jetzt bin ich links oben in der Ecke und suche genau
das Teil, was dahin kommt. Da könnte ich natürlich erst mal so ganz doof vorgehen. Ich probiere
einfach drein nach alle Teile, die ich noch über habe durch. Und meine Approximation ist, dass man
das jetzt so macht. Also ohne sortieren gucke ich vielleicht auch die Bilder gar nicht an. Ich
probiere einfach die Teile der Reihe nach durch. Jedes Teil durchzuprobieren dauert irgendwie eine
bestimmte Zeit. Die nehme ich jetzt auch mal an für alle Teile gleich. Und das ist jetzt Zufall,
kann ich Glück haben oder Pech haben. Aber über die Anzahl Teile ermittelt sich das alles raus. Ich
brauche irgendwie eine konstante Zeit mal die Anzahl der Teile, die noch da liegen. Sagen wir so
im Mittel bin ich immer nach der Hälfte, finde ich das richtige Teil. Für jedes Teil brauche ich drei
Sekunden. Also brauche ich irgendwie drei Sekunden mal Hälfte der Anzahl der Teile und drei Sekunden
mal Hälfte ist irgendwie dieser Proportionalitätsfaktor. Und mal hat man Glück, mal hat man weniger Glück,
aber das mittelt sich eben draus, wenn man es so oft macht. Und man merkt ja auch, dass man dann am
Ende immer schneller wird, weil die Teile, die man noch über hat, unter denen man sucht, eben
weniger werden. Also kann man das approximieren, indem man diese ganzen Zeiten alle zusammen addiert.
Und sagen wir mal, mein Puzzle hat N Teile, dann habe ich jetzt beim ersten muss ich aus diesen
N Teilen die linke obere Ecke suchen und dann muss ich aus den N-1 verbleibenden Teilen das nächste
suchen. Und jetzt mal habe ich diese Konstante, also kann ich die Konstante ausklammern und summiere
einfach N plus N minus eins plus N minus zwei und so geht es immer weiter bis eins. Also summiere
ich einfach die Zahlen von N bis eins absteigend auf, hat man also die Summe der ersten N Zahlen
mal diesen Faktor, diesen konstanten Faktor. Und das ist eben dieser kleine Gauss, das soll
angeblich der Karl Friedrich Gauss, der berühmte Mathematiker, als Schüler berechnet haben. Und
da kommt raus N mal N plus eins halbe, wenn man die ersten N Zahlen aufsummiert. Also hat er so
gemacht, er nimmt die N, also die, sagen wir mal, er will die Zahlen von eins bis hundert addieren,
nimmt er die hundert mit der eins zusammen, kriegt er hundert eins, nimmt er die 99 mit der zwei
zusammen, kriegt er auch wieder hundert eins, kriegt er die 98 mit der drei zusammen, auch wieder hundert
eins. Also kriegt er N halbe mal N plus eins, wenn das genau das N gerade war oder eben im anderen
Fall, fügt man einfach noch eine Null hinzu und kriegt dann N plus eins halbe Paare mal,
jedes Paar ergibt N, ergibt auch wieder die gleiche Zahl. So rechnen wir das eben aus. Und wie diese
Form jetzt genau aussieht, interessiert mich gar nicht so genau, sondern nur, dass N mal N plus
eins halbe quadratisch in N ist. Also das war meine Zeit für das Auffinden eines Puzzleteils. Und
jetzt möchte ich eben sehen, wie das von dem N abhängt und das hängt quadratisch von diesem
N ab. Und wenn ich jetzt zwei 500er Puzzle lösen will, dann habe ich sowas wie zweimal 500 quadrat
und wenn ich ein 1000er Puzzle lösen will, kriege ich 1000 ins Quadrat und 1000 ist zweimal 500,
also kriege ich zweimal 500 in Klammern ins Quadrat, was viermal 500 Quadrat ist, also doppelt so lange
wie meine zwei 500er Puzzle. Natürlich habe ich noch einen gewissen Overhead, also eine gewisse
Zusatzzeit, die ich für das Sortieren brauche. Also wenn ich mein 1000er Puzzle in zwei 500er
Puzzle aufteilen könnte, angenommen ich wüsste schon, welches die linke und die rechte Hälfte
ist, dann hätte ich ja zwei 500er Puzzle, dann würde ich zwar schneller vorankommen, aber irgendwie
muss ich das noch schaffen, das in die linke und die rechte Hälfte zu unterteilen. Meine Tante,
die macht immer sowas komisches, wenn die Puzzle fertig hat und es wieder einpackt in die Schachtel,
dann macht sie zwei Tüten, eine für die linke Hälfte, eine für die rechte Hälfte. Ich finde
das irgendwie ein bisschen übergriffig, aber na gut, ist auf jeden Fall leichter zu lösen, wie wir uns
gerade überlegt haben. Man kann den Vorteil noch verbessern, indem man statt einen 1000er in zwei
500er zu unterteilen, einen 1000er in 10 100er Puzzle unterteilt oder noch besser in 1000 Einer Puzzle.
Hä? Moment mal, 1000 Einer Puzzle? Was soll das denn bedeuten? Ja, also da kommt dann der Overhead zum
Sortieren richtig zu tragen. Also 1000 Einer Puzzle bedeutet irgendwie sowas wie, man weiß
eigentlich immer sofort, welches Teil man nehmen soll als nächstes und muss es nur noch hinsetzen.
Dann muss aber das Puzzle schon vorher sehr gut sortiert sein. Aber diese 10 100er Puzzle, das
bedeutet irgendwie, es gibt eine natürliche Unterteilung der Puzzleteile, die man hat,
in so Gruppen, sagen wir von Größe 100, 10 Gruppen von Größe 100 und man kann sich ganz sicher sein,
welches in welcher Gruppe ist. Ich kann mir bei einem Puzzle erst mal a priori nicht sicher sein,
welches in der linken Hälfte ist und welches in der rechten Hälfte ist. Das sehe ich einem Teil
meistens nicht so leicht an. Aber wenn man ein Bild hat, was sich farblich unterscheidet,
starker Kontrast da hat oder so, also Farbunterschiede, dann kann man eben sortieren
nach die roten Teile und die grünen Teile und bekommt dann eine natürliche Unterteilung in so
Unterpuzzle. Naja und dann hat man eben diese Verbesserung, indem man irgendwie nach Farbe
sortiert oder irgendwelchen anderen Informationen. Ich benutze zum Beispiel auch gerne diese
Formkriterien. Wichtig ist jedenfalls, dass es sortieren irgendwie leicht ist und zügig geht,
irgendwie fast schon algorithmisch. Habe ich darüber nachgedacht, dass es irgendwas mit
Sortieralgorithmen zu tun hat? Ich will es auch gar keine große Sortieralgorithmen-Vorlesung
halten. Das könnt ihr dann im Informatikstudium machen oder auch im Selbststudium lernen. Das
sind so Sachen, die sehr schön auf Wikipedia oder verschiedenen Blogs beschrieben sind. Ich möchte
euch mal einen Algorithmus vorstellen, der meiner Meinung nach viel zu wenig Bedeutung hat oder viel
zu wenig Beachtung bekommt. Und der Algorithmus heißt Slow Sort, also langsames Sortieren. In
gewisser Hinsicht ist das ja auch das, worum es beim Puzzlen geht. Ich sage euch erstmal,
wie der Algorithmus geht. Slow Sort funktioniert so. Man hat eine Liste von Dingen, die man sortieren
möchte. Das ist jetzt ein bisschen anders als ein Puzzle sortieren. Man hat nämlich eine Liste von
Dingen und man kann für je zwei Dinge sagen, ob eins größer ist als das andere oder ob sie gleich
groß sind. Und man möchte die Liste jetzt der Größe nach sortieren. Bei einem Puzzle ist es
irgendwie so, dass man nach Kategorien sortiert. Natürlich kann man die Kategorien irgendwie
beliebig anordnen und dann wäre es auch so eine vergleichbare Algorithmus. Also diese Liste zu
sortieren, die wie man sagt, partiell geordnet ist, also mit so einer ist größer gleich,
ist kleiner gleich oder gleich. Groß Eigenschaft ist eine Verallgemeinerung von dem, was wir beim
Puzzle sortieren machen. Na gut, sagen wir mal, man hat also diese Liste von Dingen, die man
sortieren möchte. Und Slow Sort ist jetzt ein rekursiver Algorithmus, der ruft sich also selbst
wieder auf. Und er geht vor nach dem Paradigma multiply and surrender, also vervielfältige und
gibt auf. Und das Paradigma bedeutet, dass er nur prinzipiell sinnvolle Schritte macht,
also nicht irgendwie jetzt dumm rumwartet oder irgendwelche Endlosschleifen macht. Also der
macht schon sinnvolle Schritte der Algorithmus. Der will aber seine Termination, hört sich auch
schon so schlimm an, also das Laufzeitende so lang wie möglich herauszögern. Denn das begreift
er eben als Niederlage. Surrender ist der Surrenderschritt. Deswegen versucht er,
sich vorher immer zu multiplizieren, also sich möglichst oft selbst rekursiv aufzurufen. Okay,
also wie geht der jetzt? Wir wollen sortieren und dazu bestimmen wir erstmal das Maximum der Liste.
Also wir haben unsere Liste und bestimmen nach einem bestimmten Verfahren, das ich gleich noch
erkläre, das Maximum. Dann nehmen wir dieses Maximum und platzieren das am Ende der Liste. Und
dann sortieren wir den Rest der Liste mit dem gleichen Verfahren. Das ist die Rekursion. Gibt
auch noch eine andere Rekursion in dem Schritt, in dem wir das Maximum bestimmen. Um das Maximum der
Liste zu bestimmen, teilen wir die Liste nämlich in zwei Hälften auf und rufen den gleichen
Algorithmus wieder rekursiv für die beiden Hälften auf. Und dann haben wir zwei Listen. Die sind
beide in sich sortiert. Also die haben beide das Maximum ganz rechts oder ganz oben oder eben wir
kennen das Maximum von der Liste, von den zwei Listen. Und dann vergleichen wir die zwei maximal
und das ist das Ergebnis, was wir in dem ersten Schritt haben wollen. Nämlich das Maximum der
Gesamtliste ist das Maximum von den beiden maximal. Okay, und das nehmen wir nach hinten und machen
eben das Ganze. Es hört sich eigentlich gar nicht so schlimm an. Es ist eigentlich so ein
ähnliches Verfahren wie Merge Sort, falls es jemand kennt. Merge Sort verfährt die ganze Zeit
genauso. Merge Sort führt die beiden Listen zusammen, indem es ausnutzt, dass die schon
sortiert sind und die einfach so wie so ein Reißverschluss ineinander führt, sodass die
Gesamtliste sofort sortiert ist nach einem Schritt. Das machen wir bei Slow Sort aber nicht. Slow Sort
verzichtet jetzt einfach auf diesen mühsamen Schritt des Zusammenführens und ist dadurch
konzeptionell viel einfacher. Natürlich haben die Informatikerinnen schon untersucht, wie effizient
Slow Sort ist. Und es braucht ungefähr N hoch log N Schritte. Das bedeutet für die Leute, die
sich jetzt mit Komplexität nicht so auskennen, das ist ziemlich blöd, weil normalerweise will
man irgendwie so eine Art polinomiellen, also man erwartet irgendwie so ein polinomielles
Wachstum und N ist wieder die Länge der Liste, die man sortieren will. Und schlechte Sortieralgorithmen
haben sowas wie N-Quadrat-Operationen und gute sowas wie N-Mal-Logarithmus von N. Und Merge Sort
zum Beispiel ist einer in der Kategorie, der sich im Wesentlichen so wie N-Mal-Log N verhält und noch
viele andere schöne Eigenschaften hat. Slow Sort hat die Eigenschaft aber nicht. Slow Sort ist
langsamer als alle polinomiellen Sortieralgorithmen. Man kann das auch genau analysieren mit so Analyse
von rekursiven Algorithmen. Mach ich jetzt aber hier nicht. Man kann sich das irgendwie so ein
bisschen vorstellen, dass von den zwei Listen, dass eigentlich ziemlich selten was getauscht wird in
diesem Algorithmus, denn von den zwei Listen wird immer nur was getauscht, wenn die beiden maximal in
der falschen Reihenfolge sind. Es sind aber eine ganze Menge Vertauschungen nötig und dieser
Algorithmus, der lässt sich eben Zeit und genießt das Leben ein bisschen. Und das ist vielleicht
ganz wichtig in unserer hektischen Wirklichkeit, nicht immer nur auf die Effizienz zu schielen.
Man sollte vielleicht auch mal einen Puzzle machen oder was mit Slow Sort sortieren. Und das ist mein
Fazit dieses Sortierens und da wünsche ich euch jetzt einen guten Tag, eine gute Nacht,
eine gute Zeit und lasst es mal langsam angehen. Ciao!