Quando dovremmo usare Radix sorta?

StackOverflow https://stackoverflow.com/questions/4146843

Domanda

Sembra Radix ha una sorta di una prestazione molto buona media caso, vale a dire O (kN) : http://en.wikipedia.org/wiki/Radix_sort

ma sembra la maggior parte delle persone ancora utilizzano rapida Ordina, non è vero?

È stato utile?

Soluzione

Breve ha sorta una media di O (N log N), ma ha anche un caso peggiore di O (N ^ 2), quindi, anche a causa nella maggior parte dei casi pratici non ci vorrà arrivare a N ^ 2, c'è sempre il rischio che l'ingresso sarà in "cattivo ordine" per voi. Questo rischio non esiste in radix sort. Credo che questo dà un grande vantaggio per radix sort.

Altri suggerimenti

Radix sort è più difficile generalizzare maggior parte degli altri algoritmi di ordinamento. Richiede fissato chiavi dimensioni, e alcuni modo standard di rompere le chiavi in ??pezzi. Così non trova la sua strada in librerie.

A cura secondo i vostri commenti:

  • Radix applica solo alle liste interi, stringhe dimensione fissa, virgola mobile e "inferiore", "superiore" o "predicati confronto ordine lessicografico", mentre i tipi di confronto possono ospitare diversi ordini.
  • k può essere maggiore di log N.
  • Breve specie può essere fatto sul posto, radix diventa specie meno efficiente.

Le altre risposte qui sono orribili, non danno esempi di quando radix sort è effettivamente utilizzato .

Un esempio è quando si crea un "matrice suffisso" utilizzando l'algoritmo DC3 skew (Kärkkäinen-Sanders-Burkhardt). L'algoritmo è lineare solo tempo se l'algoritmo di ordinamento è lineare-tempo, e un ordinamento digitale è necessaria e utile qui perché le chiavi sono brevi da costruzione (3-tuple di interi).

A meno che non si dispone di una enorme o estremamente piccole chiavi, log (N) è di solito più piccolo di k, raramente è molto più alto. Quindi, la scelta di un generico algoritmo di ordinamento con O (N log N) performance media caso non è neccesarily peggio che usare radix sort.

Correzione : Come @Mehrdad sottolineato nei commenti, l'argomento di cui sopra non è sana: o la dimensione della chiave è costante, allora ordinamento digitale è O (N), o la dimensione della chiave è k, allora quicksort è O (k log N N). Quindi, in teoria, radix ha una sorta veramente runtime meglio asintotica.

In pratica, i tempi di esecuzione sarà dominato da termini come:

  • ordinamento digitale: c1 k N

  • quicksort: c2 log k N (N)

dove c1 c2 >>, perché "estrazione" bit su una chiave è più solitamente dispendioso e causa di scorrimenti di bit e operazioni logiche (o almeno non allineato Access Memory), mentre le CPU moderni possono confrontare le chiavi con 64, 128 o anche 256 bit in una sola operazione. Così, per molti casi comuni, a meno che N è gigantesco, c1 sarà più grande di log c2 (N)

Radix sort richiede tempo O (n * k). Ma si deve chiedere che cosa è K. K è il "numero di cifre" (un po 'semplicistico, ma in fondo qualcosa di simile).

Quindi, quante cifre hai? Piuttosto risposta, più di log (n) (log utilizzando la "dimensione cifra" come base) che rende il Radix algoritmo O (n log n).

Perché? Se hai meno di log (n) cifre, quindi si hanno meno di n numeri possibili. Quindi si può semplicemente utilizzare "contare sort" che prende O (n) (basta contare il numero di ogni numero che avete). Quindi presumo si ha più di k> log (n) le cifre ...

Questo è il motivo per cui la gente non usa Radix sorta più di tanto. Anche se ci sono casi in cui vale la pena di usarlo, nella maggior parte dei casi rapida specie è molto meglio.

quando n> 128, dovremmo usare radix sort

quando int32s sort, scelgo radice 256, così k = log (256, 2 ^ 32) = 4, che è significativo minore di registro (2, n)

e nel mio test, radix sort è 7 volte più veloce di quicksort nel migliore dei casi. 

public class RadixSort {
    private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
    private final int bar[]=new int[radix];
    private int s[] = new int[65536];//不使用额外的数组t，提高cpu的cache命中率

    public void ensureSort(int len){
        if(s.length < len)
            s = new int[len];
    }   

    public void sort(int[] a){
        int n=a.length;
        ensureSort(n);
        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
        for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素，在bar中找到下标x=bar[slot]-1, 另s[x]=a[i]（同时--bar[slot]将下标前移，供桶内其它元素使用）

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
        for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数，比正数小
        bar[0] += bar[255];
        for(int i=1;i<128;i++)bar[i]+=bar[i-1];     
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变      
    }
}

k = "lunghezza del valore più lungo Array da smistare"

n = "lunghezza della matrice"

O (k * n) = "caso peggiore in esecuzione"

k * n = n ^ 2 (se k = n)

così quando si utilizza Radix sort verificare che "il numero intero più lungo è inferiore alla dimensione dell'array" o viceversa. Poi si va a battere Quicksort!

Lo svantaggio è:. Il più delle volte non si può garantire come numeri interi grandi diventano, ma se si dispone di una gamma fissa di numeri radix sort dovrebbe essere la strada da percorrere

Ecco un link che confronta il Quicksort e radix sort:

Is radix sort più veloce di quicksort per intero array? (sì, è, 2-3x)

Ecco un altro link che analizza tempi di esecuzione dei diversi algoritmi:

Una questione di sorta :

che è più veloce sugli stessi dati; un O (n) o un tipo O (nCollegatevi (n)) tipo?

Risposta: Dipende. Dipende dalla quantità di dati da ordinare. Essa dipende dall'hardware suo essere eseguito su, e dipende dalla implementazione degli algoritmi.

Radix ordinamento non è un confronto basato ordinamento e può soltanto tipi sorta numerici come gli interi (compresi indirizzi di puntatore) e in virgola mobile, e che è un po 'difficile supporto portabile virgola mobile.

E 'probabilmente perché ha una gamma così ristretta di applicabilità che molte librerie standard scelgono di ometterlo. Non può nemmeno consentono di fornire il proprio confronto, dal momento che alcune persone potrebbero non voler interi ordinamento anche direttamente così tanto come con i numeri interi come indici a qualcos'altro da utilizzare come chiave per l'ordinamento, ad esempio, sorta di confronto a base di consentire a tutti che la flessibilità quindi è probabilmente un caso di solo preferendo una soluzione generalizzata raccordo 99% dei bisogni quotidiani della gente invece di andare fuori strada per soddisfare che l'1%.

Detto questo, nonostante l'applicabilità stretto, nel mio dominio trovo più bisogno di ordinamenti digitali di introsorts o quicksorts. Sono in quel 1% e appena mai il lavoro con, diciamo, chiavi stringa, ma spesso trovo casi d'uso per i numeri che beneficiano da ordinare. E 'perché i miei ruota intorno codebase indici a enti e componenti di sistema (entità-componente), così come le cose come maglie indicizzati e c'è un sacco di dati numerici.

Come risultato, radix diventa sorta utile per tutti i tipi di cose nel mio caso. Un esempio comune nel mio caso è eliminare gli indici duplicati. In quel caso non ho davvero bisogno dei risultati per essere ordinati, ma spesso una radice tipo possono eliminare i duplicati più veloce rispetto alle alternative.

Un altro è trovare, per esempio, una spaccatura mediana per un kd-albero lungo una data dimensione. Ci ordinamento digitale i valori a virgola mobile del punto per una data dimensione mi dà rapidamente una posizione mediana in tempo lineare per dividere il nodo della struttura.

Un altro è la profondità ordinamento primitive di livello più alto da z per semi-corretta trasparenza alfa, se non stiamo andando da farlo in uno shader Frag. Ciò vale anche per le GUI e grafica vettoriale software ad elementi z-order.

Un altro è la cache-friendly accesso sequenziale utilizzando una lista di indici. Se gli indici sono attraversati molte volte, spesso migliora le prestazioni se li ordinamento digitale in anticipo in modo che l'attraversamento avviene in ordine sequenziale anziché ordine casuale. Quest'ultima potrebbe zig-zag avanti e indietro nella memoria, sfrattando dati da linee di cache solo per ricaricare la stessa regione di memoria più volte all'interno dello stesso ciclo. Quando sono ordinamento digitale indici primo prima di accedere ripetutamente, che cessa di accadere e che possono ridurre notevolmente cache miss. Questo è in realtà il mio uso più comune per ordinamento digitale ed è la chiave della mia ECS essendo la cache da usare quando i sistemi vogliono entità di accesso con due o più componenti.

Nel mio caso ho un multithread radix sort che io uso molto spesso. Alcuni parametri di riferimento: 

--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...

mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

posso qualcosa di media come 6-7 ms per ordinare un milione di numeri una volta sul mio hardware Dinky che non è così veloce come vorrei dal 6-7 millisecondi possono ancora essere notati dagli utenti a volte in contesti interattivi, ma ancora molto meglio di 55-85 ms come con il caso di std::sort C ++ s 'o qsort di C che sicuramente portare a molto evidenti singhiozzo in frame rate. Ho anche sentito parlare di persone di attuazione ordinamenti digitali utilizzando SIMD, anche se non ho idea di come sono riusciti così. Sono abbastanza non è intelligente a venire con una soluzione del genere, sebbene anche la mia piccola radix ingenuo sorta non abbastanza bene rispetto alle librerie standard.

Un esempio potrebbe essere quando si ordina un grande insieme o array di interi. Un ordinamento digitale ed eventuali altri tipi di distribuzione tipi sono estremamente veloce in quanto elementi di dati sono principalmente essendo accodati in una matrice di code (max 10 code per un LSD ordinamento digitale) e rimappate ad una diversa posizione di indice degli stessi dati di ingresso da ordinare. Non ci sono cicli annidati in modo l'algoritmo tende a comportarsi in modo più lineare, come il numero di interi immettere i dati da ordinare diventa significativamente più grande. A differenza di altri metodi di ordinamento, come il metodo bubblesort estremamente inefficiente, l'ordinamento digitale non implementa le operazioni di confronto di ordinamento. Il suo solo un semplice processo di rimappatura interi a diverse posizioni di indice finché l'ingresso è finalmente ordinato. Se si desidera testare una radice LSD sorta di persona, ho scritto uno fuori e memorizzati su GitHub, che può essere facilmente testato su un JS in linea IDE come sandbox codifica di javascript eloquenti. Sentitevi liberi di giocare con essa e vedere come si comporta con differenti numeri di n. Ho provato con un massimo di 900.000 interi non ordinati con un runtime <300ms. Ecco il link se volete giocare con essa.

https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top