Praktische Anwendungen der Radix-Sortierung

Question

Die Radix-Sortierung ist theoretisch sehr schnell, wenn Sie wissen, dass die Schlüssel in einem bestimmten begrenzten Bereich liegen, beispielsweise $n$-Werte im Bereich $[0\dots n^k -1]$.Wenn $k<\lg n$, wandeln Sie die Werte einfach in die Basis $n$ um, was $ heta(n)$ Zeit in Anspruch nimmt, führen Sie eine Basis-$n$-Radix-Sortierung durch und konvertieren Sie sie dann zurück in Ihre ursprüngliche Basis für einen Gesamtwert von $\ Theta(nk)$-Algorithmus.

Allerdings habe ich das gelesen In der Praxis ist die Basissortierung typischerweise viel langsamer als beispielsweise eine zufällige Schnellsortierung:

Für große Arrays hat die Radix -Sortierung die niedrigste Anweisungsanzahl, aber aufgrund seiner relativ schlechten Cache -Leistung ist die Gesamtleistung schlechter als die maßstab optimierten Versionen von Mergesort und Quicksort.

Ist die Radix-Sortierung nur ein netter theoretischer Algorithmus oder hat sie allgemeine praktische Anwendungen?

Answer 1

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

• Zagha ​​und Blelloch:Radix-Sortierung für Vektor-Multiprozessoren. Supercomputing, 1991: 712-721.
• Blelloch, Leiserson, Maggs, Plaxton, Smith und Zagha:Ein Vergleich der Sortieralgorithmen für die Verbindungsmaschine CM-2. Symp Parallele Algorithmen und Arch (SPAA-3):3-16, 1991.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein und Patterson:Hochleistungssortierung in Netzwerken von Arbeitsplätzen. Conf on Mgt of Data, (SIGMOD-1997):243-254.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein und Patterson.Suche nach dem Sortierdatensatz:Erfahrungen im Tuning NOW-Sort. ACM Sigmametrics Symp Parallele und verteilte Tools, (SPDT-2):124-133, 1998.

Auf jedem Knoten des Multiprozessors führen Sie wahrscheinlich so etwas wie eine Quicksortierung durch, aber die Basissortierung ermöglicht die Zusammenarbeit mehrerer Knoten mit weniger Synchronisierung als die verschiedenen rekursiven Sortierungen.

Es gibt auch andere Situationen.Wenn Sie eine benötigen stabile Sorte (eine Sortierung, bei der zwei Schlüssel, wenn sie gleich sind, in derselben Reihenfolge bleiben und nicht neu angeordnet werden), dann ist mir keine Version von Quicksort bekannt, die von Nutzen sein könnte.Mergesort ist ebenfalls stabil (bei korrekter Implementierung).Ihr Link ist das erste Mal, dass ich jemals jemanden sagen höre, dass Mergesort so gestaltet werden könnte, dass es ein besseres Cache-Verhalten als Radix-Sortierung aufweist.

Answer 2

@Robert: Ihr Link ist ziemlich überraschend (tatsächlich konnte ich den zitierten Satz nicht finden). Meine persönliche Erfahrung ist für zufällige Eingaben, Radix -Sortierung ist viel schneller als die STL std::sort(), der eine Variante von Quicksort verwendet. Ich habe einen Algorithmus 50% schneller durch Ersetzen gemacht std::sort() mit einer instabilen Radix -Sortierung. Ich bin mir nicht sicher, was die "Speicheroptimierte Version" von Quicksort ist, aber ich bezweifle, dass es doppelt so schnell sein kann wie die STL -Version.

Dieser Blog -Beitrag bewertete die Radix -Sortierung zusammen mit mehreren anderen Sortieralgorithmen. Kurz gesagt, in dieser Bewertung, std::sort() Dauert 5,1 Sekunden, um 50 Millionen Ganzzahlen zu sortieren, während die Innen-/instabile Radix-Sortierung 2,0 Sekunden dauert. Die stabile Radix -Sortierung sollte noch schneller sein.

Die Radix -Sortierung wird auch häufig zum stabilen Sortieren von Zeichenfolgen verwendet. Varianten der Radix -Sortierung sind manchmal zum Bau von Suffix -Arrays, BWT usw. zu sehen.

Answer 3

Die Radix-Sortierung ist auch eine natürliche Möglichkeit, Wörter mit fester Länge über ein festes Alphabet zu sortieren, z.http://www.cs.cmu.edu/~guyb/realworld/papers04/kasa03.pdf)