Und mehr über Sorten

Ich würde es wagen, dieses Thema noch einmal anzusprechen. Ich beginne mit einem Link zu einem Artikel von Mikhail Opanasenko (oms7) , der sowohl hinsichtlich des Arbeitsaufwands als auch der Anzahl der zitierten Links sehr beeindruckend ist. Er begann, sein Material vorzubereiten, ohne über diese Veröffentlichung Bescheid zu wissen, was nach seiner Einarbeitung zu der Notwendigkeit führte, es inhaltlich zu verarbeiten. Für diejenigen, die diesen Artikel bereits gelesen haben, informiere ich Sie, dass in meinem Material verschiedene Arten von Daten untersucht werden, insbesondere Zeichenfolgen und reelle Zahlen, die Boost- und BSD-Bibliotheken verwendet werden und einige andere Themen, die im Artikel fehlen, erwähnt werden.

Es gibt Dutzende verschiedener Möglichkeiten, Datenelemente in der richtigen Reihenfolge anzuordnen. Unter ihnen gibt es solche, die schnell arbeiten, so dass sie beispielsweise jedes Datenarray im RAM des Computers in maximal wenigen Minuten sortieren können. Insbesondere kann gesagt werden, dass durch schnelles Sortieren eine Milliarde Ganzzahlen in einem guten modernen Personal Computer in weniger als hundert Sekunden organisiert werden. Wenn Sie primitive, langsame Methoden verwenden, z. B. Blasensortierung oder Auswahlsortierung, um eine größere Anzahl von Elementen zu sortieren, kann die für eine solche Datenverarbeitung aufgewendete Zeit alle Erwartungen übertreffen - eine solche „Verarbeitung“ kann tatsächlich mehrere Tage, Wochen und sogar Jahre dauern. Dieser große Unterschied wird durch die Tatsache verursacht, dass die Sortierzeit durch schnelle Methoden ungefähr proportional zu N log N und primitiv - N ^{2 ist} . Mit zunehmendem N wird der Unterschied zwischen den beiden Werten sehr deutlich. Daher ist es sinnvoll, primitive Methoden nur für die Arbeit mit kleinen Daten zu verwenden, beispielsweise auf modernen Computern mit bis zu mehreren tausend Elementen. Es ist auch selbstverständlich, sie zum Unterrichten der Grundlagen des Programmierens und des logischen Denkens zu verwenden, da sie viel einfacher sind als schnelle Methoden.

Ich möchte die Sortiermethoden verstehen, die in den aktuellen Standardbibliotheken vorhanden sind. Finden Sie heraus, wie groß der Unterschied zwischen ihnen in Bezug auf ihre Hauptmerkmale, Arbeitsgeschwindigkeit und auch ihre charakteristischen Merkmale ist. Darüber hinaus werden wir auf dem Weg zum Vergleich und für den Verstand einige Methoden betrachten, die nicht schwer zu implementieren sind. Es ist auch erwähnenswert, dass der Optimierer des GCC-Compilers und möglicherweise anderer guter Compiler sehr gut mit Sortierungen zusammenarbeitet und den Code mehrmals beschleunigt (manchmal sogar mehr als fünfmal).

Beginnen wir mit der Blasensortiermethode als der einfachsten und langsamsten. Nach dieser Methode müssen Sie das Datenarray immer wieder durchgehen, benachbarte Elemente vergleichen und ihre Positionen ändern, wenn die Reihenfolge zwischen ihnen unterbrochen ist. Nach jedem Durchgang befindet sich mindestens ein Element (das größte oder kleinste - abhängig von der ausgewählten Reihenfolge) an seiner Stelle. Neben der Einfachheit hat dieses Verfahren einen weiteren Vorteil: Es benötigt keinen zusätzlichen Speicher. Ein weiteres Merkmal der Blasenmethode ist: Sie verarbeitet die bereits bestellten Daten sehr schnell und macht sie in einigen Fällen zu einer der schnellsten Methoden. Wenn die Daten nur teilweise geordnet sind, funktioniert diese Methode schneller, in den meisten Fällen jedoch nur geringfügig. Für Tests habe ich die folgende Implementierung verwendet .

Eine andere langsame Methode ist die Auswahlsortierung. Hier werden bei jedem Durchgang zuerst die größten und kleinsten Elemente in den Daten gefunden, und dann werden diese Elemente an den Extrempositionen platziert, die der ausgewählten Reihenfolge entsprechen. Beim nächsten Durchgang sortieren wir die Daten ohne diese extremen Elemente. Diese Methode ist so einfach wie das Sortieren von Blasen und erfordert keinen zusätzlichen Speicher, ist jedoch spürbar schneller. Darüber hinaus führt das Sortieren nach dieser Methode eine Mindestanzahl von Permutationen von Datenelementen auf. Wenn Permutationen viel langsamer als Vergleiche sind, kann daher die Reihenfolge nach dem Auswahlverfahren akzeptabel sein, wenn die Anzahl der Datenelemente gering ist. Hier ist meine Implementierung . Diese Sortierung wird häufiger durchgeführt, wobei nur ein Element pro Durchgang installiert wird. Die Heap- Sortierung (oder Pyramiden-Sortierung), die später erläutert wird, ist die am weitesten fortgeschrittene Version der betreffenden Sortierung.

Der Code für die zuletzt betrachtete langsame Methode, die Einfügesortierung, ist wahrscheinlich der kürzeste aller Codes, die die Sortierung implementieren. Daher wird diese Methode manchmal von komplexen schnellen Sortierungen in Fällen verwendet, in denen die Anzahl der zu sortierenden Elemente gering ist (mehrere Zehner). Es ähnelt dem Sortieren nach einer Blase, da hier und da die benachbarten Elemente nacheinander verglichen werden. Das Sortieren nach Einfügungen sucht jedoch nach dem nächsten Element für die richtige Position im bereits sortierten Teil der Daten und schiebt das extreme Element nicht nur an die extreme Position. Bei diesem Ansatz wird auch kein zusätzlicher Speicher benötigt. Wie bei der Blasensortierung ist die Einfügungssortierung bei bestellten Daten sehr schnell und bei teilweise geordneten Daten schneller. Im letzteren Fall deutlich schneller als die Blase. Normalerweise ist das Sortieren nach Einfügungen etwas schneller als das Sortieren nach Auswahl. Und im Gegensatz zu letzterem ist es wie die Blasensortierung stabil. Am schlimmsten ist, dass die Einfügesortierung mit Daten in umgekehrter Reihenfolge funktioniert, wodurch sie manchmal die langsamste der langsamsten werden. Für Tests wurde die folgende Implementierung verwendet. Sie kann etwas beschleunigt werden, wenn Sie nicht die lineare, sondern die binäre Suche verwenden, z. B. mit der Funktion std :: bsearch. Eine signifikante Beschleunigung kann durch Verwendung einer Listentypstruktur erreicht werden, bei der das Einfügen eines Elements sehr schnell erfolgt. Sie können auch feststellen, dass dies die natürlichste Sortierung ist - sie wird beispielsweise normalerweise beim Kartenspielen intuitiv verwendet.

Die Shell- Sortierung ist die einfachste unter den schnellen Methoden und eignet sich gut für Schüler, die gerade erst mit dem Programmieren beginnen. Es ist nur eine Modifikation der Blasensortierung. Der einzige Unterschied zwischen ihnen besteht darin, dass bei der Shell-Sortierung der Abstand zwischen den verglichenen Elementen von Gang zu Gang variiert, vom größeren im ersten Durchgang bis zum 1 im letzten Durchgang, sodass die Shell-Methode in diesen letzten Durchgängen zur primitiven Blasensortierung ausartet. Donald Shell veröffentlichte den grundlegenden Sortieralgorithmus, der 1959 seinen Namen erhielt. Somit ist dies eine der ersten universellen Sortierungen, die schnell arbeiten. Zum Vergleich wurde der schnelle Sortieralgorithmus zwei Jahre später veröffentlicht, und Tims beliebte Sortierung oder introspektive Sortierung wurde erst in den 90er Jahren bekannt. Mit der Shell-Sortierung sind einige interessante ungelöste mathematische Probleme verbunden, von denen das wichtigste darin besteht, die Verschiebungen zwischen den verglichenen Elementen optimal auszuwählen. Einige Aufzeichnungssequenzen wurden gefunden, zum Beispiel A102549 . Solche Sequenzen werden durch kolossale Berechnungen gefunden, so dass sie eine sehr kurze Länge haben. A102549 besteht nur aus 8 Elementen, was nur für Daten bis zu etwa 3.000 Elementen ausreicht. Für Big Data müssen Fortsetzungen fast zufällig betrachtet werden. Verwendete Werte nahe den Potenzen von 2, e , 2,25 und 3. Primzahlen nahe den Potenzen von 2 zeigten die schlechtesten Ergebnisse und waren den besten deutlich unterlegen. Die anderen drei Optionen erwiesen sich jedoch als ungefähr gleich in Bezug auf die Auswirkungen auf die Leistung und wahrscheinlich sehr nahe am Optimum. Darüber hinaus ergab die Verwendung von Primzahlen in diesen drei Fällen keine greifbaren Vorteile. Es ist merkwürdig, dass die auf Wikipedia vorgeschlagenen Verzerrungen (mit einer Basis von 2,25), die auf Verweisen auf die entsprechenden Werke beruhen, nicht die besten Ergebnisse bei den Tests zeigten, obwohl ihre Unterschiede zu den besten sehr unbedeutend waren (nicht mehr als 5-10%). Die Verwendung von A102549 als Ausgangspunkt ergab ebenfalls keine erkennbaren Ergebnisse. Mikhail Opanasenko versuchte auch, die Shell-Sortierung zu entschlüsseln und erzielte ein interessantes Ergebnis, dass die durch die Formel s _{n + 1} = 10s _n / 3 ausgewählten Verschiebungen einen sehr guten Effekt ergeben und vielleicht sogar nahezu ideal sind. Meine Ergebnisse bestätigen dies. In vielen Fällen waren es solche Verzerrungen, die das beste Ergebnis erbrachten, obwohl dies nicht immer der Fall war und die Lücke zum nächsten Ergebnis recht gering war (etwa 5%). Mein Code zum Implementieren von Shell-Sortierungen verwendet kleine Tabellen mit Offsets. Wenn Sie jedoch keine Primzahlen verwenden, können diese Offsets für Tabellen fast sofort berechnet werden, wie dies bei der Implementierung einer der angegebenen Varianten dieser Sortierung der Fall war.

Es ist interessant, dass wenn wir Offsets in der Nähe der Dreierpotenzen auf etwas andere Weise nehmen und einen etwas anderen Algorithmus verwenden (siehe Implementierung ), bei 32-Bit-Zahlen Geschwindigkeiten nahe am Besten erzielt werden, bei längeren Zahlen und Leitungen jedoch manchmal eine erhebliche Verlangsamung mehr als 100%. Die Ergebnisse für den besten von oms7 verwendeten Algorithmus sind ebenfalls in der folgenden Tabelle aufgeführt. Obwohl er in der Reihenfolge gute Ergebnisse zeigt, bleibt er in Bezug auf die absoluten Werte deutlich hinter den Führenden zurück.

Wird es jemals einen Weg geben, die besten Offsets zu finden? Vielleicht, aber ich wage zu behaupten, dass es nicht bald ist. Die Shell-Sortierung wird im Linux-Kernel verwendet, und in mindestens einer C-Bibliothek wird der Code für die Standardfunktion qsort () verwendet. Es wurde theoretisch bewiesen, dass die optimale Sortiergeschwindigkeit von Shell in der Reihenfolge nur geringfügig langsamer ist als die „echten“ schnellen logarithmischen Methoden. In der Tat wird die Abhängigkeit der durchschnittlichen Datenverarbeitungszeit von ihrer Größe für eine optimale Shell-Sortierung durch die Formel ∽ N (log N / log log N ) ^{2 beschrieben} , die selbst für sehr großes N der für andere schnelle Methoden typischen Formel ∽ N log N sehr nahe kommt. Normalerweise ist die Shell-Sortierung in der Reihenfolge oft sogar schneller als theoretisch schnellere Methoden und ergibt sich nur geringfügig, wenn ziemlich große Arrays (in der Größenordnung von 10 Millionen Elementen) verarbeitet werden. Diese Sortierung benötigt absolut keinen zusätzlichen Speicher und verhält sich stabil für eine Vielzahl von Optionen zum Füllen von Daten, verglichen mit einer schnellen Sortierung. Die Shell-Methode besitzt nicht die Stabilitätseigenschaft.

Die schnelle Sortierung ist nur geringfügig komplexer als der Shell-Algorithmus und immer noch eine der schnellsten Methoden zum Organisieren zufällig gestreuter Daten. Diese Sortierung weist jedoch mehrere Nachteile auf. Sie braucht zusätzliches Gedächtnis und in sehr seltenen Fällen arbeitet es extrem langsam, entsprechend einer quadratischen Abhängigkeit. Die Hauptidee dieser Methode besteht darin, die Daten in zwei Teile zu teilen: Die Daten in einem Teil sollten mehr oder weniger (abhängig von der ausgewählten Reihenfolge) als im anderen sein. Es gibt verschiedene Methoden für diese Trennung. Idealerweise sollten bei jeder Teilung beide Teile ungefähr gleich groß sein, und am schlimmsten, wenn sich herausstellt, dass eines der Teile während der Teilung nur aus einem Element besteht. Betrachten wir mehrere Implementierungen von schnellen Sortieralgorithmen, insbesondere die Hoar-Methode , bei der ein Referenzelement, das Daten in zwei Teile teilt, aus der Mitte der sortierten Daten ausgewählt wird.

Wir betrachten auch den extrem kompakten Lomuto-Algorithmus , der manchmal etwas (etwa 1%) schneller ist als die betrachtete Hoare-Methode. In typischen Sonderfällen, beispielsweise bei geordneten, inversen oder malovarianten Daten, zeigt die Lomuto-Methode jedoch extreme Langsamkeit. Unter den Optionen, die für eine schnelle Sortierung in Betracht gezogen wurden, erwies sich dies als die gierigste für die Stapelgröße während praktischer Läufe: Beim Sortieren relativ kleiner Arrays hatte nur diese Sortierung nicht genügend 8 Megabyte für den Stapel, ich musste diese Größe durch ulimit mehr einstellen. Diese Gier nach dem Stapel führt zu großen Verlangsamungen bei der Verarbeitung von Big Data (zig Millionen Zeilen), und ich habe Schwierigkeiten, seine Natur zu nennen. Ich kann nur sagen, dass es besser ist, diese Sortierung aus dem nächsten Absatz nicht mit solchen Daten zu verwenden.

Die Lomuto-Methode wählt das letzte Element als Referenzelement aus, es ist jedoch möglich, eine schnelle Sortierung ohne unterstützendes Element zu implementieren, genauer gesagt, die Auswahl eines solchen Elements erfolgt hier aufgrund einer bereits durchgeführten Datenhalbierung. Es stellte sich heraus, dass diese Sortierung nach Geschwindigkeitseigenschaften der Lomuto-Methode nahe kommt, obwohl sie normalerweise etwas schneller ist und in extremen Fällen merklich schneller als Lomuto, aber langsamer als Hoar.

Im Jahr 2009 wurde ein Schnell-Sortier- Algorithmus mit zwei Ankern veröffentlicht, der zum Standard für die Java-Sprache wurde. Dieser Algorithmus reduziert die Anzahl der Permutationen um 20% im Vergleich zu den besten typischen, aber die Anzahl der Vergleiche ändert sich nicht. Sein Autor ist Vladimir Yaroslavsky. Es funktioniert in der Regel wirklich schneller als andere schnelle Sorten. Ich habe es ein wenig optimiert, indem ich die seit langem bekannte Tatsache verwendet habe, dass Swap in der x86-Architektur normalerweise schneller als die Zuweisung funktioniert und für C ++ - Zeichenfolgen viel, viel schneller ist. Alle bisher berücksichtigten schnellen Sortierungen haben nicht die Stabilitätseigenschaft.

Zusätzlicher Speicher für die schnelle Sortierung ist erforderlich, um rekursive Aufrufe zu organisieren. Der zweite derartige Aufruf kann jedoch durch eine Schleife ersetzt werden, indem die Schwanzrekursion optimiert wird, was in Bezug auf die Geschwindigkeit möglicherweise keine Gewinne bringt, aber die Größe der verwendeten zusätzlichen Daten erheblich verringert. Ich habe die Hoar-Sortieroption mit dieser Optimierung implementiert. Darüber hinaus können Sie in Systemprogrammen den Stapelzeiger überprüfen. Wenn er sich einem kritischen Wert nähert, können Sie einfach alle rekursiven Aufrufe zurücksetzen und erneut mit dem Sortieren beginnen. In diesem Fall ist es offensichtlich, dass Sie die Option für die schnelle Sortierung verwenden müssen, die beispielsweise bei fast geordneten Daten nicht langsamer wird , die oben vorgeschlagene Version von Hoar. Die Bekämpfung der Verwendung von zusätzlichem Speicher kann als Hauptidee der schnellen Sortierung aus der Standard-C-Sprachbibliothek in GCC angesehen werden. Es gab im Allgemeinen die Rekursion auf. Stattdessen verwenden sie ihre Simulation, mit der ein Drittel die Belastung des Stapels reduzieren kann. Der Code war ziemlich groß, ungefähr 150 Zeilen. Über diese Sortierung wird es unten noch ein wenig Material geben.

Die Hash- Sortierung kann sehr schnell sein, nahe ∽ N. Manchmal kann es jedoch zu einer quadratischen Abhängigkeit kommen. Die Geschwindigkeit dieser Sortiermethode hängt stark von der Eingabe ab. Wenn die Daten durch die Hash-Funktion gleichmäßig über das Hilfsarray verteilt werden, erhalten wir die schnellste lineare Beziehung. Und wenn alle Daten in der Nähe mehrerer weit voneinander entfernter "Massenschwerpunkte" gruppiert sind oder wenn es viele identische Datenelemente gibt, dh wenn viele Hash-Kollisionen auftreten, erhalten wir die schlimmste Abhängigkeit vom Typ ∽ N ² . Wie bei der Baumsortierung benötigen Sie zum Sortieren des Hashs eine Menge zusätzlicher Daten. In der folgenden Codeliste benötigen Sie beispielsweise 12 zusätzliche Bytes für jede sortierbare Ganzzahl (int32, x86-64). Eine interessante Eigenschaft der Hash-Sortierung ist das Fehlen von Vergleichsoperationen zwischen Datenelementen, was diese Sortierung von allen oben betrachteten unterscheidet. Genauer gesagt werden diese Operationen nur für Kollisionen benötigt. Wenn Sie Daten sortieren, bei denen der Schlüssel mit dem gesamten Datenelement übereinstimmt, können Sie einen zusätzlichen Zähler für die Anzahl identischer Elemente verwenden. Dies ist jedoch eher eine zweifelhafte Optimierung. Sie können auch einen Binärbaum anstelle einer Liste zum Speichern von Hash-Kollisionsdaten verwenden. Dies beschleunigt die Arbeit für einzelne Einzelfälle bei vielen Kollisionen erheblich. Insgesamt verlangsamt sich die Verwendung eines Binärbaums jedoch in vielen Fällen und dies trotz der Tatsache, dass in diesem Fall das Element Daten müssen fast 100 Bytes zusätzlicher Informationen speichern. Ich habe drei Optionen für die Hash-Sortierung mithilfe eines Binärbaums implementiert: Eine verwendet einen ungeordneten Baum und die anderen beiden verwenden Standardbäume aus den Standard- und Boost-Bibliotheken. Die Hash-Sortierung ist praktisch nicht zum Sortieren von Textzeichenfolgen geeignet, außer für sehr kurze, da es unmöglich ist, eine gute Hash-Funktion für solche Daten zu erstellen. Ich konnte den Standard-C ++ - Hash (unordered_multiset) nicht zum Sortieren anpassen: Ich habe versucht, monotone Hash-Funktionen und Ordnungsbeziehungen anstelle von Gleichheit zu verwenden - dies hat nicht funktioniert.

Die Array-Sortierung ist der vorherigen sehr ähnlich. Es wird auch ein Hilfsarray verwendet, in das Werte von der Hash-Funktion eingegeben werden. Im Falle einer Kollision muss das fortlaufende Fragment der belegten Elemente nach links oder rechts verschoben werden, um die durch die Hash-Funktion für das neue Element angegebene Position freizugeben. Um eine gute Geschwindigkeit zu erzielen, muss das Hilfsarray mehrmals (von 2-3) größer sein als das ursprüngliche. Mit zunehmender Größe des Hilfsarrays steigt die Geschwindigkeit in Abhängigkeit von den sortierten Daten und der damit verbundenen Hash-Funktion nur bis zu einem bestimmten Grenzwert an und nimmt dann (normalerweise von 4 bis 5) ab. Die Betriebsgeschwindigkeit entspricht in etwa der des Hashs, ist jedoch bei guten Daten etwas schneller und bei schlechten Daten spürbar langsamer. Diese Art benötigt auch viel zusätzlichen Speicher.Wenn wir die Anzahl der Elemente im sortierten Array auf etwas mehr als vier Milliarden beschränken, benötigt ein dreifaches Hilfsarray die gleiche Menge zusätzlicher Daten wie das Sortieren mit einem Hash, und ein dreifaches benötigt 28 Bytes, was deutlich weniger ist als beim Sortieren nach einem Baum oder viel weniger als ein Hash mit Bäumen. Diese Sortierung ist auch für die Arbeit mit Strings fast ungeeignet. Es gibt keinen Wikipedia-Artikel über einen solchen Algorithmus, aber hier ist meine Implementierung .

Interessant ist , dass in einem guten Bewertung in Wikipedia, Artikel in der Regel gibt es keine Erwähnung solcher Zwischen Techniken, wie das Array sortieren und Hash, die zwischen Methoden auf einem Vergleich der Elemente basieren natürlich platziert sind, und Methoden basierend auf dem absoluten Wert der Elemente.

Eine der schnellsten Sortierungen, bei denen überhaupt keine Vergleiche verwendet werden, ist die seit dem 19. Jahrhundert bekannte bitweise Sortierung .(Radix-Sortierung). Ihre Idee ist sehr einfach - Sie müssen mit Gruppen von Bits der Datendarstellung arbeiten (für Tests habe ich Gruppen von 8, 11 und 16 Bits genommen). Für jede Gruppe werden Tabellen erstellt und die Ergebnisse auf relativ einfache Weise kombiniert. Es gibt zwei Hauptmethoden für die bitweise Sortierung. Es ist bequemer, die Ziffern zum Sortieren von Zahlen von rechts nach links zu verwenden (dies ist die Option LSD - Least Significant Digit) und zum Sortieren von Zeichenfolgen von links nach rechts (dies ist die Option MSD - Most Significant Digit). Die bitweise Sortierung ist häufig erheblich schneller als jede andere Datenbestellmethode. Überraschenderweise ist die Unterstützung für die bitweise Sortierung immer noch nicht sehr bedeutsam: Sie befindet sich weder im Boost noch in der Standard-C ++ - Bibliothek. Mir ist nicht einmal die Version für eine bekannte Bibliothek für die Arbeit mit C ++ - Zahlen oder Zeichenfolgen bekannt. Diese Art hatnatürlich und Nachteile. Es ist sehr empfindlich gegenüber der Art der zu sortierenden Daten. Sie müssen beispielsweise eine eigene Version dieser Sortierung für Daten jeder Größe haben, spezielle Optionen für vorzeichenlose und vorzeichenbehaftete Ganzzahlen festlegen und die Unterstützung für die Arbeit mit reellen Zahlen kann einen erheblichen Aufwand erfordern. Wenn die Reihenfolge vom niedrigstwertigen bis zum wichtigsten Byte verwendet wird, benötigt die Variante normalerweise zusätzlichen Speicher, etwas mehr als für die Anfangsdaten (dies ist erheblich weniger als für die Sortierung nach einem Hash oder Array und noch mehr nach einem Baum). Darüber hinaus ist diese Option zum Sortieren langer Zeichenfolgen von geringem Nutzen. Mein Code für diese ArtSie müssen spezielle Optionen für vorzeichenlose und vorzeichenbehaftete Ganzzahlen festlegen, und die Unterstützung für die Arbeit mit reellen Zahlen kann einen erheblichen Aufwand erfordern. Bei Verwendung der Reihenfolge vom niedrigstwertigen bis zum wichtigsten Byte benötigt die Variante normalerweise zusätzlichen Speicher, etwas mehr als für die Anfangsdaten (dies ist erheblich weniger als beim Sortieren nach einem Hash oder Array und noch mehr nach einem Baum). Darüber hinaus ist diese Option zum Sortieren langer Zeichenfolgen von geringem Nutzen. Mein Code für diese ArtSie müssen spezielle Optionen für vorzeichenlose und vorzeichenbehaftete Ganzzahlen festlegen, und die Unterstützung für die Arbeit mit reellen Zahlen kann einen erheblichen Aufwand erfordern. Wenn die Reihenfolge vom niedrigstwertigen bis zum wichtigsten Byte verwendet wird, benötigt die Variante normalerweise zusätzlichen Speicher, etwas mehr als für die Anfangsdaten (dies ist erheblich weniger als für die Sortierung nach einem Hash oder Array und noch mehr nach einem Baum). Darüber hinaus ist diese Option zum Sortieren langer Zeichenfolgen von geringem Nutzen. Mein Code für diese ArtDiese Option eignet sich nicht zum Sortieren langer Zeichenfolgen. Mein Code für diese ArtDiese Option eignet sich nicht zum Sortieren langer Zeichenfolgen. Mein Code für diese Arthier basiert es auf dem Code aus dem erwähnten oms7-Artikel. Die Option für die umgekehrte Bytereihenfolge ist vielseitiger und eignet sich sehr gut zum Sortieren von Zeichenfolgen. Diese Option kann ohne Verwendung zusätzlichen Speichers implementiert werden (der Preis hierfür ist der Verlust der Stabilitätseigenschaft), wie dies in der Funktion radixsort () der bsd-Bibliothek der Fall ist. Mein CodeFür diese Option basiert sie ebenfalls auf dem oms7-Code. Sie verwendet zusätzlichen Speicher, etwas größere Quelldaten, hat die Stabilitätseigenschaft, ist jedoch nicht für Zeichenfolgen optimiert und weist daher deutlich schlechtere Leistungseigenschaften auf als die ähnliche Funktion sradixsort () aus der bereits erwähnten bsd-Bibliothek . Diese Sortierung kann überraschend schlechte Ergebnisse zeigen, wenn mit kleinen numerischen Arrays gearbeitet wird, die mehrere Größenordnungen langsamer als gerade Blasen arbeiten, obwohl es sich um sehr kleine Werte von nicht mehr als einigen Millisekunden handelt und dieser Unterschied nicht leicht zu bemerken ist. Dies liegt an der Tatsache, dass Hilfsarrays kleiner Größe verwendet werden. Beim Sortieren von Daten kleiner Größe können diese kleinen Größen jedoch größer sein als die sortierten Daten selbst.Um Verlangsamungen zu vermeiden, verwendet die Option "von links nach rechts" in solchen Fällen die Einfügesortierung anstelle der Hauptsortierung. Zusammenfassend ist anzumerken, dass dies die einzige mir bekannte relativ beliebte Sortierung ist, die immer zuverlässig mit einer Geschwindigkeit von ∽ arbeitetN , aber der Proportionalitätskoeffizient hängt hier von der Größe der Datenelemente ab und kann für Zeichenfolgen oder lange Zahlen durchaus erkennbar sein.

Ausführungsbeispiel MSD radix Sortieranlage zu sortieren ist Strahl eine Datenstruktur , die effektiv zuzuordnen Schlüssel assoziative Array ermöglicht. Meine Implementierung erwies sich trotz der Optimierung der Speichernutzung immer noch als sehr gierig. Durch die Geschwindigkeit wurden die besten Ergebnisse beim Sortieren langer Zeilen erzielt.

Weiter werden wir einige Sortierungen betrachten, die in Standardbibliotheken zu finden sind.

Beginnen wir mit der schnellen aus der Standard-C-Bibliothek (qsort, eine Variante von GCC), über die ich bereits geschrieben habe. Ich kann hier nur hinzufügen, dass diese Sortierung sowie andere C-Sortierungen (z. B. die folgenden aus der BSD-Bibliothek) für die Arbeit mit Objektdaten, insbesondere C ++ - Zeichenfolgen, ungeeignet sind, da es sich bei diesen Daten nicht um POD handelt. Mit der Quelle kann das Problem leicht gelöst werden, indem memcpy-Operationen durch reguläre Zuweisungen ersetzt werden. Möglicherweise stellen Sie auch fest, dass diese Sortierung in einigen Standard-C-Bibliotheken nicht unbedingt schnell ist, sondern durch andere ersetzt werden kann. In der aktuellen Version für GCC hat diese Sortierung sogar die Stabilitätseigenschaft. Es gab manchmal Überraschungen mit den erwähnten c-Sortierungen beim Sammeln von Daten, zum Beispiel, wenn mit dem Typ std :: vector über ein funktionales Objekt gearbeitet wurde, konnten sie Schwierigkeiten verursachen - ich kann empfehlen, sie mit Objektdaten mit Vorsicht zu verwenden. Laut den Läufen ist diese Sortierung manchmal relativ langsam: Sie ist in der Geschwindigkeit anderen Implementierungen der schnellen Sortierung beim Arbeiten mit Zahlen merklich unterlegen, aber beim Arbeiten mit Si-Strings ist es besser, wenn nur das Sortieren mit zwei Kontrollpunkten manchmal voranschreitet.aber in langen Schlangen überholt die Standard-Qsort sie fast immer. Das Interessanteste wurde entdeckt, als ich versuchte, eine Milliarde Ganzzahlen damit zu sortieren - es stellte sich heraus, dass das Ausfüllen von Typ 7 zu einer Zeitabhängigkeit nahe einem quadratischen Gesetz führt, dh zu einer möglichen "Verarbeitung", die bis zu mehreren Jahren dauert (ich habe nicht auf das Ende gewartet und es gestoppt bei 21 Stunden laufen). Mit weniger Daten kann diese Sortierung normalerweise Ankerpunkte auswählen, mit denen sie schnell funktioniert.Mit weniger Daten kann diese Sortierung normalerweise Ankerpunkte auswählen, mit denen sie schnell funktioniert.Mit weniger Daten kann diese Sortierung normalerweise Ankerpunkte auswählen, mit denen sie schnell funktioniert.

Introspektive Sortierung wird in der C ++ - Standardbibliothek verwendet, obwohl die genaue Methode in std :: sort von der Implementierung abhängt, sofern nur Informationen zu GCC bereitgestellt werden. Laut den Läufen ist dies die zweitschnellste nach dem Spread-Sortieren, wenn mit Zahlen gearbeitet wird, und der Vorteil des Spread-Sortierens ist gering (von fast 0 bis 30%), aber beim String-Sortieren ist alles viel schlimmer - es kann 3-4 mal niedriger sein als bei den Führenden . Dies ist eigentlich eine schnelle Sortierung, bei der zwei Sonderfälle berücksichtigt werden: 1) Wenn die Anzahl der Rekursionen zu groß geworden ist, erfolgt die Umstellung auf Sortierung nach Heap. 2) Wenn die Anzahl der zu sortierenden Elemente gering ist, erfolgt das Umschalten auf Sortieren nach Einfügungen.

Stabile Sortierung aus der C ++ - Standardbibliothek ( std :: stabile_sort) hat, wie der Name schon sagt, die Eigenschaft der Stabilität - es behält die relative Reihenfolge zwischen Elementen mit demselben Schlüssel bei. Diese Eigenschaft ist relativ selten notwendig, obwohl ich darüber eher unbegründet schreibe, nur aufgrund meiner eigenen Erfahrung. Es kann zusätzlichen Speicher verwenden, was es schneller macht. Überraschenderweise ist diese Sortierung oft schneller als std :: sort.

In der sehr beliebten Python-Sprache wird standardmäßig Tims Sortierung verwendet . Für Tests habe ich die Version aus dem Github-Repository verwendet. Es zeigt rekordverdächtige gute Ergebnisse bei teilweise geordneten Daten, ist aber im Durchschnitt immer noch merklich langsamer als die führenden Unternehmen. Normalerweise ist seine Geschwindigkeit der Durchschnitt zwischen schneller Sortierung und Shell-Sortierung, obwohl er in den Linien manchmal nahe an den Führenden liegt. Es hat die Eigenschaft der Stabilität. Es implementiert einen relativ komplizierten Algorithmus, in dessen Standardimplementierung 2015 ein Fehler entdeckt wurde, für dessen Manifestation jedoch eine eher unrealistische Situation erforderlich ist.

Die BSD C-Bibliothek verfügt über eine bitweise Sortierung ( radixsort)) und seine stabile Version (sradixsort). Leider können beide Arten nur für C-Strings verwendet werden. Wie aus den Testdaten hervorgeht, ist dies heute der schnellste Weg, um Zeichenfolgen zu sortieren. Daher ist es überraschend, dass es keine Standardoption für C ++ - Zeichenfolgen gibt.

Die BSD - C - Bibliothek hat mehr Sortier merge ( den mergesort) Diese Sortierung ist als eine der schnellsten für Daten mit sequenziellem Zugriff (Dateien, Listen) bekannt und wird wahrscheinlich in der C ++ - Standardbibliothek zum Sortieren von Listen (std :: list und std :: forward_list) verwendet. Sie war übrigens seit 1948 bekannt und einer ihrer Entwickler war ein sehr bekannter Mathematiker und Spezialist für die ersten Computersysteme von Neumann. Von den schnellen Methoden unterscheidet sich diese Sortierung nicht durch die besten Eigenschaften, obwohl sie in der Regel etwas schneller ist als die Shell-Methoden. Es benötigt zusätzlichen Speicher und wird in der Regel nachhaltig implementiert.

Außerdem wird immer noch nach einem Haufen sortiert(Heapsort). Der Heap wird normalerweise für eine optimale Warteschlange mit Prioritäten verwendet, kann aber auch zum Sortieren verwendet werden. Sortierhaufen benötigen keinen zusätzlichen Speicher, verfügen jedoch nicht über die Stabilitätseigenschaft. Die Geschwindigkeit für Zahlen ist erheblich (bis zu 3-6 Mal) langsamer als bei Shell-Methoden, aber bei nicht sehr kurzen Zeilenreihen werden sehr gute Ergebnisse erzielt, da Shell-Methoden überholt werden (mit zunehmender Zeilenlänge wächst der Vorteil).

Die Heap-Sortierung ist auch in der C ++ - Standardbibliothek verfügbar. Eine solche Sortierung erfolgt in zwei Vorgängen: Erstellen des Heaps (std :: make_heap) und anschließendes Sortieren ( std :: sort_heap)) Im Gegensatz zur bsd-Bibliothek ist das Sortieren hier nur eine der Operationen für den Heap. Normalerweise ist diese Sortieroption etwas schneller als die vorherige (die bsd-Option zeigt bessere Ergebnisse nur bei kurzen Zahlen und langen S-Zeilen).

Mit der Standard-C ++ - Bibliothek können Sie den binär ausgeglichenen Baum (std :: multiset) sortieren - füllen Sie einfach den Baum und gehen Sie dann umher. Diese Methode kann als nicht rekursive schnelle Sortierung betrachtet werden. Ein Problem ergibt sich aus der Tatsache, dass der Standardspeicher-Allokator bemerkenswert langsam ist. Um die besten Ergebnisse zu erzielen, müssen Sie Ihren eigenen Allokator verwenden, der um etwa 10 bis 30% schneller wird. Es kann auch angemerkt werden, dass ein solches Verfahren viel zusätzlichen Speicher benötigt, mit g ++ für jedes Datenelement. Zusätzlich dazu müssen Sie 32 Bytes (auf der x86-64-Architektur) speichern - es wäre interessant zu versuchen, einen solchen Baum als Bündel zu speichern, d. H. Ohne zusätzlichen Byte Wenn Sie boost :: container :: multiset verwenden, benötigen Sie weniger Speicher: nur 24 zusätzliche Bytes pro Datenelement. Wie Boost,und die Standardbibliothek zeigte eine unangenehme Überraschung - dabei benötigten sie manchmal mehr Speicher als nötig. Möglicherweise liegt dies am Ausgleich von Binärbäumen. Codes -hier .

Die Boost-Bibliothek verfügt über Spreadort , einen Algorithmus, der im 21. Jahrhundert erfunden wurde. Dies ist die schnellste Gesamtmethode, die heute in bekannten Bibliotheken verfügbar ist. Diese Sortierung verwendet einige bitweise Ideen und kann ebenso wie die Art der Argumente ziemlich launisch sein. Normalerweise zeigt diese Sortierung Rekordergebnisse, die manchmal deutlich besser sind als die der engsten Wettbewerber. Die einzige Ausnahme ist die Sortierung von C-Zeilen, bei der sie den bitweisen Methoden aus der bsd-Bibliothek deutlich unterlegen ist. Beim Sortieren langer C-Linien kann dies anderen Methoden unterlegen sein, z. B. Spin-Sortieren oder schnelles Sortieren mit zwei Ankerpunkten. Die Spread-Sortierung (Boost v1.62) zeigte ein sehr unangenehmes Problem- Beim Sortieren kleiner (bis zu 1000 Elemente) C-String-Arrays funktioniert dies mit Fehlern.

Es gibt auch einen neuen pdqsort- Algorithmus , der, wie vom Autor angegeben, die introspektive Sortierung verbessert. Dieser neue Algorithmus, der auf Wikipedia noch nicht beschrieben ist. Die Ergebnisse - zwar nicht schlecht, aber nicht besonders beeindruckend. Es ist langsamer als std :: sort bei kurzen Ganzzahlen, aber schneller bei Zeichenfolgen und langen Ganzzahlen. In beiden Fällen ist der Unterschied eher unbedeutend. Die besten Ergebnisse für diese Sortierung wurden für lange C ++ - Zeichenfolgen erzielt - hier ist sie der Spread-Sortierung unterlegen, wenn auch nur der führenden.

In Boost finden Sie immer noch Spinsort. Dies ist auch ein neuer Algorithmus, der im Gegensatz zum vorherigen die Stabilitätseigenschaft besitzt und der auch in Wikipedia noch nicht beschrieben ist. Normalerweise ist er dem Anführer nahe, aber mit einer merklichen Verzögerung hinter sich. Es erfordert, wenn auch nicht zu viel, zusätzlichen Speicher. Lassen Sie uns

mit flat_stable_sort aus derselben Boost-Bibliothek enden . Dies ist ein weiterer neuer robuster Algorithmus, der in Wikipedia noch nicht beschrieben ist. Dies ist bei weitem die schnellste Methode, aber den meisten anderen schnellen Bibliotheksmethoden etwas unterlegen. Es benötigt sehr wenig zusätzlichen Speicher (benötigt jedoch immer eine Tabelle mit fester Größe von 8 KB) und ist häufig spürbar schneller als die Shell-Methode.

Betrachten Sie die TabelleZeit (in ms) des Betriebs dieser Algorithmen auf einem Computer mit 8 GB RAM mit einem AMD Phenom ™ II X4 955 @ 3,214 MHz-Prozessor. Der Computer hat insgesamt mehrere Monate gearbeitet, und die Gesamtgröße der gesammelten Daten in zwei mit Tabellen geladenen JSON-Dateien beträgt fast 400 KB. Die Zeitangaben ergeben sich aus dem Durchschnitt der Anzahl der Läufe, bei kleineren Größen waren diese Läufe größer. Wenn Sie ziemlich kompliziert mit dem Cache arbeiten, ändert sich die Geschwindigkeit der Berechnungen, sodass die erzielten Ergebnisse bestenfalls ungefähr sind (ich kann davon ausgehen, dass Timing-Ungenauigkeiten bis zu 20% erreichen können). Ich glaube, dass auf den besten modernen Prozessoren für PCs das Ergebnis 2-3 Mal schneller erzielt werden kann, aber denken Sie daran, dass viel mehr moderne Prozessoren durch Umschalten zwischen verschiedenen Frequenzen und dem mit ihnen erzielten Ergebnis arbeiten.wird noch näher sein.

Diese und die folgende Tabelle sind interaktiv. Zusätzlich zu den absoluten Werten der Timings können Sie auch deren Werte relativ zum Durchschnitt, Median, Minimum und Maximum anzeigen. Sie können die Genauigkeit der Zeichen ändern. Sie können auch Zeitbeziehungen für verschiedene Arten von Füllungen und Datentypen abrufen. Letzteres kann beispielsweise zeigen, dass das Sortieren von C-Strings spürbar schneller ist als das Sortieren von C ++ - Strings. Unter Sortiermethoden können Sie auch eine Vielzahl von Teilmengen auswählen und zusammenstellen. Sie können die Sortierung natürlich nach jeder Spalte festlegen. Leider weiß ich nicht, wie man Javascript in dem Artikel auf dem Hub verwendet, so dass die Tabellen nur als Referenz verfügbar sind. Für den Fall, dass imtqy.com überladen ist, gebe ich auch Backup-Links zur ersten und zweiten Tabelle.

Die Zeit wird in Millisekunden gemessen, aber im Gesetz der Zeitabhängigkeit werden Formeln für Mikrosekunden angegeben, um zu kleine Koeffizienten zu vermeiden. Wenn wir also den Wert für N in der Formel einsetzen , muss das Ergebnis auch durch 1000 geteilt werden, um eine Zahl aus der Tabelle zu erhalten, die der entsprechenden nahe kommt. Das Gesetz der Zeitabhängigkeit wird auf der Grundlage der erhaltenen Zeitpunkte aus einem Vergleich zweier Ergebnisse abgeleitet (normalerweise werden die extremen genommen). Sie können die Qualität des abgeleiteten Gesetzes überprüfen, indem Sie die Option der relativen Abweichung des tatsächlichen Werts von der Ausgabe verwenden.

Einige allgemeine Schlussfolgerungen aus den Ergebnissen dieser Tabelle:

• Die besten Shell-Sortierungen für Daten mit bis zu 10 Millionen Elementen können Timsort und sogar einige schnelle Sortierungen überholen.
• Timsort ist sehr nahe an der Geschwindigkeit qsort (clib), manchmal überholt es etwas und manchmal umgekehrt;
• Heapsort und insbesondere Treesort verlangsamen sich oft merklich, aber vor dem Hintergrund einer Blase oder sogar einer Wahl ist klar, dass dies immer noch schnelle Methoden sind. Interessanterweise haben beide Methoden oft sehr ähnliche Eigenschaften - beide bauen Bäume. Es ist leicht zu bemerken, dass die Abhängigkeiten von Heapsort und TreeSort, obwohl nicht eindeutig quadratisch, offensichtlich nicht N log N sind , sondern viel schlechter - verglichen mit der Shell-Sortierung, die sich mit zunehmendem Datenvolumen viel besser verhält als Heapsort oder TreeSort. dass sie selbst langsamer ist als N log N. Daher stimmen die praktischen Implementierungen von Heap- und Baumsortierungen nicht mit ihren theoretischen Spezifikationen überein.
• Die Daten zum Sortieren von Zeichenfolgen zeigen, dass die Gesetze der Zeitabhängigkeiten hier nicht dieselben sind wie für Zahlen - die Länge der Zeichenfolgen, die hier sortiert werden, überlappen diese Gesetze irgendwie. Leider kenne ich die Formeln für bekannte Sortierungen nicht, die bei der Arbeit mit Zeichenfolgen genaue Gesetze der Zeitabhängigkeiten ergeben würden.
• Es ist interessant, dass die Geschwindigkeit der Arbeit mit reellen Zahlen ungefähr der Geschwindigkeit ganzzahliger Zahlen entspricht. Dies ist eine Folge der Tatsache, dass in der modernen x86-Architektur sehr effektive Optimierungen für die Arbeit mit dem Stapel vorgenommen werden.
• hash_sort zeigte recht mittelmäßige Ergebnisse. Dies ist möglich, da aufgrund der Verwendung von zusätzlichem Speicher die Leistung von Prozessor-Caches stark abnimmt. Bei kleinen zufälligen Daten (weniger als einhunderttausend Elemente) überholt die Hash-Sortierung die besten schnellen Sortierungen. Sie können auch feststellen, dass es aufgrund von Caches wieder möglich ist. Einige der Ergebnisse dieser Sortierung sind sehr seltsam, z. B. werden 10 ⁵ , 10 ⁶ und 10 ⁷ 32-Bit-Ganzzahlen, wenn teilweise geordnete Füllungen verwendet werden, ungefähr gleich sortiert Zeit! Eine Art fast Quanteneffekt. :) Ich bin mir sicher, dass Sie bei der Suche andere schwer zu erklärende Ergebnisse finden können.

Ich werde einige weitere Schlussfolgerungen zu einigen Sonderfällen hinzufügen:

• Einige Arten der Datenauffüllung weisen Schwachstellen in Quicksorts auf. Die Auswahl eines Stützelements auf komplizierte Weise macht die Wahrscheinlichkeit, in eine schlechte Reihenfolge für das Sortieren zu fallen, jedoch praktisch Null. Sie können auch ein Unterstützungselement für jeden Durchgang auf unterschiedliche Weise oder zufällig auswählen. Vielleicht tun sie dies in qsort (clib). Die betrachtete Hoare-Methode arbeitet sehr langsam nur bei speziell entworfenen Sequenzen, die während der praktischen Arbeit zufällig auftreten - dies ist ein Fall mit einer Wahrscheinlichkeit von 2 ^{N -3} / N ^N , dh ein fast absolut unmögliches Ereignis. Wenn wir Sequenzen betrachten, bei denen die Hoar-Methode nicht so langsam wie möglich arbeitet, sondern nur mit einer signifikanten Verlangsamung, dann gibt es viel mehr solcher Fälle, was jedoch die Wahrscheinlichkeit lässt, dass ein unannehmbar langsamer Datenverarbeitungsfall immer noch praktisch unbedeutend ist, obwohl er in seinem Unterschied zu sehr ärgerlich ist Null. Es ist auch fast unmöglich, versehentlich Daten zu erhalten, bei denen eine schnelle Sortierung mit zwei Kontrollpunkten nach dem quadratischen Gesetz langsam funktioniert. Die schnellen Sortieroptionen von Lomuto ohne und ohne Unterstützungselement zeigen in fast allen bestimmten Füllfällen sehr schlechte Ergebnisse.
• In einigen besonderen Fällen liefert die langsamste "Blasensortierung" hervorragende Ergebnisse, und einige der schnellsten und schnellsten Sortierungen sind im Gegenteil sehr schlecht.
• Die Hash-Sortierung zeigte bei Füllungen der Typen 8 und 9 ein sehr schlechtes Ergebnis. Dies liegt daran, dass die monotone Sequenz von aufeinanderfolgenden Werten ausgehend vom kleineren Wert genommen wird und 1% der Zufallszahlen aus dem Bereich vom unteren bis zum maximalen Wert entnommen werden, der alle aufeinanderfolgenden 99% der Daten langweilt in ein Hash-Element. Dieser Fall zeigt sehr gut die Probleme, die auftreten können, wenn diese Sortierung oder Sortierung mit einem Array mit unbekannten Daten verwendet wird.
• Die Auswahlsortierung verhält sich bei allen Arten der Füllung sehr stabil. Die Sortierung von Haufen und Bäumen ist ebenfalls recht stabil, ohne offensichtliche Spitzen und Einbrüche. Dies gilt natürlich sowohl für Shell-Sortierungen als auch für die meisten anderen schnellen Methoden aus Standardbibliotheken.

Jetzt ist es Zeit, über die Datentypen zu sprechen, die mit Sortieralgorithmen verwendet werden:

1. Ganzzahlen 32-Bit-Vorzeichen (int32_t), aber nur nicht negative wurden verwendet. Andere numerische Daten wurden ebenfalls nur nicht negativ aufgenommen - dies verringert nicht die Allgemeinheit der Ergebnisse, erleichtert jedoch das Abrufen für einige Algorithmen erheblich.
2. Ganzzahlen, 64-Bit-Vorzeichen (int64_t);
3. Ganzzahlen, 128-Bit-Vorzeichen (__int128 - wird von mindestens GCC unterstützt);
4. Strukturen von fünf ganzen Zahlen (int32_t), von denen eine als Schlüssel verwendet wird (INT1P4). Beim Sortieren solcher Daten beginnt die Anzahl der Permutationen die Rechenzeit signifikanter zu beeinflussen, daher gewinnen Verfahren mit weniger Permutationen einen gewissen Vorteil;
5. reelle Zahlen wie doppelte Genauigkeit, doppelte (Gleitkommazahlen);
6. kurze Strings C ++ und C. Strings von 1 bis 16 wurden genommen (Strings kurz und C-Strings kurz);
7. Strings C und C ++ mittlerer Länge, deren Länge 1 bis 256 beträgt (Strings und C-Strings);
8. lange Zeilen C und C ++, deren Länge 1 bis 2 ²⁰ beträgt (dies ist etwas mehr als eine Million), und die Zeilen werden so ausgewählt, dass ihre durchschnittliche Länge 512 nicht überschreitet, sodass die Zeilen nur zum zufälligen Füllen ausgewählt wurden, in anderen Fällen wurden die Zeilen einfach genommen Längen von 1 bis 512 (Saiten lang und C-Saiten lang).

Und auch darüber, wie das Quellarray zum Sortieren gefüllt wird:

1. durch Zufall;
2. streng aufsteigend (bestellt);
3. streng absteigend (umgekehrte Reihenfolge, umgekehrt);
4. Zufallswerte im Bereich von 0 bis 99 (kleine Variation, geringe Variation 100);
5. zufällige Folge von 0 und 1 (kleine Variation, geringe Variation 2);
6. Konstante 0 (kleine Streuung, geringe Variation 1);
7. Die Sequenz, die die qsort (Hoare) -Version zur langsamsten Ausführung führt. Es ist merkwürdig, dass es unter allen Sequenzen der Länge N genau 2 ^{N -3} solcher Sequenzen gibt;
8. streng aufsteigend, mit der Einfügung von 1% Zufallszahlen (teilweise geordnet);
9. streng absteigend, mit einer Einfügung von 1% Zufallsvariablen (teilweise umgekehrt).

Es sollte betont werden, dass zufällige Daten der typischste Fall beim Füllen eines Arrays sind. Alle anderen Methoden sind äußerst selten und im normalen Betrieb eines bestimmten Arrays sogar fast unmöglich.

Schauen wir uns die Testergebnisse an, bei denen Sortierungen mit allen möglichen Datensequenzen funktionieren. Die Anzahl solcher Sequenzen entspricht der Fakultät ihrer Länge, daher gibt es für Sequenzen der Länge 12 479'001'600 Varianten - ein guter moderner PC berechnet ihre Anzahl in weniger als einer Minute. Wenn wir Sequenzen der Länge 14 nehmen, erhalten wir bereits 87'178'291'200 Varianten für mehrere Stunden Computerbetrieb. Daher zeigt die folgende Tabelle die durchschnittliche Zeit (in Prozessorzyklen, die durch den RDTSC- Befehl erhalten wurden) einer Sortierung, wenn alle Permutationen bis zu nur 12 sortiert werden. In den Daten werden die vorherigen numerischen Typen und kurzen Zeichenfolgen verwendet. Natürlich könnte man feststellen, dass Sequenzen mit sich wiederholenden Elementen nicht berücksichtigt werden. Ich wage jedoch vorzuschlagen, dass ihre Anwesenheit die Ergebnisse qualitativ nicht verändern würde, aber ihren Empfang erheblich verlangsamen könnte.

Die Ergebnisse für solch kleine Daten sind nicht sehr repräsentativ, insbesondere für komplexe Sortiermethoden, aber sie ergänzen immer noch die Idee des Sortierverhaltens. Soweit ich weiß, ersetzen einige Sorten ihren Hauptalgorithmus durch einen anderen, wenn sie mit kleinen Arrays arbeiten - dies sind verteilte Sorten, schnell mit zwei Ankerpunkten und radix_msd (die letzten beiden verwenden Einfügungen). Einige Sortierungen (flat_stable und radix) verwenden kleine Tabellen. Bei winzigen Datengrößen sind diese Tabellen jedoch viel größer als die Daten selbst, was diese Methoden im Vergleich zu anderen erheblich verlangsamt und zu seltsamen Ergebnissen führt. Seltsame Ergebnisse werden auch mit anderen bitweisen Sortierungen sowie mit Hash- und Array-Sortierungen erzielt. Solche ungewöhnlichen Ergebnisse lassen sich leicht dadurch erklären, dass die Vorbereitungszeit für Daten vor dem Sortieren für diese Methoden für kleine Daten länger ist als die Sortierzeit selbst. Bei der Messung derart kleiner Zeitintervalle (Nanosekunden) ist der Einfluss verschiedener Fehler auf das angezeigte Gesetz natürlich viel höher als in der vorherigen Tabelle. Daher erwiesen sich die Gesetze als sehr ungefähr, oft „mit einer Drift“ zu übertriebenen Werten. Letzteres erklärt sich teilweise aus der Tatsache, dass bei der Arbeit mit kleinen Daten die Sortierzeit selbst mit der Zeit des Aufrufs der Sortierfunktion und mehreren notwendigen Hilfsoperationen zur Zeitmessung vergleichbar wird. Das Programm versucht, den genannten Overhead von der Ausgabe zu subtrahieren, aber es stellt sich heraus, dass dies ziemlich ungefähr erfolgt. Bei alledem wage ich anzunehmen, dass Sie durch den Vergleich der Ergebnisse für verschiedene Datentypen und die Berücksichtigung der gemachten Kommentare manchmal Annahmen treffen können, die nicht sehr weit von der Genauigkeit entfernt sind.

Abschließend eine weitere Tabelle, die zeigt, wie viele verschiedene Testmethoden zum Sortieren von zusätzlichem Speicher erforderlich sind. Dieser Wert hängt natürlich vom System ab. In meinen Tests ist dies, wie ich bereits geschrieben habe, x86-64, GCC. Der Buchstabe T bedeutet die Größe des Typs in Bytes (die Länge der Zeichenfolge ist in dieser Größe nicht enthalten: für C-Zeilen ist es die Größe des Zeigers, für C ++ - Zeilen ist es die Größe des Deskriptors, 32 Bytes für x86-64 GCC), der Buchstabe L ist die Mitte Die Länge des Typs in Bytes (für Zahlen ist dies T und für Zeichenfolgen ist es die durchschnittliche Länge der Zeichenfolge), der Buchstabe A kann 1 oder 0 sein - dies ist die Ausrichtung an der 64-Bit-Grenze, und der Buchstabe M ist die Ausrichtung vom Standardspeicher-Allokator (es wird angenommen) richtet sich nach einer 32-Byte-Grenze). Das Symbol ^* bedeutet, dass die Daten für diese Art der Sortierung nur auf der Grundlage der Analyse des Lesens des VmRSS-Felds aus / proc / PID / status erhalten wurden (das erwähnte Feld ist die Größe des Prozessprogramms).


Es gibt natürlich auch andere Sortiermethoden, sowohl primitive als auch schnelle. Die Boost-Bibliothek verfügt über parallele Algorithmen, mit denen Sie das Vorhandensein zusätzlicher Prozessorkerne im System nutzen können. Sie können auch das selbstordnende Container boost :: container :: flat_multiset anstelle von std :: multiset verwenden, es funktioniert jedoch sehr langsam.

Ich nutze diese Gelegenheit, um einige Kommentare zur Boost-Bibliothek im Allgemeinen abzugeben. Ich empfehle nicht vorbei zu gehen. Sogar die Funktionen, die in der Standardbibliothek in Boost enthalten sind, sind in der Regel besser implementiert und manchmal (wie beispielsweise reguläre Ausdrücke) viel besser. Wenn wir über Container sprechen, sind sie beim Boost merklich größer, und diejenigen, die mit den Standardcontainern übereinstimmen, sind manchmal etwas schneller und haben oft kleine, aber nette Verbesserungen. Boost prüft Typen gründlicher, was manchmal dazu beitragen kann, fast schwer fassbare Fehler zu erkennen, die sich normalerweise nicht manifestieren, aber unter bestimmten Umständen unerwartet aktiviert werden können. Zu den Nachteilen von Boost gehören bedingungslos völlig unlesbare und umfangreiche Nachrichten über Kompilierungsfehler bei vielen Konstruktionen aus dieser Bibliothek - dies gilt jedoch in geringerem Maße für die Standardbibliothek. Es ist Zeit für C ++ - Entwickler, etwas dagegen zu unternehmen.

Alle Dateien mit Tests und einigen anderen verwandten Materialien können aus meinem Repository entnommen werden. Wenn sich jemand für Rohdaten interessiert, können Sie diese hier herunterladen (1,4 MB). Ich freue mich über Kommentare, Kritik und Ergänzungen.