[GO] Ich habe TimSort ~ Anspruchsvolle Sortiermethode studiert, die standardmäßig in Java und Python ~ implementiert ist (Teil 1).

Wie bist du zum Studium von Tim Sort gekommen?

Anfangs dachte ich daran, ein Paar von zwei Elementen ($ m (m-1) / 2 $ Paare) in einer Menge von $ m $ Elementen zu sortieren, und es war bereits $ O (m ^ 2). Da es $ Paare gab, dachte ich, es würde einige Zeit dauern, wenn ich keine Sortierung entwickeln würde, also implementierte und sortierte ich den Heap selbst. (Die Heap-Sortierung wird im schlimmsten Fall ausgeführt. $ O (n \ log n) \ sim O (m ^ 2 \ log m ^ 2) $. Andererseits sind die naive Blasensortierung und die Einfügesortierung $ O (n ^ 2) \ sim O ( Es kostet m ^ 4) $. Hier wird die Anzahl der Paare als $ n \ sim m ^ 2 $) beschrieben.

Rückblickend entwickeln sich Java und Python jedoch von Tag zu Tag weiter. Daher dachte ich, dass sich auch der in der Standardimplementierung verwendete Sortieralgorithmus weiterentwickeln sollte, und untersuchte ihn daher. Ich sah nicht viel Notwendigkeit, es als einfache Methode wie Blasensortierung beizubehalten.

Wie erwartet wurde es nur jeden Tag gewidmet und es wurde ein sehr ausgefeilter Sortieralgorithmus implementiert. Ich heiße Tim Sort.

Programmiersprache, die TimSort implementiert

• Python (implementiert als Standardsortierung in 2.3 und höher)
• Java (Standardimplementierung für Referenztyp-Arrays seit SE7)
• Swift

TimSort soll 2002 erstmals von Tim Peter in Python implementiert worden sein. Tim Peter ist auch als Autor von "The Zen of Python" bekannt, einer bekannten Sammlung von Python-Sprichwörtern.

(Referenz: Wikipedia https://en.wikipedia.org/wiki/Timsort)

Darüber hinaus wird Tim Sort auch in Android Platform, GNU Octave, V8 usw. verwendet.

Übersicht über Tim Sort

Das Video, in dem Tim Sort von Gaurav Sen erklärt wurde, war sehr leicht zu verstehen. Referenz: https://www.youtube.com/watch?v=emeME__917E Bitte beachten Sie, dass indisches Englisch eine starke Angewohnheit hat. (Im Gegenteil, japanisches Englisch scheint für Inder ziemlich süchtig zu machen und kann nicht gehört werden.) Ich möchte hier zusammenfassen, was ich hauptsächlich mit Bezug auf dieses Video studiert habe.

Die schlechteste Rechenzeit von Tim Sort

• O(n\log n)

ist. Es unterscheidet sich nicht wesentlich von der Heap-Sortierung und der Zusammenführungssortierung ($ O (n \ log n)) $, ist aber etwas besser als diese.

Mit einem Wort, die Eigenschaften von Tim Sort

Um es grob auszudrücken, damit Sie leicht ein Bild bekommen können,

• ** Ein gut aussehender Algorithmus, der in einigen Fällen natürlich auf die bestmögliche Sortiermethode umschaltet **

Ich denke es kann gesagt werden.

Wie ich bereits sagte, gibt es keine signifikante Verbesserung der Berechnungszeit im ungünstigsten Fall, wie beim Vergleich zwischen der Blasensortierung $ (O (n ^ 2)) $ und der Heap-Sortierung $ (O (n \ log n)) $. Man kann jedoch sagen, dass es durch die Kombination einiger verbesserter Sortieralgorithmen in allen Fällen als das Beste entwickelt wurde. (Ich denke nicht, dass es immer das Beste ist)

In einigen Fällen sollte die Auswahl der besten Sortiermethode in ** begrüßt werden, wenn verschiedene Anwendungsfälle wie Programmiersprachen erwartet werden **. Wenn Sie eine Vielzahl von Anwendungsfällen abdecken möchten, kann die Datenmenge groß oder klein sein. Ich denke, es geht darum, eine schnellere Sortiermethode bereitzustellen, selbst wenn diese klein ist.

Tim Sort Verfahrensübersicht

Um es grob auszudrücken

1. Gruppieren Sie die zu sortierenden Spalten in einer Reihe kleiner sortierter Spalten (Läufe). ● Verwenden Sie beim Gruppieren in Spalten die Einfügesortierung, die für kleine Größen effizienter ist als die Zusammenführungssortierung

2. Zusammenführungslauf mit Zusammenführungssortierung, aber in diesem Fall ● Übernahme der Zusammenführungsreihenfolge von Läufen, die die Anzahl der Zusammenführungen unterdrücken kann (Stapel unter Verwendung einer Ungleichung der Beziehung nahe der Fibonacci-Zahl) ● Effizientes Zusammenführen (ranglose Dichotomie, Galoppmodus, Zusammenführen benachbarter Speicherbereiche usw.) Wir werden effizient mit.

Ich denke, es wird. Im Folgenden werde ich die Details des Verfahrens betrachten.

1. Teilen Sie die zu sortierende Spalte in eine Reihe kleiner Spalten, die bereits sortiert wurden, "Ausführen".

1-1. Sortierte kleine Spalte "run" (Anzahl der Elemente 32 bis 64)

Wenn wir eine Spalte mit zu sortierenden Elementen erhalten, versuchen wir zunächst, sie in eine Reihe kleiner sortierter Spalten zu sortieren, die "ausgeführt" werden.

Warum ist hier die Größe 32 bis 64? ** Dies liegt daran, dass die Einfügesortierung die maximale Größe ist, die sie zum schnellsten Sortieralgorithmus macht. ** **.

1-2. Vergleich der Insert-Sortierung und anderer Algorithmen

Die folgende Tabelle fasst zusammen, was als grundlegende Sortiermethode angesehen werden kann.

Auf den ersten Blick scheint es, dass die $ O (n \ log n) $ -Methode auf der rechten Seite einheitlich verwendet werden sollte, aber warum sollte die Einfügesortierung auf der linken Seite verwendet werden? (Es tut mir leid für diejenigen, die es verstehen.)

Es ist zu beachten, dass diese Berechnungszeitschätzung gültig ist, wenn ** $ n $ groß genug ist **. Wenn die Daten groß sind, ist die Häufigkeit, mit der die typische Verarbeitung des Algorithmus wiederholt wird, effektiv. Wenn jedoch die Anzahl der Daten gering ist, ist es wichtiger als der Faktor, der von der Anzahl der Daten abhängt, wie kompliziert die Verarbeitung durch den Algorithmus ist. Es wird klappen. Dies liegt an der Komplexität der algorithmischen Verarbeitung, die nicht von der Anzahl der Daten abhängt und ein Term von $ O (1) $ ist. Im Allgemeinen wurde der Algorithmus $ O (n ^ 2) $ früher entwickelt, und das einmalige Verarbeitungsverfahren selbst ist einfach, sodass die Faktoren für diese $ O (1) $ kleiner sind.

Was ist die Bedeutung davon? Die Zahl dieser Schätzung ist feiner. $ O (1) $ Koeffizientenfaktor $ c_ {i, b, s, m, q, h}, \ tilde {c} _ {i, b, s, m, q, h Lassen Sie uns darüber nachdenken, indem wir} $ einschließen.

• $ O (n ^ 2) $ Methode

• Sort einfügen: $ c_i n ^ 2 + \ tilde {c} _i n $

• Blasensortierung: $ c_b n ^ 2 + \ tilde {c} _b n $

• Selektive Sortierung: $ c_s n ^ 2 + \ tilde {c} _s n $

• $ O (n \ log n) $ Methode

• Sortierung zusammenführen: $ c_m n \ log n + \ tilde {c} _m n $

• Schnelle Sortierung: $ c_q n \ log n + \ tilde {c} _q n $ --Günstige Sortierung: $ c_h n \ log n + \ tilde {c} _h n $

Von hier an wird der Faktor $ n $, der beim Lesen ein häufiger Faktor ist, zur Vereinfachung verwendet, wenn um die für den Algorithmus $ O (n \ log n) $ und den Algorithmus $ O (n ^ 2) $ erforderliche Zeit konkurriert wird. Ich würde gerne ausgehen und vergleichen. In diesem Fall, in dem $ n $ klein ist, ist das Verhalten der schlechtesten Zeit $ f (n) $, die jeder benötigt, ungefähr so, wie in der folgenden Grafik gezeigt.

Wenn die Größe der Daten klein ist, ist der zuvor eingeführte Faktor $ O (1) $, der nichts mit der Größe der Daten zu tun hat, zeitlich wirksam. Grundsätzlich ist der Koeffizientenfaktor $ \ tilde {c}, c_ {i, b, s} $ des $ O (n ^ 2) $ -Algorithmus besser als der $ c_ {des $ O (n \ log n) $ -Algorithmus. Es ist kleiner als m, q, h} $, $ \ tilde {c} _ {m, q, h} $, weil es einfacher zu verarbeiten ist. Wenn die Daten größer werden, wird schließlich der Differentialkoeffizient von $ \ log n $ kleiner und die Reihenfolge wird umgekehrt, aber wenn die Datengröße kleiner ist, wird der Gradient der $ \ log n $ -Funktion $ 1 / n. Ich verstehe, dass der $ O (n ^ 2) $ -Algorithmus ein angemessenes Intervall hat, bevor er größer wird, weil $ nicht klein genug ist.

Auf diese Weise ist der $ O (1) $ -Koeffizient, der durch die Kompliziertheit des Verfahrens bestimmt wird, in dem Bereich wirksam, in dem die Daten klein sind. Wenn die Daten klein sind, sollten Sie einen Algorithmus anwenden, der eine einfache Verarbeitung durchführt, sodass ein solcher Koeffizient der kleinste ist. Die Antwort lautet ** Sortierung einfügen **. (In einer Nicht-Koeffizienten-Ansicht sind Einfügesortierungen schneller als Blasensortierungen und wählen in einigen Fällen Sortierungen aus, da sie die Anzahl der Vergleiche verringern können (Überspringen). Derzeit handelt es sich um vollständige Sortierungen einer bestimmten Spalte, also des Teils Sortierung wird nicht berücksichtigt.)

Um den ersten sortierten Unterspaltenlauf zu erstellen, wird daher die Einfügesortierung verwendet, solange die Anzahl der Daten garantiert ist, für die die Einfügesortierung am schnellsten ist. Es wird gesagt, dass die Anzahl der Elemente etwa 32 bis 64 beträgt. ** Daher ist die Anzahl der ausgeführten Elemente auf 32 ~ 64 festgelegt.

1-3. Verbesserung der Sortierung der Einsätze

TimSort verwendet die Einfügesortierung, wenn die Daten klein sind, wie ich zuvor erklärt habe, aber ich möchte sie mit der schnellen Einfügesortierung noch schneller machen, also verwende ich die ** Einfügesortierung **. Die Bisektions-Insert-Sortierung ist ein verbesserter Algorithmus für die Insert-Sortierung, der eine Dichotomie durchführt, um die Insertionsposition zu ermitteln.

1-4 Lokalität des Elements, das den Lauf generiert

Wenn hier ein Lauf gebildet wird, wird der Lauf aufgepumpt, indem nur die Elemente eingefügt und sortiert werden, die in der ursprünglichen angegebenen Spalte in der Nähe vorhanden sind. Daher durchsucht die Einfügesortierung nicht alle Elemente in einer Spalte der Größe $ n , um die Elemente zu finden, die in den Lauf eingefügt werden sollen. Wenn daher die Anzahl der Elemente in der zu sortierenden Spalte groß ist ( n $), endet die für diese Operation erforderliche Zeitreihenfolge bei ungefähr $ O (n) $, was der Anzahl der Läufe entspricht. Diese Reihenfolge ist ein kleiner Begriff im Vergleich zu der Zeit, die für die später erscheinende Zusammenführungssortierung erforderlich ist, und funktioniert nicht für die schlechteste Zeitschätzung.

2. Zusammenführen mit Zusammenführungssortierung.

2-1. Wie können Sortierzeichenfolgen effizient kombiniert werden?

In der Debatte geht es darum, wie die Anzahl der Verknüpfungen reduziert werden kann, um eine Spalte mit der ursprünglichen Größe zu bilden. Es hilft überraschenderweise, die gleiche Regelmäßigkeit wie das Wachstum lebender Organismen in der Natur zu nutzen. Es ist eine Sequenz namens ** Fibonacci-Sequenz **. Diese Zahlenfolge ist ein Muster, in dem Organismen, insbesondere Pflanzen, effizienter wachsen, und die Tatsache, dass sie stetig wachsen, bedeutet, dass große Aggregate effizient und in kurzer Zeit gebildet werden können, wenn dies angewendet wird.

Die Fibonacci-Sequenz wird durch die folgende allmähliche Gleichung beschrieben:

\begin{equation}
a_{m+2} = a_{m+1} + a_{m}
\end{equation}

In dieser Abschlussformel ist das Verhalten bei $ m \ gg 1 $, wenn der erste Zahlenterm $ a_0 = 0, , a_1 = 1 $ ist

\begin{equation}
a_{m} \sim \frac{\phi^m}{\sqrt{5}}, \hspace{2cm} \phi = \frac{\sqrt{5} + 1}{2} \sim 1.6 > 1
\end{equation}

Es wird sein. Daraus können wir erkennen, dass es im inkrementellen Schritt von $ m \ sim \ log n $ wachsen kann, bis es die Zielgröße $ n $ erreicht.

Mit anderen Worten, der Punkt von TimSort ist, dass Sie, wenn Sie eine Run-Join-Verarbeitung mit einer Struktur in der Nähe der Fibonacci-Sequenz durchführen, eine endgültige Liste mit der Anzahl der Zusammenführungen von $ \ log n $ erstellen können.

Wenn Sie eine strenge Fibonacci-Sequenz erstellen, wird es natürlich Zeit und Mühe kosten, daraus eine Struktur zu machen, und es ist verschwenderisch. Ich möchte keine genaue Fibonacci-Sequenz. Daher geht es darum, einen Zusammenführungsprozess durchzuführen, der einer Struktur nahe der Fibonacci-Sequenz ziemlich nahe kommt. Selbst wenn Sie zunächst weit von Fibonacci entfernt sind, können Sie sich dieser Zahl im Verlauf des Prozesses nähern. Die Auftragsschätzung ist eine grobe Schätzung von $ n \ gg 1 $ (es sollte Fibonacci sein, wenn $ n $ wächst).

Dies ist die "Verwendung des Stapels unter Verwendung einer Ungleichung nahe der Fibonacci-Sequenz", die als nächstes erläutert wird.

2-2. Verwendung eines Stapels mit Ungleichung nahe der Fibonacci-Sequenz

Führen Sie den Lauf zusammen, während Sie ihn auf den Stapel legen. (Ich werde das Stapeldiagramm später hinzufügen, wenn ich noch Kapazitätsreserven habe, aber wenn Sie eine Weile auf Wikipedia darauf zugreifen und ein Bild erhalten können)

Referenz (Stapel): https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF

Der Stapel hat im Grunde eine Struktur wie ein Eimer mit demselben Ein- und Ausgang, in den neue Daten von oben eingegeben und oben gestapelt werden. Unten befindet sich die Struktur, in der die alten Mitglieder platziert sind. Beim Abrufen von Daten vom Stapel werden diese aus den obersten Daten extrahiert.

Hier lege ich es in den Stapel und füge die Spalten im Stapel zusammen. Wenn ich jedoch alle Daten eingefügt und die Prozedur der letzten Phase des Zusammenführens eingegeben habe, den Lauf, der sich im Stapel befindet Wir sind bestrebt, die Größenrelationen so zu halten, dass sie die folgenden spiegelmochiartigen Relationen erfüllen. Hier gibt der Index $ 0 $ das oberste Element am oberen Rand des Stapels an. Je höher die Zahl, desto niedriger die Daten. Hier sei das Symbol für run $ r_ {i} (i = 0, 1, \ cdots) $.

\begin{align}
r_{n+2} &> r_{n+1} + r_{n} \\
r_{n+1} &> r_{n}
\end{align}

Wenn Sie sich die allererste Formel ansehen, ist diese Beziehung keine Fibonacci-Sequenz, aber sie sieht mehr oder weniger ähnlich aus und ist eine entspannte Version der Fibonacci-Sequenz. Wenn diese beiden Ungleichungen erfüllt sind, befindet sich das Datenarray im Stapel nahe der Fibonacci-Spalte, und die endgültige Zusammenführungsprozedur lautet $ \ log n $.

Die verbleibende Frage ist, was getan werden sollte, um einen solchen Zustand der Ungleichheit zu erreichen. Dies entspricht dem Ausführen des folgenden Überstands im Schiff des Stapels bei jedem Einfügen von Daten in den Stapel: (Hier wird ein Java-ähnlicher, gefälschter Algorithmus geschrieben.) Benennen Sie das Array, das als Element im Stapel ausgeführt wurde, als ausgeführt. Stellen Sie sich vor, der Index des Arrays wird in aufsteigender Reihenfolge von oben angehängt.

if(runs.length >= 2){
  if(runs[2].length > runs[1].length + runs[0].length){
    if(runs[1].length > runs[0].length){
       break;
    }
    else{
      merge(runs[0], runs[1]);
    }
 }
 else{
   merge(runs[1], min(runs[0], runs[2]));　//min ist läuft[0]Und rennt[2]Dies ist die einzige gefälschte Notation, die die kürzere von darstellt
 }

}

In dem obigen Algorithmus wird die Zusammenführungsoperation ausgeführt, so dass der überstehende Teil der Ungleichung näher kommt, wenn neue Daten in den Stapel gelegt werden. Wenn Sie die Überstandsdaten weiterhin so manipulieren, wird sich schließlich eine Fibonacci-ähnliche Laufsäule bilden.

Hierzu ist eine als Stapel bezeichnete Struktur wirksam, in die Daten von oben eingegossen werden. Das Bild hier ist, den ungeschmolzenen, klumpigen Teig von Okonomiyaki nach und nach auf die Eisenplatte zu gießen und einen Spatel oder etwas anderes zu verwenden, damit der untere Teig eine größere Fläche einnimmt als der obere Teig. Ich denke, es ist ähnlich wie zu tun. Wenn Sie vom Beginn des Eingießens von Daten in den Stapel an weiter gießen, während Sie mit einem "Spatel" drücken, so dass der Boden länger ist, so dass der Überstand allein stabil ist, ist die alte Datenzeichenfolge ohne Versinken Da es durch die Zusammenführungsoperation für eine lange Zeit gedrückt wird, wird es eine bessere und längere Linie, und eine stabile Fibonacci-Zahlenlinie von Lauflinien kann natürlich gebildet werden. Mit anderen Worten, ** die alten Daten haben die Eigenschaft eines Stapels, der unten stagniert, und der Lauf mit einer großen Anzahl von Elementen, die lange Zeit dem Zusammenführungsvorgang ausgesetzt waren, sinkt natürlich unter den Stapel. ** ist der Schlüssel.

Durch Erstellen des Datensatzes von run im Fibonacci-Zustand, um ihn nicht zu übertreiben, kann die Anzahl der Zusammenführungsoperationen auf $ \ log n $ unterdrückt werden.

2-3. Sortiermethode zusammenführen und schlechteste Zeit pro Zusammenführungssortierung

Danach wird die schlechteste Berechnungszeit für eine Zusammenführungssortierung wichtig. Dank dieses bereits sortierten Laufs kann die Ausführungszeit einer Zusammenführungssortierung pro ** auf $ O (n) $ gehalten werden. ** **.

Bei der Zusammenführungssortierung wird zuerst der Speicherbereich gehalten, in dem das zusammengeführte Array gespeichert ist (der kontinuierliche Speicherbereich, der ursprünglich von den beiden Läufen verwendet wurde), und der Speicherbereich dort ist in den kombinierten Elementen der beiden Läufe enthalten. Ich werde sie vom kleinsten in Ordnung bringen. Nennen Sie zunächst die beiden Läufe als zu vergleichende Seite A und als zu vergleichende Seite B. Erstens nimmt die zu vergleichende Seite A nacheinander als "zu vergleichende Elemente von A" in der Reihenfolge von der kleinsten auf. (** Lauf ist bereits sortiert, daher beträgt die Zeit für diese Aufnahme O (1) .) Dieses eine Element wird in der Reihenfolge des kleinsten Elements in B verglichen. ( Auch hier dauert das Aufnehmen vom kleinsten Element nicht lange, da es sortiert ist. ) Hier der Speicher, in dem das Array mit dem kleineren gespeichert ist Ich werde es in die Gegend stellen. Wenn das Element von B klein ist, bleibt das "zu vergleichende Element von A" unverändert, und das kleinere Element von B wird eingefügt. Dann wird das nächst kleinere Element in B mit dem Element von A verglichen, und das kleinere Element von A oder B wird in dem Speicherbereich gespeichert, in dem auch das zusammengeführte Array gespeichert ist. Wenn das "zu vergleichende Element von A" klein ist, speichern Sie es im Speicherbereich und bringen Sie das nächstkleinere Element von A. Starten Sie dann den Vergleich mit dem kleinsten Element von B, das sich nicht im Speicher befindet. ( Die Details hier werden sehr lang sein, daher werde ich versuchen, sie in der Fortsetzung mit Abbildungen und konkreten Beispielen zu erklären. **) Der Punkt hier ist **, weil es bereits sortiert wurde. Die benötigte Zeit entspricht in etwa der Anzahl der Vergleiche, die der Anzahl der Elemente im zusammenführungssortierten Bereich entspricht (da sie gleichzeitig mit dem Vergleich enthalten sind). Mit anderen Worten, die Zeit, die im schlimmsten Fall benötigt wird, ist O (n) **.

Nach diesen Berechnungen beträgt die schlechteste Berechnungszeit von TimSort etwa $ O (n \ log n) $, indem die Berechnungszeit $ O (n) $ pro Zeit mit der Anzahl der Verknüpfungen $ O (\ log n) $ multipliziert wird. Ich denke, es wird.

2-3-1. Sollten wir nicht Dichotomie verwenden?

Die obige Erklärung wird durch lineare Suche erklärt, und ich denke, dass es einen Ansturm gibt, dass es möglicherweise nicht sehr effizient ist. Dies ist jedoch von Fall zu Fall **, und in einigen Fällen kann eine Dichotomie länger dauern. ** Zum Beispiel, wenn zwei Läufe ähnlich groß sind und ein Element und das andere Element nahe beieinander liegen. Wenn Sie in einem solchen Fall eine Dichotomie durchführen, werden Sie auch mit Gegnern völlig unterschiedlicher Größe verglichen, sodass Sie die Größenbeziehung und $ \ log n $ für ein Element überhaupt nicht berücksichtigen müssen. Wir werden die Anzahl der Male durchführen. Wenn Sie dies für alle Elemente tun, kostet es Sie im schlimmsten Fall $ O (n \ log n) $. Daher ist es besser, keine einfache Dichotomie durchzuführen. ** Wenn Sie dies tun, ist die lineare Suche effizienter, wenn bereits sortierte Läufe zusammengeführt werden.

Im Gegenteil, wenn die Größe der beiden Läufe verzerrt ist oder die Verteilung der Größe der Elemente verzerrt ist, gibt es offensichtlich nutzlose Suchen, selbst wenn die lineare Suche durchgeführt wird. Natürlich denke ich, dass es besser ist zu überspringen. Wenn beispielsweise in Lauf B viele Elemente vorhanden sind, die kleiner als der Minimalwert a von Lauf A sind, ist es verschwenderisch, die Größen des Minimalwerts a von Lauf A und die Elemente von Lauf B in der Reihenfolge des Minimalwerts zu vergleichen. Daher ist eine Methode zum Ausführen einer Art Überspringen erforderlich.

** Ungeordnete Dichotomie ** macht das effizient. Dies ermöglicht es, den Fall zu überbrücken, in dem die lineare Suche effizienter und die dichotome Suche effizienter ist, da die Elemente weniger voreingenommen sind.

2-3-2. Keine Bereichshalbierungssuche

Im Englischen wird es Exponentialsuche oder galoppierende Suche genannt, aber es ist wie folgt.

Hier sind die beiden zu verschmelzenden Läufe A und B, und das kleinste nicht zusammengeführte Element von A ist $ A [0] $. Wir werden dies mit dem Element $ B [i] , (i = 0, 1,2,3,4, \ cdots) $ von Lauf B vergleichen.

1. Erhöhen Sie $ B [0], B [1], B [3], B [7], B [15], \ cdots B [2 ^ {n} - 1] $ und das Intervall um 2 Exponenten Finden Sie heraus, wo $ A [0] $ in den Bereich $ (B [2 ^ {n}] \ sim B [2 ^ {n + 1} -1]) $ fällt.

2. Finden Sie heraus, wohin $ A [0] $ geht, indem Sie mit $ (B [2 ^ {n}] \ sim B [2 ^ {n + 1} -1]) $ in diesem Bereich dichotomisieren Machen

Es wird zum Verfahren.

Hier sind einige der großartigen Dinge an diesem Ansatz: In der Kombination von zwei Läufen mit weniger Verzerrung, die die lineare Suche grundsätzlich effizienter macht, liegt sie bei der obigen Suche ungefähr zwischen $ B [0] \ sim B [1] $ und $ B [1]. ] \ sim B [3] $ wird tendenziell zwischen engen Bereichen von $ A [0] $ eingefügt. In einem solchen Fall wird $ A [0] $ frühzeitig im Suchbereich gefangen und verhindert, dass Sie vergeblich weit weg suchen. (Der größte Nachteil der Halbierungssuche) Da der Bereich von $ B [i] $, der das Ziel nach dem Fangen ist, eng ist, gibt es keinen großen Unterschied zwischen der linearen Suche und der Dichotomiesuche von dort. Wenn andererseits die Dichotomie besser ist, ist es ein ziemlich großes Intervall $ (B [2 ^ {n}] \ sim B [2 ^ {n + 1} -1]) (n \ gg 1) $ $ A [0] $ sollte enthalten sein, daher ist in einem solchen Fall die Dichotomie natürlich effizienter. Auf diese Weise kann gesagt werden, dass die ranglose Dichotomie beide Fälle ausgewogen betrachtet.

Grundsätzlich hat Tim Sort die Atmosphäre, einen natürlichen Wechsel zwischen linearer Suche und Dichotomie durch "ranglose Dichotomie" durchzuführen. Es scheint, dass der Index des Umschaltens dort ** Gallop Mode Threshold ** genannt wird. Der Schwellenwert scheint auf ** 7 ** eingestellt zu sein. Dies basiert auf der Anzahl aufeinanderfolgender Elemente vom Anfang (Ende) eines zusammenzuführenden Laufs, die in dieser Reihenfolge in das zusammengeführte Array kopiert werden können. Wenn es mehr aufeinanderfolgende Kopien als diesen Wert ** 7 ** gibt, scheint die Dichotomie aktiv ausgeführt zu werden, indem ** Galoppmodus ** gesagt wird. Der Standard für diese Zahl ** 7 ** scheint aus den bisherigen Ergebnissen zu stammen, sodass die lineare Suche schneller ist, wenn sie 7 oder weniger beträgt.

Wenn im Hintergrund des Einstellens eines solchen Modus die Tendenz besteht, dass solche zwei Läufe in der Nähe des Minimalwerts und des Maximalwerts des Elements liegen, wird die Folge anderer Elemente mittlerer Größe beider Läufe ausgeführt Es scheint, dass es festgelegt ist, weil es eine ähnliche Tendenz in geben wird.

2-4 Speicher zum Kopieren von Spalten, die zum Zusammenführen von Sortierungen verwendet werden

Reservieren Sie beim Zusammenführen von zwei Spalten mit einer Zusammenführungssortierung eine Kopie einer der Spalten im Speicher. Grundsätzlich ist es erforderlich, einen Speicherbereich von $ O (n) $ zu sichern, um eine Zusammenführungssortierung mit der Anzahl der Elemente $ O (n) $ durchzuführen. Das Zuweisen dieses Speicherbereichs ist ein Aufwand bei der Sortierung nach Zusammenführungen. Versuchen Sie, diesen Speicherzuordnungsbereich zu reduzieren, um diesen Overhead zu verringern und Zusammenführungssortierungen schneller durchzuführen.

Wenn in TimSort zwei Läufe vorhanden sind, ** erstellen Sie eine Kopie des Laufs mit der geringeren Anzahl von Elementen. ** Im Fall von run ist es jedoch möglich, die Zuweisung des Speicherbereichs weiter zu reduzieren, da es sich um eine bereits sortierte Spalte handelt. Wie es geht?

Achten Sie zunächst auf den größeren der Mindestwerte der beiden Läufe. Sei A derjenige mit dem größeren Element. Wenn Elemente mit kleineren Werten in Lauf B, der nicht A ist, nacheinander ausgerichtet werden, kann die Unterspalte dort ohne Manipulation belassen werden. (Wie unten beschrieben, ist es effektiv, aufeinanderfolgende Speicherbereiche zusammenzuführen.) Dieser Betrag kann wie zuvor zusammengeführt oder belassen werden, sodass er vom Ziel ausgeschlossen wird. Darüber hinaus werden wir das Gleiche für den größeren tun. Dadurch wird die Größe des effektiven Laufs verringert, der nach Zusammenführung sortiert wird.

Führen Sie bei der Suche nach einer fortlaufenden Spalte wie der oben beschriebenen die zuvor erwähnte "ranglose Dichotomie" durch.

Daher kann der zum Kopieren erforderliche Speicherbereich um die Anzahl aufeinanderfolgender minimaler und maximaler Elemente reduziert werden, die kontinuierlich in das zusammengeführte Array ** kopiert werden. Auf diese Weise scheint der Overhead reduziert und die Geschwindigkeit erhöht zu werden.

2-4-1. Läufe in benachbarten Speicherbereichen werden kombiniert

Wenn Sie einen Lauf in den Stapel legen, ordnen Sie ihn grundsätzlich in der Reihenfolge der benachbarten Kameraden im Speicherbereich an. Wie Sie aus dem obigen Algorithmus zum Zusammenführen von Fälschungen ersehen können, wird der zusammenzuführende Lauf im Stapel nebeneinander zusammengeführt. Wenn Sie diese Art der Zusammenführung fortsetzen, werden die Dinge, die Sie zusammenführen möchten, zwischen benachbarten Speicherbereichen zusammengeführt.

Das ist sehr praktisch. Variablen vom Referenztyp wie Arrays zeigen auf Zeiger oder zeigen nicht auf Zeiger, ohne die Struktur des Speichers selbst zu ändern. Wenn Sie sie zusammenführen, entfernen Sie einfach den zusätzlichen mittleren Zeiger und ändern Sie die zu handhabende Größe. Dies ist einfach als ein Array zu handhaben. (Da die Typen der Elemente des zu sortierenden Arrays von Anfang an gleich sind), ist zu erwarten, dass ein großes Array leicht erstellt und die Operation des Arrays leicht ausgeführt werden kann. (Bitte beeilen Sie sich hier.)

Und noch besser, da run ein bereits sortiertes Array ist, können Sie die folgenden Annehmlichkeiten nutzen:

• Wenn es ein Sub-Array gibt, das aus Elementen besteht, die kleiner als der Anfang des Back-Arrays im Array im Bereich vor dem Speicher sind, wird das Sub-Array als sortierter Zustand vervollständigt, ohne wirklich etwas zu tun.
• Umgekehrt, wenn es ein Subarray gibt, das aus Elementen besteht, die größer als das letzte Element des vorherigen Arrays im Array im Bereich hinter dem Speicher sind, wird das Subarray als sortierter Zustand abgeschlossen, ohne wirklich etwas zu tun. Es gibt.

Auf diese Weise kann gelesen werden, dass die sortierte Natur des Laufs und die benachbarte Natur des Speichers unnötige Operationen effektiv sparen.

Schließlich

Ich habe versucht, es mit vielen sinnlichen Worten und intuitiven Berechnungen zu erklären, damit ich wütend werde und TimSort selbst verstehe. Es mag ein stirnrunzelnder Artikel für diejenigen gewesen sein, die sehr streng sind und Genauigkeit bevorzugen. Auf der anderen Seite wäre es eine Liste von in Rauch gehüllten Fachbegriffen, selbst wenn ich Angst hätte, Fehler zu machen, und nicht in den Kern des Aufbaus meines Verständnisses eintreten könnte, so dass ich damit unzufrieden wäre. Ich fühle mich wie ich geworden bin.

Einige Leute beschweren sich vielleicht über Artikel, die nicht sehr genau sind, aber als ich sie schrieb, hat es Zeit und Mühe gekostet, und genauere Ausdrücke sind in der Fortsetzung und der zweiten und nachfolgenden Ausgabe verfügbar. Ich würde es begrüßen, wenn Sie mir verzeihen könnten, dass ich körperliche Kraft angesammelt habe.

Außerdem hat es einige Zeit gedauert, um zu verstehen und hungrig zu werden, und ich denke, es gibt einige Teile, die aufgrund mangelnden Verständnisses völlig missverstanden wurden. Wenn Sie einen solchen Punkt finden, würden wir uns freuen, wenn Sie uns darauf hinweisen und uns eine Anleitung geben könnten.