Applicazioni pratiche di Radix Sort

Question

Radix sort è teoricamente molto veloce quando si sa che le chiavi sono in un certo intervallo limitata, ad esempio $ n $ valori nell'intervallo $ [0 \ puntini n ^ k -1] $ per esempio. Se $ k <\ lg n $ basta convertire i valori alla base $ n $ che prende $ \ Theta (n) $ tempo, fare una base di $ n $ radix sort e poi convertire di nuovo alla vostra base originale per $ complessiva \ Theta (nk) $ algoritmo.

Comunque, ho letto che , in pratica, un ordinamento digitale è in genere molto più lento di fare per esempio uno studio randomizzato Quicksort :

Per grandi array, radix ha una sorta di istruzioni il conteggio più basso, ma a causa della sua relativamente scarse prestazioni della cache, la sua complessiva le prestazioni sono peggiori rispetto alle versioni di memoria ottimizzate di mergesort e quicksort.

È radix sort solo una bella algoritmo teorica, o ha usi pratici comuni?

Answer 1

ordinamenti digitali sono spesso, in pratica, il genere più veloci e più utili su macchine parallele.

• Zagha ??e Blelloch: Radix ordinamento per multiprocessori vettoriali. Supercomputing , 1991. 712-721
• Blelloch, Leiserson, Maggs, Plaxton, Smith, e Zagha: un confronto di Ordinamento algoritmi per il Machine Connection CM-2. Simp parallelo Algoritmi e Arco (SPAA-3): 3-16, 1991.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, e Patterson: High le prestazioni di smistamento su reti di stazioni di lavoro. Conf su Mgt di dati , (SIGMOD-1997):. 243-254
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, e Patterson. Ricerca del record di ordinamento: esperienze in sintonia NOW-Sort. ACM Sigmetrics Symp paralleli e distribuiti Strumenti , (SPDT-2): 124-133, 1998.

In ogni nodo del multiprocessore probabilmente fare qualcosa di simile a un Quicksort, ma radix permette di ordinare più nodi di lavorare insieme con meno di sincronizzazione rispetto ai vari tipi ricorsivi.

Ci sono altre situazioni troppo. Se avete bisogno di un ordinamento stabile (una specie in cui ogni volta che due chiavi sono uguali rimangono nello stesso ordine piuttosto che ottenere riorganizzate) allora io non sono a conoscenza di qualsiasi versione di quicksort che sarà di utilizzo. Mergesort è stabile (se implementato correttamente). Il tuo link è la prima volta che io abbia mai sentito nessuno dire che Mergesort potrebbe essere fatto per avere una migliore comportamento della cache di radix sort.

Answer 2

@ Robert: Il link è abbastanza sorprendente (in realtà non riuscivo a trovare la frase citata). La mia esperienza personale è per l'input casuale, radix sort è molto più veloce rispetto alla std::sort() STL, che utilizza una variante di quicksort. Ho usato per fare un algoritmo veloce del 50% sostituendo std::sort() con una instabile radix sort. Io non sono sicuro di quello che è la "versione ottimizzata della memoria" di quicksort, ma dubito che può essere due volte più veloce della versione STL.

questo post del blog Evaluated ordinamento digitale insieme a molti altri algoritmi di ordinamento. In breve, in questa valutazione, std::sort() prende 5,1 secondi per ordinare 50 milioni di numeri interi, mentre sul posto / Radix instabile prende sorta 2.0 sec. radix Stabile sorta dovrebbe essere ancora più veloce.

Radix sort è anche ampiamente utilizzato per l'ordinamento in modo stabile le stringhe. Varianti di ordinamento digitale sono a volte visti per costruire array suffisso, BWT, ecc.

Answer 3

Radix sort è anche un modo naturale per ordinare parole di lunghezza fissa su un alfabeto fisso, ad esempio in Kärkkäinen & Sanders algoritmo ( http: //www.cs.cmu. edu / ~ GuyB / realworld / papersS04 / KaSa03.pdf )