Timsort verstehen
Sortieralgorithmen sind eine unangenehme Kombination aus grundlegend notwendigen und zutiefst umstrittenen. Von neuen Ingenieuren, die in einem Interview beeindrucken wollen, bis hin zu älteren Ingenieuren, die nach einer Lösung für eine schnell skalierbare Datenbank suchen, Es gibt unzählige Faktoren, die berücksichtigt werden müssen. Was ist die Geschwindigkeit des Vergleichs zwischen zwei Objekten? Was ist die Swap-Zeit? Wie groß ist die Datenbank? Welche Art von Objekten enthält es? Ist es schon halbsortiert? Müssen die Ergebnisse stabil sein?
Jede dieser Fragen kann Argumente für den einen oder anderen Algorithmus liefern. Sind die Quelldaten groß und komplex? Die meisten Sprachen verwenden standardmäßig die standardmäßige Schnellsortierung mit ihrer O (n log n) -Zeitkomplexität. Ist es kleiner? Insertion Sort wirkt Wunder auf diejenigen. Überwiegend sortiert? Heck, Bubble Sort könnte dafür fast funktionieren. Wenn Sie die Vorzüge jedes einzelnen lesen / visualisieren möchten, lesen Sie diesen Vergleich von toptal.com.
Ein Sortieralgorithmus, den Sie auf dieser oder fast jeder anderen Website nicht finden, ist Tim Sort. Diese obskure Sortierung ist derzeit einzigartig für Python und wird als Standardsortieralgorithmus verwendet. Rufen Sie array.sort in Python auf, und Tim Sort wird ausgeführt. Trotzdem ist es selten, Ingenieure zu finden, die Timberland kennen und verstehen. Also: Was ist das?
Tim Sort wurde erstmals 2002 von Tim Peters für die Verwendung in Python implementiert. Es kam angeblich aus dem Verständnis, dass die meisten Sortieralgorithmen in Schulzimmern geboren werden und nicht für den praktischen Einsatz in realen Daten entwickelt wurden. Tim Sort nutzt gängige Muster in Daten und verwendet eine Kombination aus Zusammenführungssortierung und Einfügesortierung sowie eine interne Logik, um die Manipulation großer Datenmengen zu optimieren.
Warum Tim Sort?
Wenn wir Abbildung 2 betrachten, können wir sofort etwas Interessantes sehen. Im besten Fall übertrifft Tim Sort Merge Sort und Quick Sort. Im schlimmsten Fall läuft es mit vergleichbarer Geschwindigkeit Merge Sort und übertrifft tatsächlich Quick Sort. Mit anderen Worten, es ist unerwartet schnell.
In Bezug auf den Speicherplatz befindet sich Tim Sort am schlechteren Ende des Spektrums, aber die Berücksichtigung des Speicherplatzes für die meisten Sortieralgorithmen ist ziemlich spärlich. O (n) ist in den meisten Fällen nicht zu grob; Es ist erwähnenswert als möglicher Mangel und der einzige Ort, an dem Quick Sort Tim Sort wirklich überstrahlt.
Der letzte Punkt, an dem Sortieralgorithmen oft beurteilt werden, ist die Stabilität. Stabilität ist das Konzept, dass Objekte von gleichem Wert beim Sortieren ihre ursprüngliche Reihenfolge beibehalten. Nun, Sie fragen sich vielleicht, warum wir uns darum kümmern. Die Artikel sind gleichwertig – warum stört es uns, wie sie bestellt werden?
Die einfache Antwort ist, dass Stabilität für gestapelte Sorten wichtig ist. Das heißt, Sie sortieren zuerst nach einem Kriterium und dann nach einem zweiten. Wenn Sie dies in einem instabilen Algorithmus tun, verlieren Sie sofort die Zuverlässigkeit Ihrer ersten Sortierung, wenn Sie die zweite ausführen. Als Referenz ist die Schnellsortierung instabil und die Zusammenführungssortierung stabil.
Tim Sort ist auch stabil, ganz zu schweigen von fast, wenn auch etwas schwer (im Vergleich zu Quick Sort). Während Sortieralgorithmen anhand anderer Überlegungen beurteilt werden können (und sollten), sind dies die großen drei.
Die Implementierung in drei Schritten
Tim Sort ist selbst nach algorithmischen Maßstäben komplex. Die Implementierung wird am besten in Teile zerlegt.
Binäre Suche
Das erste, was Sie benötigen, um eine Tim-Sortierung zu implementieren, ist eine binäre Suchmethode. Dies wird nur verwendet, um Ihre Einfügesortierung später zu implementieren.
Als Referenz: Binäre Suchalgorithmen
Einfügesortierung & Sortierung zusammenführen
Zweitens müssen Sie die Einfügesortierung codieren und die Sortierung zusammenführen. Dies sind vertraute Algorithmen, und sollte in der Gesäßtasche der meisten Ingenieure sein, aber wir werden über die Grundlagen gehen, wie sie funktionieren und warum sie für uns wertvoll sind hier.
Insertion Sort ist ein sehr einfacher Sortieralgorithmus. Es durchläuft das Array und verschiebt es jedes Mal, wenn es auf ein Element stößt, das nicht in Ordnung ist (streng genommen weniger / mehr als das Element davor), an die entsprechende Position im bereits sortierten Array. Einfügesortierung ist berüchtigt dafür, sehr schnell an bereits sortierten Arrays sowie kleineren Arrays zu arbeiten. In der Tat können wir aus Figur 2 sehen, dass Insertion Sort eine beeindruckende Best-Case-Laufzeit von O (n) hat. Denken Sie daran, mit der Einfügesortierung fortzufahren: Der beste Fall für die Einfügesortierung ist ein bereits sortiertes Array. Es mag albern klingen, aber das wird relevant sein.
Merge Sort hingegen funktioniert nach einem Grundprinzip: Es ist außerordentlich einfach, bereits sortierte Arrays zusammenzuführen. Es teilt also ein Startarray immer wieder in zwei Hälften, bis es nur noch einzelne Elemente sind. Dann wird das Hauptarray langsam neu erstellt, indem diese Elemente in sortierter Reihenfolge wieder zusammengeführt werden. Da wir mit Bausteinen der Größe eins begonnen haben, war es sehr einfach, erste sortierte Arrays zu erstellen. Dann ist es einfach, sie zusammenzuführen. Am Ende verbringen wir O (n log n) Zeit, und (wichtig) wir tun dies auf eine Weise, die garantiert stabil ist.
Beispielhafte Implementierungen finden Sie unter:
Sortierung zusammenführen: https://www.geeksforgeeks.org/merge-sort/
Sortierung einfügen: https://www.geeksforgeeks.org/insertion-sort/
Tim Sort implementieren
Der Schlüssel zum Verständnis der Implementierung von Tim Sort liegt im Verständnis der Verwendung von Runs. Tim Sort nutzt natürlich vorkommende vorsortierte Daten zu seinem Vorteil. Mit presorted meinen wir einfach, dass sequentielle Elemente alle zunehmen oder abnehmen (es ist uns egal, welche).
Zuerst setzen wir eine minrun Größe. Damit meinen wir, dass wir sicherstellen wollen, dass alle unsere Läufe mindestens eine bestimmte Länge haben. Bitte beachten Sie, dass wir nicht garantieren, dass wir Läufe dieser Größe finden — wir werden später darauf eingehen. Wir sagen einfach, dass ein Lauf mindestens eine bestimmte Länge haben muss.
Wenn wir auf einen Lauf stoßen, legen wir ihn beiseite. Wenn wir den längsten Lauf innerhalb eines minrun Bereichs finden. Wir haben jetzt eine vertraute Datenstruktur: ein kleines, sortiertes Array. Wenn es mindestens minrun lang ist, dann huzzah! Wir können weitermachen. Wenn nicht, setzen wir Insertion Sort ins Spiel.
Sie erinnern sich vielleicht von oben, dass die Einfügesortierung bei zwei Arten von Arrays besonders wirksam ist: kleine und bereits sortierte. Was wir gerade gemacht haben, ist ein kleines, sortiertes Array. Wenn es nicht mindestens minrun lang ist, greifen wir nach vorne und greifen nach genügend anderen Elementen, um den Lauf abzuschließen. Wenn ein Lauf auf das Ende des Arrays trifft, können Sie ihn natürlich etwas kurz lassen.
Sobald Sie alle Ihre Läufe erstellt haben (dh sortierte Subarrays), verwenden Sie Ihre Zusammenführungssortierung, um sie miteinander zu verbinden. Im besten Fall ist das gesamte Array bereits sortiert und Tim Sort ist intelligent genug, um zu wissen, dass es nichts anderes tun muss. Andere Zeiten, es neigt dazu, nur extrem effizient zu sein. Als zusätzlichen Vorteil sind sowohl die Einfügesortierung als auch die Zusammenführungssortierung stabil, sodass das resultierende Array stabil ist.
Für diejenigen, die Kugeln bevorzugen:
- Legen Sie eine
minrunGröße fest, die eine Potenz von 2 ist (normalerweise 32, niemals mehr als 64 oder Ihre Einfügesortierung verliert an Effizienz) - Finden Sie einen Lauf in der ersten
minrunvon Daten. - Wenn der Lauf nicht mindestens
minrunlang ist, verwenden Sie die Einfügesortierung, um nachfolgende oder vorherige Elemente zu erfassen und sie in den Lauf einzufügen, bis sie die richtige Mindestgröße haben. - Wiederholen, bis das gesamte Array in sortierte Unterabschnitte unterteilt ist.
- Verwenden Sie die zweite Hälfte von Merge Sort , um die geordneten Arrays zu verbinden.
Fazit
Tim Sort ist mächtig. Es ist schnell und stabil, aber vielleicht am wichtigsten ist es nutzt die reale Welt Muster und nutzt sie, um ein Endprodukt zu bauen. Ist es für jede Situation? Wahrscheinlich nicht. Viel Glück beim Programmieren auf einem Whiteboard während eines Interviews, und wenn Sie zur Not nur einen schnellen, einfachen Sortieralgorithmus benötigen, möchten Sie sich wahrscheinlich nicht die Mühe machen, etwas so Komplexes zu implementieren. Für Datenwissenschaftler, die Zahlen knirschen, ist es jedoch mehr als einen Blick wert.
Für Neugierige können Sie den gesamten Tim-Sortiercode auf github überprüfen.
Vielen Dank
Vielen Dank an alle meine Leser. Ich schätze Ihre Zeit und hoffe aufrichtig, dass Sie den Inhalt informativ fanden. Wenn Sie Fragen oder Antworten haben, zögern Sie nicht, eine unten fallen zu lassen.