Warum wird Radix Sort nicht öfter verwendet?

31

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.

Queequeg
quelle
2
Siehe hier: en.wikipedia.org/wiki/Radix_sort#Efficiency Die Effizienz ist O (kn) und sie ist möglicherweise nicht besser als O (n * log (n)).
FrustratedWithFormsDesigner
2
Die Radix-Sortierung wird häufig in Soft-Echtzeitsystemen wie Spielen verwendet. Ob ein Algorithmus einen anderen übertrifft oder nicht, hängt wie üblich von allen Parametern des Problems ab, nicht nur von der damit verbundenen Komplexität
awdz9nld
@FrustratedWithFormsDesigner Vielleicht hat sich das Wiki geändert? Ich sehe den Verweis auf `n log (n) nicht mehr, FWIW ...
Rogerdpack
Boost hat eine (in place-Variante) davon: boost.org/doc/libs/1_62_0/libs/sort/doc/html/sort/sort_hpp.html aber ich denke, die Leute wissen einfach nicht, dass es existiert ... Entweder das oder sie alle verwenden nur den "Standard" -Sortieralgorithmus. Aus welchen Gründen auch immer verwenden Framework-Ersteller die "generischen" Sortierungen, die nicht so effizient sind, immer wieder. Vielleicht konzentrieren sie sich nicht auf das Sortieren von Ints in der Regel, da es ein seltener Anwendungsfall ist?
Rogerdpack

Antworten:

38

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.

vartec
quelle
Hinweis zur angegebenen Komplexität: Obwohl die (LSD) -Radix-Sortierung eine Komplexität von O (n * K) aufweist, ist diese Konstante normalerweise klein und wird typischerweise so gewählt, dass (2 ^ (W / K)) * C in L1 passt, wobei C ist die Größe des Zählers in Bytes, W die Größe des zu sortierenden Schlüssels. Die meisten Implementierungen wählen K = [3,4] für 32-Bit-Wörter auf x86. K kann auch adaptiv gemacht werden, um die zeitliche Kohärenz (Nah-Sortiertheit) auszunutzen, da jede Basis einzeln sortiert wird.
Awdz9nld
11
Hinweis zur Universalität: Radix-Sortierung kann sowohl mit Gleitkomma-Schlüsseln als auch mit Integer-Schlüsseln variabler Länge ausgeführt werden
awdz9nld
20

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.

David Thornley
quelle
Tatsächlich benötigt QuickSort O(n^2)aufgrund von nrekursiven Aufrufen auf der linken und rechten Partition im schlimmsten Fall Speicherplatz . Wenn die Implementierung die Schwanzrekursionsoptimierung verwendet, kann dies auf den Wert gesenkt werden, O(n)da die Aufrufe der richtigen Partition keinen zusätzlichen Speicherplatz erfordern. ( en.wikipedia.org/wiki/Quicksort#Space_complexity )
Splinter of Chaos
Sie brauchen nur S(n) \in O(n)Platz zum Sortieren mit radix, also genauso wie beim Heap- oder Schnellsortieren.
Velda
@SplinterofChaos hat sich das Wiki vielleicht geändert? Es scheint nicht n^2mehr für Quicksort zu erwähnen , aber O(log n)...
Rogerdpack
Ich denke nicht, dass es "viel" mehr Speicher ist, vielleicht 2 * n (OK, das ist viel mehr, aber vielleicht nicht unmöglich)? Und die Buckets sind so klein (vorausgesetzt, Sie teilen sich Bytes und rekursiven), dass es gut in den Cache passen könnte?
Rogerdpack
5

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)).

Kilian Foth
quelle
Radix-Sortierung kann ganze Zahlen (oder Zeichenfolgen) in einem beliebigen Bereich verarbeiten, indem sie "byteweise" rekursiv sortiert werden, damit sie nicht in einem geringen Bereich liegen müssen. FWIW ...
rogerdpack
4

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.


quelle
1
Immer schön, die Meinungen von Menschen mit Erfahrung in der Region zu hören.
Frank Hileman
Es scheint, dass mt_ Multi-Thread-Implementierungen sind: softwareengineering.stackexchange.com/a/362097/65606
rogerdpack
1

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.)

Loren Pechtel
quelle
In Anbetracht eines der Nachteile, die manchmal bei der Radix-Sortierung erwähnt werden, ist faszinierend, dass "mehr Platz benötigt". Ich versuche immer noch, meinen Kopf darum zu wickeln ...
Rogerdpack
1
@rogerdpack Es war nicht so, dass mein Ansatz weniger Speicherplatz beanspruchte, sondern dass er weniger Zugriff auf die Daten benötigte. Ich sortierte eine Datei, die etwa ein Gigabyte groß war, während ich mit einem Compiler-Limit (dies war DOS-geschützter Modus, nicht Windows) von etwas weniger als 16 MB Gesamtspeicher einschließlich Code und einem Strukturlimit von 64 KB zu tun hatte.
Loren Pechtel,
-1

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

developer747
quelle
Es gibt versteckte Konstanten in den Implementierungsdetails, aber im Grunde sagen Sie "für größere Eingaben ist das Sortieren schneller", was ... der Fall sein sollte! Es ist nur schwer, Anwendungsfälle dafür zu finden, aber wenn Sie können ...
Rogerdpack