performance natural Quando dovremmo usare Radix sort?




counting sort wiki (9)

Sembra che l'ordinamento di Radix abbia una prestazione media molto buona, cioè O (kN) : http://en.wikipedia.org/wiki/Radix_sort

ma sembra che la maggior parte delle persone stia usando Quick Sort, vero?


Answer #1

L'ordinamento Radix richiede O (k * n) tempo. Ma devi chiedere che cosa è K. K è il "numero di cifre" (un po 'semplicistico ma fondamentalmente qualcosa del genere).

Quindi, quante cifre hai? Abbastanza risposta, più di log (n) (log usando la "dimensione del digit" come base) che rende l'algoritmo Radix O (n log n).

Perché? Se hai meno di log (n) cifre, allora hai meno di n numeri possibili. Quindi puoi semplicemente usare "count sort" che impiega il tempo O (n) (basta contare quanti numeri hai). Quindi presumo tu abbia più di k> log (n) cifre ...

Questo è il motivo per cui le persone non usano così tanto Radix. Anche se ci sono casi in cui è utile utilizzarlo, nella maggior parte dei casi l'ordinamento rapido è molto meglio.


Answer #2

L'ordinamento Radix non è un ordinamento basato su confronto e può solo ordinare tipi numerici come interi (inclusi gli indirizzi puntatori) e virgola mobile, ed è un po 'difficile supportare in modo mobile il punto mobile.

Probabilmente è perché ha una gamma di applicabilità così ristretta che molte librerie standard scelgono di ometterlo. Non può nemmeno permettervi di fornire il vostro comparatore, dal momento che alcune persone potrebbero non voler persino ordinare gli interi direttamente tanto quanto usare gli interi come indici per qualcos'altro da usare come chiave per l'ordinamento, ad esempio gli ordinamenti basati su Confronto consentono a tutti questa flessibilità quindi probabilmente è il caso di preferire una soluzione generalizzata che soddisfi il 99% delle necessità quotidiane delle persone invece di andare fuori dai modi per soddisfare quell'1%.

Detto questo, nonostante la stretta applicabilità, nel mio dominio trovo più uso per i tipi di radix che introsorts o quicksorts. Sono in quell'1% e quasi mai lavoro con, per esempio, chiavi di stringa, ma spesso trovo casi d'uso per numeri che traggono vantaggio dall'essere ordinati. È perché il mio codebase ruota attorno agli indici di entità e componenti (sistema di componenti-entità), nonché cose come le reti indicizzate e c'è un sacco di dati numerici.

Di conseguenza, l'ordinamento digitale diventa utile per tutti i tipi di cose nel mio caso. Un esempio comune nel mio caso è l'eliminazione di indici duplicati. In questo caso non ho davvero bisogno di ordinare i risultati, ma spesso un ordinamento digitale può eliminare i duplicati più velocemente delle alternative.

Un altro è trovare, diciamo, una spaccatura mediana per un albero kd lungo una data dimensione. Lì radix ordinamento dei valori a virgola mobile del punto per una data dimensione mi dà una posizione mediana rapidamente nel tempo lineare per dividere il nodo dell'albero.

Un altro è l'ordinamento in profondità di primitive di livello superiore di z per una trasparenza alfa semipropria se non lo faremo in un frag shader. Ciò vale anche per le GUI e il software di grafica vettoriale per gli elementi z-order.

Un altro è l'accesso sequenziale cache-friendly utilizzando un elenco di indici. Se gli indici vengono attraversati più volte, spesso migliorano le prestazioni se si radix ordinano in anticipo in modo che l'attraversamento venga eseguito in ordine sequenziale anziché in ordine casuale. Quest'ultimo potrebbe zigzag avanti e indietro nella memoria, sfrattando i dati dalle linee della cache solo per ricaricare la stessa regione di memoria ripetutamente all'interno dello stesso ciclo. Quando radix ordina prima gli indici prima di accedervi ripetutamente, ciò cessa di accadere e posso ridurre considerevolmente i caching. Questo è in realtà il mio uso più comune per i tipi di radix ed è la chiave per la mia ECS che è cache-friendly quando i sistemi vogliono accedere a entità con due o più componenti.

Nel mio caso ho un ordinamento digitale multithread che uso abbastanza spesso. Alcuni parametri:

--------------------------------------------
- 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 fare una media di qualcosa come 6-7 ms per ordinare un milione di numeri una volta sul mio hardware dinky che non è veloce come vorrei visto che 6-7 millisecondi possono ancora essere notati dagli utenti a volte in contesti interattivi, ma pur sempre un intero molto meglio di 55-85 ms come nel caso di std::sort di C ++ o di qsort di C che porterebbe sicuramente a singhiozzi molto evidenti nei frame rate. Ho persino sentito parlare di persone che implementano ordinamenti via RADIX usando SIMD, anche se non ho idea di come siano riusciti a farlo. Non sono abbastanza intelligente per trovare una soluzione del genere, anche se il mio ingenuo piccolo tipo di radix funziona piuttosto bene rispetto alle librerie standard.


Answer #3

L'ordinamento di Radix è più difficile da generalizzare rispetto alla maggior parte degli altri algoritmi di ordinamento. Richiede chiavi di dimensioni fisse e un modo standard per rompere le chiavi in ​​pezzi. Quindi non trova mai la sua strada nelle biblioteche.


Answer #4

k = "lunghezza del valore più lungo in Array da ordinare"

n = "lunghezza dell'array"

O (k * n) = "worst case running"

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

quindi quando usi Radix sort assicurati che "il numero intero più lungo sia inferiore alla dimensione dell'array" o viceversa. Quindi batterai Quicksort!

Lo svantaggio è: la maggior parte delle volte non è possibile assicurare quanto diventino i grandi numeri interi, ma se si dispone di un intervallo di numeri fisso, l'ordinamento digitale dovrebbe essere la strada da seguire.


Answer #5

L'ordinamento rapido ha una media di O (N logN), ma ha anche il peggior caso di O (N ^ 2), quindi, anche nella maggior parte dei casi pratici, non si arriva a N ^ 2, c'è sempre il rischio che l'input sarà in "cattivo ordine" per te. Questo rischio non esiste nell'ordinamento digitale. Penso che questo dia un grande vantaggio all'ordinamento digitale.


Answer #6

quando n> 128, dovremmo usare RadixSort

quando ordino int32s, scelgo radix 256, quindi k = log (256, 2 ^ 32) = 4, che è significativamente più piccolo di log (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]来保证原有的顺序不变      
    }
}

Answer #7

A meno che tu non abbia una lista enorme o tasti estremamente piccoli, il log (N) di solito è più piccolo di k, raramente è molto più alto. Pertanto, la scelta di un algoritmo di ordinamento di tipo generale con O (N log N) prestazioni medie del caso non è nettamente peggiore rispetto all'utilizzo di ordinamento digitale.

Correzione : come sottolineato da @Mehrdad nei commenti, l'argomento sopra non è corretto : o la dimensione della chiave è costante, quindi l'ordinamento radix è O (N), o la dimensione della chiave è k, quindi quicksort è O (k N log N). Quindi in teoria, radix sort ha davvero un runtime asintotico migliore.

In pratica, i runtime saranno dominati da termini come:

  • ordinamento digitale: c1 k N

  • quicksort: c2 k N log (N)

dove c1 >> c2, perché "estrarre" i bit da una chiave più lunga è in genere un'operazione costosa che implica spostamenti di bit e operazioni logiche (o almeno un accesso non modificato alla memoria), mentre le CPU moderne possono confrontare le chiavi con 64, 128 o addirittura 256 bit in una sola operazione. Quindi per molti casi comuni, a meno che N non sia gigantesco, c1 sarà più grande di c2 log (N)


Answer #8

Modificato secondo i vostri commenti:

  • Ordinamento Radice si applica solo a numeri interi, stringhe di dimensione fissa, punti mobili ea predicati di confronto "minore di", "maggiore di" o "ordine lessicografico", mentre gli ordinamenti di confronto possono accogliere ordini diversi.
  • k può essere maggiore di log N.
  • L'ordinamento rapido può essere eseguito sul posto, l'ordinamento digitale diventa meno efficiente.

Answer #9

Un esempio potrebbe essere quando si ordina un set molto grande o un array di numeri interi. Un ordinamento di tipo radix e tutti gli altri tipi di distribuzione di tipi sono estremamente veloci poiché gli elementi di dati vengono principalmente accodati in una serie di code (massimo 10 code per un ordinamento digitale LSD) e rimappati in una diversa posizione dell'indice degli stessi dati di input da ordinare. Non ci sono cicli annidati, quindi l'algoritmo tende a comportarsi in modo più lineare in quanto il numero di interi di input di dati da ordinare diventa significativamente maggiore. A differenza di altri metodi di ordinamento, come il metodo bubbleSort estremamente inefficiente, l'ordinamento digitale non implementa le operazioni di confronto per ordinare. È solo un semplice processo di rimappatura degli interi in diverse posizioni di indice fino a quando l'input non viene infine ordinato. Se vuoi testare un ordinamento digitale LSD per te stesso, ne ho scritto uno e memorizzato su github che può essere facilmente testato su un js ide online come la sandbox di codifica javascript eloquente. Sentiti libero di giocarci e guarda come si comporta con diversi numeri di n. Ho testato fino a 900.000 interi non codificati con un runtime <300ms. Ecco il link se desideri giocare con esso.

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





radix-sort