Praktische Anwendungen von Radix Sort

20

Die Radix-Sortierung ist theoretisch sehr schnell, wenn Sie wissen, dass sich die Tasten in einem bestimmten begrenzten Bereich befinden, z. B. Werte im Bereich [ 0 … n k - 1 ] . Wenn k < lg n Sie nur die Werte zu Base umwandeln n , die nimmt Θ ( n ) Zeit, führen Sie eine Basis n Art radix und dann konvertiert für eine Gesamt zu Ihrer ursprünglichen Basis zurück Θ ( n k ) Algorithmus.n[0…nk-1]k<lg⁡nnΘ(n)nΘ(nk)

Ich habe jedoch gelesen, dass die Radix-Sortierung in der Praxis in der Regel viel langsamer ist als beispielsweise eine zufällige Quicksortierung :

Bei großen Arrays weist radix sort die niedrigste Befehlsanzahl auf. Aufgrund der relativ schlechten Cache-Leistung ist die Gesamtleistung jedoch schlechter als bei den speicheroptimierten Versionen von Mergesort und Quicksort.

Ist radix sort nur ein guter theoretischer Algorithmus oder hat er allgemeine praktische Anwendungen?

algorithms sorting applied-theory radix-sort Robert S. Barnes
quelle

Antworten:

15

Radix-Sortierungen sind in der Praxis häufig die schnellsten und nützlichsten Sortierungen auf Parallelmaschinen.

Auf jedem Knoten des Multiprozessors führen Sie wahrscheinlich so etwas wie eine Quicksortierung durch, aber die Radix-Sortierung ermöglicht, dass mehrere Knoten mit weniger Synchronisation zusammenarbeiten als die verschiedenen rekursiven Sortierungen.

Es gibt auch andere Situationen. Wenn Sie eine stabile Sortierung benötigen (eine Sortierung, bei der zwei Schlüssel, wenn sie gleich sind, in derselben Reihenfolge bleiben, anstatt neu angeordnet zu werden), sind mir keine verwendbaren QuickSort-Versionen bekannt. Mergesort ist auch stabil (wenn es richtig implementiert ist). Ihr Link ist das erste Mal, dass ich jemanden sagen hörte, dass Mergesort ein besseres Cache-Verhalten aufweisen könnte als Radix-Sortierung.

Wandering Logic
quelle
Patterson und Hennessy weisen in ihrem Buch Computer Organization and Design auf das oben verlinkte Papier von Lamarca hin.
Robert S. Barnes
Ihre Erwähnung von Patterson hat mich an die wichtige Arbeit erinnert, die Andrea Arpaci-Dusseau vor etwa 15 Jahren beim Sortieren von Clustern geleistet hat. (Patterson war Mitautor). In der Veröffentlichung von 1997 entschieden sie tatsächlich, dass eine partielle Radix-Sortierung der Quicksortierung auch auf den einzelnen Knoten vorzuziehen ist. (Ich habe die Verweise auf die Antwort hinzugefügt).
Wandering Logic
Das ist interessant. In der vierten Ausgabe von CompOrg 2009 wird darauf verwiesen, dass Lamarcas Arbeiten zu früheren Versionen von Radix Sort unfreundlich im Cache sind (S. 489). In den Diagrammen, in denen Quicksort und Radix Sort verglichen werden, heißt es auf Seite 490: "Aufgrund dieser Ergebnisse werden neue Versionen von Radix-Sorten wurden erfunden, die die Speicherhierarchie berücksichtigen, um ihre algorithmischen Vorteile wiederzuerlangen. " Ich bin gespannt, wie diese neuen Versionen von Radix Sort funktionieren.
Robert S. Barnes
Mein Verdacht ist, dass Lamarca nur eine dumme Radix-Sorte verwendet hat (eine, die ihre Eimer als verknüpfte Listen aufbewahrt). Niemand würde das jemals tun. Sie würden die Buckets mit einem optimierten dynamischen Array (z. B. einem C ++ vector) implementieren . Aber ich weiß es nicht, da ich Lamarcas Papiere nicht gelesen habe.
Wandering Logic
@WanderingLogic Wo verwendet Radix Sort Eimer? Meinen Sie hier Eimersortierung?
Bar
3

@Robert: Dein Link ist ziemlich überraschend (eigentlich konnte ich den zitierten Satz nicht finden). Meine persönliche Erfahrung ist für die zufällige Eingabe, Radix-Sortierung ist viel schneller als die STL std::sort(), die eine Variante von Quicksort verwendet. Früher habe ich einen Algorithmus 50% schneller gemacht, indem ich ihn durch std::sort()eine instabile Radix-Sortierung ersetzt habe. Ich bin nicht sicher, was die "speicheroptimierte Version" von QuickSort ist, aber ich bezweifle, dass sie doppelt so schnell sein kann wie die STL-Version.

In diesem Blog-Beitrag wurde die Radix-Sortierung zusammen mit mehreren anderen Sortieralgorithmen bewertet. Kurz gesagt, std::sort()dauert es in dieser Auswertung 5,1 Sekunden, um 50 Millionen Ganzzahlen zu sortieren, während die direkte / instabile Radix-Sortierung 2,0 Sekunden dauert. Stabile Radix-Sortierung sollte noch schneller sein.

Radix-Sortierung wird auch häufig zum stabilen Sortieren von Zeichenfolgen verwendet. Zuweilen werden Varianten der Radix-Sortierung zum Erstellen von Suffix-Arrays, BWT usw. gesehen.

user172818
quelle