Timsort - Timsort

Timsort

Klasse	Sortieralgorithmus
Datenstruktur	Array
Worst-Case- Leistung	${\displaystyle O(n\log n)}$
Best-Case- Leistung	${\displaystyle O(n)}$
Durchschnittliche Leistung	${\displaystyle O(n\log n)}$
Raumkomplexität im schlimmsten Fall	${\displaystyle O(n)}$

Timsort ist ein hybrider stabiler Sortieralgorithmus , abgeleitet von Merge-Sort und Insertion-Sort , der für viele Arten von realen Daten entwickelt wurde. Es wurde 2002 von Tim Peters für die Verwendung in der Programmiersprache Python implementiert . Der Algorithmus findet Teilsequenzen der bereits geordneten Daten (Runs) und verwendet sie, um den Rest effizienter zu sortieren. Dies geschieht durch Zusammenführen von Läufen, bis bestimmte Kriterien erfüllt sind. Timsort ist seit Version 2.3 der Standard-Sortieralgorithmus von Python. Es wird auch verwendet, um Arrays nicht-primitiven Typs in Java SE 7 , auf der Android-Plattform , in GNU Octave , auf V8 , Swift und Rust zu sortieren .

Es verwendet Techniken aus Peter McIlroys Papier "Optimistic Sorting and Information Theoretic Complexity" aus dem Jahr 1993.

Betrieb

Timsort wurde entwickelt, um die Vorteile von Durchläufen aufeinanderfolgender geordneter Elemente zu nutzen, die bereits in den meisten realen Daten vorhanden sind, natürliche Durchläufe . Es iteriert über die Datenerfassungselemente in Läufen und legt diese Läufe gleichzeitig in einen Stapel. Immer wenn die Läufe oben im Stapel einem Zusammenführungskriterium entsprechen , werden sie zusammengeführt. Dies geht so lange, bis alle Daten durchlaufen sind; dann werden alle Läufe zu jeweils zwei zusammengeführt und es bleibt nur noch ein sortierter Lauf übrig. Der Vorteil des Zusammenführens von geordneten Durchläufen anstelle des Zusammenführens von Unterlisten fester Größe (wie beim herkömmlichen Mergesort) besteht darin, dass die Gesamtzahl der zum Sortieren der gesamten Liste erforderlichen Vergleiche verringert wird.

Jeder Lauf hat eine Mindestgröße, die auf der Größe der Eingabe basiert und zu Beginn des Algorithmus definiert wird. Wenn ein Lauf kleiner als diese Mindestlaufgröße ist, wird die Einfügesortierung verwendet, um dem Lauf weitere Elemente hinzuzufügen, bis die Mindestlaufgröße erreicht ist.

Kriterien zusammenführen

Die Läufe werden in einen Stapel eingefügt . Wenn | Z | | Y | + | X | , dann werden X und Y zusammengeführt und auf dem Stack ersetzt. Auf diese Weise wird das Zusammenführen fortgesetzt, bis alle Läufe i erfüllen . | Z | > | Y | + | X | und ii. | Y | > | X | .

Timsort ist ein stabiler Sortieralgorithmus (Reihenfolge von Elementen mit gleichem Schlüssel wird beibehalten) und strebt ausgewogene Zusammenführungen an (eine Zusammenführung führt also Läufe ähnlicher Größe zusammen).

Um die Sortierstabilität zu erreichen, werden nur aufeinanderfolgende Läufe zusammengeführt. Zwischen zwei nicht aufeinanderfolgenden Läufen kann sich innerhalb der Läufe ein Element mit dem gleichen Schlüssel befinden. Das Zusammenführen dieser beiden Läufe würde die Reihenfolge der gleichen Schlüssel ändern. Beispiel für diese Situation ([] sind geordnete Durchläufe): [1 2 2] 1 4 2 [0 1 2]

Beim Streben nach ausgewogenen Zusammenführungen betrachtet Timsort drei Läufe ganz oben auf dem Stapel, X , Y , Z , und behält die Invarianten bei:

Wenn eine dieser Invarianten verletzt wird, wird Y mit der kleineren von X oder Z verschmolzen und die Invarianten werden erneut geprüft. Sobald die Invarianten gelten, kann die Suche nach einem neuen Lauf in den Daten beginnen. Diese Invarianten halten die Zusammenführungen als ungefähr ausgeglichen aufrecht, während sie einen Kompromiss zwischen dem Verzögern der Zusammenführung für die Ausgewogenheit, dem Ausnutzen eines neuen Auftretens von Durchläufen im Cache-Speicher und dem relativ einfachen Treffen von Zusammenführungsentscheidungen aufrechterhalten .

Raum-Overhead zusammenführen

Zum Zusammenführen kopiert Timsort die Elemente des kleineren Arrays (X in dieser Abbildung) in den temporären Speicher, sortiert und füllt dann die Elemente in der endgültigen Reihenfolge in den kombinierten Raum von X und Y.

Die ursprüngliche Merge-Sort-Implementierung ist nicht vorhanden und hat einen Speicherplatz-Overhead von N (Datengröße). In-Place-Merge-Sort-Implementierungen sind vorhanden, haben jedoch einen hohen Zeitaufwand. Um einen mittleren Term zu erreichen, führt Timsort eine Merge-Sortierung mit einem geringen Zeit- und Platzaufwand als N durch.

Zunächst führt Timsort eine binäre Suche durch , um die Position zu finden, an der das erste Element des zweiten Durchlaufs in den ersten geordneten Durchlauf eingefügt werden würde, wobei die Reihenfolge beibehalten wird . Dann führt es den gleichen Algorithmus aus, um die Position zu finden, an der das letzte Element des ersten Laufs in den zweiten geordneten Lauf eingefügt würde, wobei es geordnet bleibt. Elemente vor und nach diesen Positionen befinden sich bereits an ihrem richtigen Platz und müssen nicht zusammengeführt werden. Dann wird das kleinere der verbleibenden Elemente der beiden Durchläufe in den temporären Speicher kopiert, und Elemente werden mit dem größeren Durchlauf in den jetzt freien Speicherplatz zusammengeführt. Wenn der erste Lauf kleiner ist, beginnt die Zusammenführung am Anfang; ist die zweite kleiner, beginnt die Zusammenführung am Ende. Diese Optimierung reduziert im allgemeinen Fall die Anzahl der erforderlichen Elementbewegungen, die Laufzeit und den temporären Platzbedarf.

Beispiel: Zwei Läufe [1, 2, 3, 6, 10] und [4, 5, 7, 9, 12, 14, 17] müssen zusammengeführt werden. Beachten Sie, dass beide Läufe bereits einzeln sortiert sind. Das kleinste Element des zweiten Durchlaufs ist 4 und müsste an der vierten Position des ersten Durchlaufs hinzugefügt werden, um seine Reihenfolge beizubehalten (vorausgesetzt, die erste Position eines Durchlaufs ist 1). Das größte Element des ersten Durchlaufs ist 10 und müsste an der fünften Position des zweiten Durchlaufs hinzugefügt werden, um seine Reihenfolge zu bewahren. Daher befinden sich [1, 2, 3] und [12, 14, 17] bereits in ihrer Endposition und die Durchgänge, in denen Elementbewegungen erforderlich sind, sind [6, 10] und [4, 5, 7, 9]. Mit diesem Wissen müssen wir nur einen temporären Puffer der Größe 2 statt 5 zuweisen.

Richtung zusammenführen

Das Zusammenführen kann in beide Richtungen erfolgen: von links nach rechts, wie beim traditionellen Mergesort, oder von rechts nach links.

Galoppmodus beim Zusammenführen

Elemente (auf die durch einen blauen Pfeil gezeigt) werden verglichen und das kleinere Element wird an seine endgültige Position verschoben (auf die durch einen roten Pfeil gezeigt wird).

Eine individuelle Zusammenführung der Läufe R1 und R2 hält die Anzahl aufeinanderfolgender Elemente, die aus einem Lauf ausgewählt wurden. Wenn diese Zahl den minimalen Galopp-Schwellenwert ( min_gallop ) erreicht, hält Timsort es für wahrscheinlich, dass noch viele aufeinanderfolgende Elemente aus diesem Lauf ausgewählt werden und wechselt in den Galopp-Modus. Nehmen wir an, dass R1 für die Auslösung verantwortlich ist. In diesem Modus führt der Algorithmus eine exponentielle Suche , auch als Galoppsuche bekannt, nach dem nächsten Element x des Laufs R2 im Lauf R1 durch. Dies geschieht in zwei Stufen: Die erste findet den Bereich (2 ^k − 1, 2 ^k+1 - 1), in dem x ist. Die zweite Stufe führt eine binäre Suche nach dem Element x in dem in der ersten Stufe gefundenen Bereich durch. Der Galoppmodus ist ein Versuch, den Zusammenführungsalgorithmus an das Muster der Intervalle zwischen Elementen in Läufen anzupassen.

Alle roten Elemente sind kleiner als blau (hier 21). Somit können sie in einem Stück in das letzte Array verschoben werden.

Galoppieren ist nicht immer effizient. In manchen Fällen erfordert der Galoppmodus mehr Vergleiche als eine einfache lineare Suche . Laut Benchmarks des Entwicklers ist Galoppieren nur dann von Vorteil, wenn das Anfangselement eines Laufs nicht eines der ersten sieben Elemente des anderen Laufs ist. Dies impliziert einen anfänglichen Schwellenwert von 7. Um die Nachteile des Galoppmodus zu vermeiden, werden zwei Maßnahmen ergriffen: (1) Wenn sich herausstellt , dass das Galoppieren weniger effizient ist als die binäre Suche , wird der Galoppmodus verlassen. (2) Der Erfolg oder Misserfolg des Galoppierens wird verwendet, um min_gallop anzupassen . Wenn das ausgewählte Element aus demselben Array stammt, das zuvor ein Element zurückgegeben hat, wird min_gallop um eins reduziert, wodurch die Rückkehr in den Galoppmodus gefördert wird. Andernfalls wird der Wert um eins erhöht, wodurch eine Rückkehr in den Galoppmodus verhindert wird. Bei Zufallsdaten wird der Wert von min_gallop so groß, dass der Galoppmodus nie wieder auftritt.

Absteigende Läufe

Um auch absteigend sortierte Daten zu nutzen, invertiert Timsort streng absteigende Läufe, wenn es diese findet und fügt sie dem Stapel der Läufe hinzu. Da absteigende Läufe später blind umgekehrt werden, erhält das Ausschließen von Läufen mit gleichen Elementen die Stabilität des Algorithmus; dh gleiche Elemente werden nicht umgekehrt.

Mindestauflagengröße

Der Timsort-Algorithmus sucht nach geordneten Sequenzen mit minimaler Größe, minruns, um seine Sortierung durchzuführen.

Da das Zusammenführen am effizientesten ist, wenn die Anzahl der Durchläufe gleich oder etwas kleiner als eine Zweierpotenz ist, und insbesondere weniger effizient ist, wenn die Anzahl der Durchläufe etwas über einer Zweierpotenz liegt, wählt Timsort minrun , um sicherzustellen, dass die ehemaliger Zustand.

Minrun wird aus dem Bereich 32 bis einschließlich 64 ausgewählt, so dass die Größe der Daten, dividiert durch minrun , gleich oder geringfügig kleiner als eine Zweierpotenz ist. Der letzte Algorithmus nimmt die sechs höchstwertigen Bits der Größe des Arrays, fügt eins hinzu, wenn eines der verbleibenden Bits gesetzt ist, und verwendet dieses Ergebnis als minrun . Dieser Algorithmus funktioniert für alle Arrays, einschließlich derer kleiner als 64; für Arrays mit einer Größe von 63 oder weniger setzt dies minrun gleich der Array-Größe und Timsort reduziert sich auf eine Einfügungssortierung.

Analyse

Im schlimmsten Fall nimmt Timsort Vergleiche an, um ein Array von n Elementen zu sortieren . Im besten Fall, der auftritt, wenn die Eingabe bereits sortiert ist, läuft sie in linearer Zeit, d. h. es handelt sich um einen adaptiven Sortieralgorithmus . ${\displaystyle O(n\log n)}$

Es ist gegenüber Quicksort zum Sortieren von Objektreferenzen oder Zeigern vorteilhaft, da diese teure Speicherumleitung für den Zugriff auf Daten und die Durchführung von Vergleichen erfordern und die Vorteile der Cache-Kohärenz von Quicksort stark reduziert sind.

Formale Überprüfung

Im Jahr 2015 fanden niederländische und deutsche Forscher im EU-FP7-ENVISAGE-Projekt einen Fehler in der Standardimplementierung von Timsort.

Insbesondere stellen die Invarianten der Stapellaufgrößen eine enge Obergrenze für die maximale Größe des erforderlichen Stapels sicher. Die Implementierung hat einen Stapel vorab zugewiesen, der ausreicht, um 2 ⁶⁴ Bytes der Eingabe zu sortieren , und weitere Überlaufprüfungen vermieden.

Die Garantie erfordert jedoch, dass die Invarianten für jede Gruppe von drei aufeinanderfolgenden Läufen gelten, aber die Implementierung hat sie nur für die ersten drei geprüft. Mit dem Key- Tool zur formalen Verifizierung von Java-Software fanden die Forscher heraus, dass diese Prüfung nicht ausreicht, und konnten Lauflängen (und Eingaben, die diese Lauflängen erzeugten) finden, die dazu führen würden, dass die Invarianten tiefer im Stapel verletzt werden nachdem die Spitze des Stapels zusammengeführt wurde.

Folglich reicht die zugewiesene Größe für bestimmte Eingaben nicht aus, um alle nicht zusammengeführten Läufe aufzunehmen. In Java generiert dies für diese Eingaben eine Array-out-of-bound-Ausnahme. Die kleinste Eingabe, die diese Ausnahme in Java und Android v7 auslöst, ist groß67 108 864 (2 ²⁶ ). (Ältere Android-Versionen haben diese Ausnahme für bestimmte Eingaben der Größe bereits ausgelöst65 536 (2 ¹⁶ ))

Die Java-Implementierung wurde korrigiert, indem die Größe des vorab zugewiesenen Stapels basierend auf einer aktualisierten Worst-Case-Analyse erhöht wurde. Der Artikel zeigte auch anhand formaler Methoden, wie die beabsichtigte Invariante ermittelt werden kann, indem überprüft wird, ob die vier obersten Läufe im Stapel die beiden obigen Regeln erfüllen. Dieser Ansatz wurde von Python und Android übernommen.

Verweise

Weiterlesen

• Auger, Nicolas; Nicaud, Cyrill; Pivoteau, Carine (2015). "Merge-Strategien: von Merge Sort zu TimSort" . hal-01212839 .
• Auger, Jugé, Nicaud, Pivoteau (2018). „Über die Worst-Case-Komplexität von TimSort“ . ESVG 2018.
• Sam Buss, Alexander Knop. "Strategien für eine stabile Merge-Sortierung." SODA 2019.

Externe Links

• timsort.txt – Originalerklärung von Tim Peters