Timsort

Timsort ist ein Sortieralgorithmus, der Mergesort und Insertionsort kombiniert und in der Praxis eine gute Effizienz aufweist. Tim Peters hat diesen Algorithmus im Jahr 2002 entworfen und er wird in Python verwendet (TimSort ist die Standardimplementierung von list.sort in Python). Der Algorithmus findet sortierte Blöcke - Partitionen in den Daten, wobei jede Partition als Run bezeichnet wird, und führt diese Runs dann nach bestimmten Regeln zusammen. Python verwendet den Timsort-Algorithmus seit Version 2.3 zum Sortieren. Jetzt verwenden auch Java SE7 und Android den Timsort-Algorithmus zum Sortieren von Arrays.

1. Operationen

Die meisten Daten in der Realität haben normalerweise einige bereits sortierte Teile, und Timsort nutzt diese Funktion. Die Eingabeeinheit von Timsort sind keine einzelnen Zahlen, sondern Partitionen. Jede Partition wird als "Run" bezeichnet (Abbildung 1). Für diese Sequenz von Runs wird jedes Mal ein Run zum Zusammenführen entnommen. Jede Zusammenführung kombiniert zwei Runs zu einem Run. Jeder Run muss mindestens 2 Elemente haben. Timsort unterteilt jeden Run in aufsteigende und absteigende Reihenfolge: Wenn ein Run in aufsteigender Reihenfolge ist, muss das nächste Element im Run größer oder gleich dem vorherigen Element sein (a[lo] <= a[lo + 1] <= a[lo + 2] <=...); wenn ein Run in strikt absteigender Reihenfolge ist, d. h. das vorherige Element im Run ist größer als das nächste Element (a[lo] > a[lo + 1] > a[lo + 2] >...), müssen die Elemente im Run umgekehrt werden (beachten Sie, dass der absteigende Teil "strikt" absteigend sein muss, um umgekehrt zu werden. Ein wichtiges Ziel von TimSort ist es, die Stabilität zu erhalten. Wenn die Umkehrung im Fall von >= erfolgt, ist der Algorithmus nicht mehr stabil).

1.1 Minimale Länge des Runs

Ein Run ist eine sortierte Partition. Runs können unterschiedliche Längen haben, und Timsort wählt eine Sortierstrategie basierend auf der Länge des Runs aus. Wenn beispielsweise die Länge eines Runs kleiner als ein bestimmter Wert ist, wird der Insertionsort-Algorithmus zum Sortieren ausgewählt. Die minimale Länge (minrun) eines Runs hängt von der Größe des Arrays ab. Wenn die Anzahl der Array-Elemente kleiner als 64 ist, ist die minimale Länge eines Runs die Länge des Arrays, und Timsort verwendet den Insertionsort-Algorithmus zum Sortieren. Wenn die Anzahl der Array-Elemente größer oder gleich 63 ist, wird für größere Arrays eine Zahl, die als Minrun bezeichnet wird, aus dem Bereich von 32 bis 65 ausgewählt, so dass die Größe des Arrays, dividiert durch die minimale Run-Größe, gleich oder geringfügig kleiner als eine Potenz von zwei ist. Der endgültige Algorithmus dafür nimmt einfach die sechs höchstwertigen Bits der Größe des Arrays, addiert eins, wenn eines der verbleibenden Bits gesetzt ist, und verwendet dieses Ergebnis als Minrun. Dieser Algorithmus funktioniert für alle Fälle, einschließlich des Falls, in dem die Größe des Arrays kleiner als 64 ist.

1.2 Optimierung der Run-Länge

Die Optimierung der Run-Länge bedeutet, dass, wenn die Länge eines Runs kleiner als Minrun ist, um die Länge eines solchen Runs die Minrun-Länge erreichen zu lassen, geeignete Elemente aus dem Array ausgewählt und in den Run eingefügt werden. Dies führt zu ausgeglichenen Längen der meisten Runs, was für das anschließende Zusammenführen von Runs hilfreich ist.

1.3 Zusammenführen von Runs

Nach dem Partitionieren der Runs und dem Optimieren der Run-Längen besteht der nächste Schritt darin, die Runs zusammenzuführen. Das Prinzip des Zusammenführens von Runs besteht darin, die höchste Effizienz in der Zusammenführungstechnik zu gewährleisten. Wenn der Timsort-Algorithmus einen Run findet, legt er die Startposition des Runs im Array und die Länge des Runs in den Stapel und entscheidet dann, ob der Run gemäß den zuvor in den Stapel geschobenen Runs zusammengeführt werden soll. Timsort führt keine nicht - aufeinanderfolgenden Runs im Stapel zusammen (Timsort führt keine nicht - aufeinanderfolgenden Runs zusammen, da dies dazu führen würde, dass das Element, das allen drei Runs gemeinsam ist, in Bezug auf den mittleren Run außer der Reihe gerät).

Timsort führt zwei aufeinanderfolgende Runs im Stapel zusammen. Seien X, Y und Z die Längen der drei Runs oben im Stapel (Abbildung 2). Wenn die folgenden zwei Bedingungen nicht gleichzeitig erfüllt sind, werden die beiden Runs X und Y zusammengeführt, bis die folgenden zwei Bedingungen gleichzeitig erfüllt sind, und dann endet die Zusammenführung:

X>Y+Z
Y>Z

Zum Beispiel: Wenn X<Y + Z, dann werden X + Y zu einem neuen Run zusammengeführt und dann in den Stapel geschoben. Wiederholen Sie die obigen Schritte, bis die beiden Bedingungen gleichzeitig erfüllt sind. Nachdem die Zusammenführung beendet ist, sucht Timsort weiter nach dem nächsten Run und schiebt ihn dann nach dem Auffinden in den Stapel. Wiederholen Sie die obigen Schritte, d. h. jedes Mal, wenn ein Run in den Stapel geschoben wird, wird geprüft, ob zwei Runs zusammengeführt werden müssen.

1.4 Schritte zum Zusammenführen von Runs

Das Zusammenführen von zwei benachbarten Runs erfordert temporären Speicherplatz, und die Größe des temporären Speicherplatzes ist die Größe des kleineren Runs der beiden Runs. Der Timsort-Algorithmus kopiert zuerst den kleineren Run in diesen temporären Speicherplatz und verwendet dann den Speicherplatz, in dem die beiden Runs ursprünglich gespeichert waren, um den zusammengeführten Run zu speichern.

Der einfache Zusammenführungsalgorithmus verwendet einen einfachen Einfügealgorithmus, um Elemente von links nach rechts oder von rechts nach links der Reihe nach zu vergleichen und dann die beiden Runs zusammenzuführen. Um die Effizienz zu verbessern, verwendet Timsort eine binäre Mergesortierung. Verwenden Sie zuerst den binären Suchalgorithmus, um die Einfügeposition zu finden, und fügen Sie dann ein.

Wenn wir beispielsweise zwei Runs A und B zusammenführen möchten und A der kleinere Run ist. Da A und B bereits sortiert sind, findet die binäre Suche, wo das erste Element von B in A eingefügt werden soll (Abbildung 4). In ähnlicher Weise wird das letzte Element von A gefunden, wo es in B eingefügt werden soll. Nach dem Auffinden müssen die Elemente von B nach diesem Element nicht verglichen werden (Abbildung 5). Diese Art der Suche ist bei Zufallszahlen möglicherweise nicht sehr effizient, aber in anderen Fällen ist sie sehr effizient.

1.5 Galloping-Modell

Es beschreibt einen Zusammenführungsprozess ähnlich den obigen Runs. Einzelheiten finden Sie im Wikipedia Galloping Model.

2. Leistung

2.1 Kernprozess von Timsort

Um die Rückverfolgung des aufsteigenden Teils und die Leistungsverschlechterung des absteigenden Teils zu reduzieren, partitioniert der TimSort-Algorithmus die Eingabe entsprechend ihren aufsteigenden und absteigenden Eigenschaften. Die Eingabeeinheit der Sortierung sind keine einzelnen Zahlen, sondern Blöcke - Partitionen. Jede Partition wird als Run bezeichnet. Für diese Run-Sequenzen wird jedes Mal ein Run entnommen und gemäß den Regeln zusammengeführt. Jede Zusammenführung kombiniert zwei Runs zu einem Run. Das Ergebnis der Zusammenführung wird im Stapel gespeichert. Die Zusammenführung wird fortgesetzt, bis alle Runs verbraucht sind, und dann werden die verbleibenden Runs im Stapel zusammengeführt, bis nur noch ein Run übrig ist. Zu diesem Zeitpunkt ist dieser verbleibende Run das sortierte Ergebnis.

Zusammenfassend lässt sich der Prozess des Timsort-Algorithmus wie folgt zusammenfassen:

Wenn die Länge des Arrays kleiner als ein bestimmter Wert ist, verwenden Sie direkt den binären Insertionsort-Algorithmus.
Suchen Sie jeden Run und schieben Sie ihn in den Stapel.
Führen Sie Runs gemäß den Regeln zusammen.

2.2 Leistungsanalyse

Laut der Informatiktheorie kann das vergleichsbasierte Sortieren im Durchschnittsfall nicht schneller als O(n log n) sein. Da der Timsort-Algorithmus die Tatsache ausnutzt, dass die meisten Daten in der Realität einige sortierte Bereiche aufweisen, ist Timsort schneller als O(n log n). Für Zufallszahlen gibt es keine sortierten Bereiche, die genutzt werden können, und die Zeitkomplexität von Timsort beträgt log(n!).

Vergleich der Zeitkomplexität von Timsort mit anderen vergleichsbasierten Sortieralgorithmen.

Vergleich der Raumkomplexitäten.

Erläuterung: JSE 7 verwendet Quicksort nicht zum Sortieren von Objekten, da Quicksort instabil ist, während Timsort stabil ist.

Das Folgende ist eine Passage aus dem Timsort-Implementierungscode in JSE7, die die Vorteile von Timsort gut veranschaulicht:

Eine stabile, adaptive, iterative Mergesortierung, die bei der Ausführung auf teilweise sortierten Arrays weitaus weniger als n lg(n) Vergleiche erfordert und gleichzeitig eine Leistung bietet, die mit einer herkömmlichen Mergesortierung bei der Ausführung auf zufälligen Arrays vergleichbar ist. Wie alle korrekten Mergesortierungen ist diese Sortierung stabil und läuft O(n log n) Zeit (schlimmster Fall). Im schlimmsten Fall benötigt diese Sortierung temporären Speicherplatz für n/2 Objektreferenzen; im besten Fall benötigt sie nur einen kleinen konstanten Speicherplatz.

Im Allgemeinen ist Timsort ein stabiler Algorithmus. Wenn sich bereits sortierte Zahlen im zu sortierenden Array befinden, ist seine Zeitkomplexität geringer als n logn. Wie andere Mergesortierungen ist Timesrot ein stabiler Sortieralgorithmus, und die Zeitkomplexität im schlimmsten Fall ist O(n log n). Im schlimmsten Fall benötigt der Timsort-Algorithmus temporären Speicherplatz von n/2, und im besten Fall benötigt er nur eine sehr geringe Menge an temporärem Speicherplatz.

Leapcell: Die beste Serverless-Plattform für Golang-Webhosting

Abschließend möchte ich die beste Plattform für die Bereitstellung von Golang-Projekten empfehlen: Leapcell

1. Multi – Sprachunterstützung

Entwickeln Sie mit JavaScript, Python, Go oder Rust.

2. Stellen Sie unbegrenzt Projekte kostenlos bereit

Zahlen Sie nur für die Nutzung – keine Anfragen, keine Gebühren.

3. Unschlagbare Kosteneffizienz

Pay - as - you - go ohne Leerlaufgebühren.
Beispiel: 25 US-Dollar unterstützen 6,94 Millionen Anfragen bei einer durchschnittlichen Antwortzeit von 60 ms.