Warum wird Radix Sort nicht öfter verwendet?

Es ist stabil und hat eine zeitliche Komplexität von O (n). Es sollte schneller sein als Algorithmen wie Quicksort und Mergesort, aber ich sehe es kaum jemals benutzt.

Im Gegensatz zur Radix-Sortierung ist die Quicksortierung universell, während die Radix-Sortierung nur für Ganzzahlschlüssel mit fester Länge nützlich ist.

Man muss auch verstehen, dass O (f (n)) wirklich in der Reihenfolge von K * f (n) bedeutet, wobei K eine beliebige Konstante ist. Für die Radix-Sortierung ist dieses K ziemlich groß (mindestens die Reihenfolge der Anzahl der Bits in den sortierten Ganzzahlen), andererseits hat Quicksort eines der niedrigsten K unter allen Sortieralgorithmen und eine durchschnittliche Komplexität von n * log (n). Im realen Szenario ist quicksort daher sehr oft schneller als radix sort.

Die meisten Sortieralgorithmen sind universell einsetzbar. Bei einer gegebenen Vergleichsfunktion arbeiten sie mit allem, und Algorithmen wie Quicksort und Heapsort sortieren mit O (1) zusätzlichen Speicher.

Die Radix-Sortierung ist spezialisierter. Sie benötigen einen bestimmten Schlüssel in lexikografischer Reihenfolge. Sie benötigen einen Eimer für jedes mögliche Symbol im Schlüssel, und die Eimer müssen viele Datensätze enthalten. (Alternativ benötigen Sie eine große Reihe von Buckets, die jeden möglichen Schlüsselwert enthalten.) Sie benötigen wahrscheinlich viel mehr Arbeitsspeicher, um die Radix-Sortierung durchzuführen, und Sie werden ihn zufällig verwenden. Beides ist für moderne Computer nicht gut, da Sie wahrscheinlich Seitenfehler wie Quicksort bekommen, die Cache-Fehler verursachen.

Schließlich schreiben die Leute im Allgemeinen keine eigenen Sortieralgorithmen mehr. Die meisten Sprachen verfügen über Bibliotheksfunktionen zum Sortieren. Normalerweise sollten Sie diese verwenden. Da die Radix-Sortierung nicht universell einsetzbar ist, normalerweise auf die tatsächliche Verwendung zugeschnitten werden muss und viel zusätzlichen Speicher benötigt, ist es schwierig, sie in eine Bibliotheksfunktion oder -vorlage einzufügen.

Es ist ziemlich selten, dass die Schlüssel, nach denen Sie sortieren, tatsächlich ganze Zahlen in einem bekannten, spärlichen Bereich sind. Normalerweise haben Sie alphabetische Felder, die aussehen wie sie nicht vergleichende Sortierung unterstützen würden, aber da die reale Welt Saiten sind nicht gleichmäßig über das Alphabet verteilt, dies nicht funktioniert und es sollte in der Theorie.

In anderen Fällen wird das Kriterium nur operativ definiert (bei zwei Datensätzen können Sie entscheiden, welcher zuerst eintritt, aber Sie können nicht beurteilen, wie weit ein einzelner Datensatz von der Skala entfernt ist). Daher ist die Methode oft nicht anwendbar, weniger anwendbar als Sie vielleicht glauben oder nur nicht schneller als O (n * log (n)).

Ich benutze es die ganze Zeit, eigentlich mehr als vergleichsbasierte Sorten, aber ich bin zugegebenermaßen ein merkwürdiger Typ, der mehr mit Zahlen als mit irgendetwas anderem arbeitet (ich arbeite kaum jemals mit Zeichenfolgen und sie werden in der Regel interniert, wenn ja, zu welchem ​​Zeitpunkt Das Sortieren kann wieder nützlich sein, um Duplikate herauszufiltern und Schnittmengen zu berechnen (lexikografische Vergleiche führe ich praktisch nie durch).

Ein grundlegendes Beispiel ist das Sortieren von Radix-Punkten nach einer bestimmten Dimension als Teil einer Suche oder einer Medianaufteilung oder eine schnelle Methode zum Erkennen von übereinstimmenden Punkten, zum Sortieren von Tiefenfragmenten oder zum Sortieren eines Arrays von Indizes, die in mehreren Schleifen verwendet werden, um einen cachefreundlicheren Zugriff zu ermöglichen Muster (nicht im Speicher hin und her gehen, nur um wieder zurück zu gehen und den gleichen Speicher in eine Cache-Zeile zu laden). Zumindest in meiner Domäne gibt es eine sehr umfangreiche Anwendung (Computergrafik), um nur nach 32-Bit- und 64-Bit-Ziffernschlüsseln mit fester Größe zu sortieren.

Eine Sache, auf die ich eingehen wollte, ist, dass die Radix-Sortierung mit Gleitkommazahlen und Negativen arbeiten kann, obwohl es schwierig ist, eine FP-Version zu schreiben, die so portabel wie möglich ist. Auch wenn es sich um O (n * K) handelt, muss K nur die Anzahl der Bytes der Schlüsselgröße sein (Beispiel: Eine Million 32-Bit-Ganzzahlen würde im Allgemeinen 4-Byte-Durchgänge benötigen, wenn sich 2 ^ 8 Einträge im Bucket befinden ). Das Speicherzugriffsmuster ist in der Regel auch wesentlich cachefreundlicher als QuickSorts, obwohl es in der Regel ein paralleles Array und ein kleines Bucket-Array benötigt (das zweite Array passt normalerweise gut in den Stapel). QS führt möglicherweise 50 Millionen Swaps durch, um ein Array von einer Million Ganzzahlen mit sporadischen Direktzugriffsmustern zu sortieren. Die Radix-Sortierung kann dies in 4 linearen, Cache-freundlichen Übergängen über die Daten tun.

Das Fehlen eines Bewusstseins, dies mit einem kleinen K bei negativen Zahlen zusammen mit Gleitkommazahlen zu tun, könnte jedoch sehr wohl erheblich zur mangelnden Beliebtheit von Radix-Sorten beitragen.

Was meine Meinung darüber betrifft, warum Leute es nicht häufiger verwenden, kann es sein, dass viele Domains im Allgemeinen keine Nummern sortieren oder als Suchschlüssel verwenden müssen. Aufgrund meiner persönlichen Erfahrung haben viele meiner ehemaligen Kollegen es jedoch auch nicht in Fällen verwendet, in denen es perfekt geeignet war, und teilweise, weil sie nicht wussten, dass es für die Bearbeitung von FPs und Negativen geeignet ist. Abgesehen davon, dass es nur mit numerischen Typen funktioniert, wird es oft als noch weniger allgemein anwendbar angesehen, als es tatsächlich ist. Ich würde es auch nicht annähernd so oft gebrauchen, wenn ich denken würde, dass es bei Gleitkommazahlen und negativen ganzen Zahlen nicht funktioniert.

Einige Benchmarks:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

Und das ist nur mit meiner naiven Implementierung ( mt_sort_intist auch eine Radix-Sortierung, aber mit einem schnelleren Code-Zweig, vorausgesetzt, er kann annehmen, dass der Schlüssel eine Ganzzahl ist). Stellen Sie sich vor, wie schnell eine von Experten geschriebene Standardimplementierung sein könnte.

Der einzige Fall , in dem ich den Radixsort gefunden schlechter als C ++ ergehen s wirklich schnell Vergleich Basis std::sortfür eine wirklich kleine Anzahl von Elementen war, 32 sagt, an welcher Stelle ich glaube , std::sortbeginnen Sorten besser geeignet für die kleinste Anzahl von Elementen wie heapsorts mit oder Einfügung sortiert, obwohl zu diesem Zeitpunkt meine Implementierung nur verwendet std::sort.

Ein weiterer Grund: Heutzutage wird das Sortieren normalerweise mit einer vom Benutzer bereitgestellten Sortierroutine implementiert, die an die vom Compiler bereitgestellte Sortierlogik angehängt ist. Bei einer Radix-Sortierung wäre dies erheblich komplexer und wird noch schlimmer, wenn die Sortierroutine auf mehrere Schlüssel variabler Länge angewendet wird. (Sagen Sie, Name und Geburtsdatum.)

In der realen Welt habe ich tatsächlich einmal eine Radix-Sortierung implementiert. Dies war in den alten Zeiten, als der Speicher begrenzt war, ich konnte nicht alle meine Daten auf einmal in den Speicher bringen. Dies bedeutete, dass die Anzahl der Datenzugriffe weitaus wichtiger war als O (n) gegenüber O (n log n). Ich habe die Daten einmal durchlaufen, um jeden Datensatz einer Ablage zuzuordnen (anhand einer Liste, welche Datensätze sich in welchen Ablagen befanden, ohne tatsächlich etwas zu verschieben). Für jede nicht leere Ablage (mein Sortierschlüssel war Text) würde es eine Menge geben leere Fächer) Ich habe geprüft, ob ich die Daten tatsächlich in den Speicher bringen kann - wenn ja, bringen Sie sie ein und verwenden Sie quicksort. Wenn nicht, erstellen Sie eine temporäre Datei, die nur die Elemente in der Bin enthält, und rufen Sie die Routine rekursiv auf. (In der Praxis würden nur wenige Fächer überlaufen.) Dies führte zu zwei vollständigen Lesevorgängen und einem vollständigen Schreibvorgang im Netzwerkspeicher und etwa 10% davon im lokalen Speicher.

Heutzutage sind solche Big-Data-Probleme weitaus schwerer zu lösen, so etwas werde ich wahrscheinlich nie wieder schreiben. (Wenn ich heutzutage mit denselben Daten konfrontiert wäre, würde ich einfach das 64-Bit-Betriebssystem angeben und RAM hinzufügen, wenn Sie in diesem Editor Probleme bekommen.)

Wenn alle Ihre Parameter Ganzzahlen sind und Sie über 1024 Eingabeparameter verfügen, ist die Radix-Sortierung immer schneller.

Warum?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

So ist die Radix-Sortierung schneller, wenn

log(n)> max num of digits

Die maximale Ganzzahl in Java ist 2147483647. Dies ist eine 10-stellige Zahl

So ist die Radix-Sortierung immer schneller, wenn

log(n)> 10

Daher ist die Radix-Sortierung immer schneller, wenn n>1024