Perché l'ordinamento digitale non viene usato più spesso?

Diversamente dall'ordinamento digitale, quicksort è universale, mentre l'ordinamento digitale è utile solo per le chiavi intere di lunghezza fissa.

Devi anche capire che O (f (n)) in realtà significa in K * f (n), dove K è una costante arbitraria. Per l'ordinamento digitale questo K sembra essere abbastanza grande (almeno l'ordine di numero di bit negli interi ordinati), d'altra parte quicksort ha uno dei K più bassi tra tutti gli algoritmi di ordinamento e la complessità media di n * log (n). Pertanto, nella vita reale, quicksort sarà molto più veloce di radix sort.

La maggior parte degli algoritmi di ordinamento è generale. Data una funzione di confronto, funzionano su qualsiasi cosa e algoritmi come Quicksort e Heapsort ordineranno con O (1) memoria extra.

L'ordinamento digitale è più specializzato. Hai bisogno di una chiave specifica che sia in ordine lessicografico. Hai bisogno di un secchio per ogni simbolo possibile nella chiave, e le benne devono contenere molti record. (In alternativa, è necessaria una grande serie di bucket che manterrà tutti i possibili valori chiave.) È probabile che sia necessaria molta più memoria per fare l'ordinamento digitale, e lo si utilizzerà in modo casuale. Nulla di ciò è positivo per i computer moderni, dal momento che è probabile che si verifichino errori di pagina come Quicksort che mancherà di cache.

Infine, in genere le persone non scrivono più i propri algoritmi di ordinamento. La maggior parte delle lingue dispone di servizi di libreria da ordinare e la cosa giusta da fare è normalmente usarli. Poiché l'ordinamento digitale non è universalmente applicabile, in genere deve essere adattato all'uso effettivo e utilizza molta memoria aggiuntiva, è difficile inserirlo in una funzione o modello di libreria.

È piuttosto raro che le chiavi ordinate dall'utente siano in realtà numeri interi in un intervallo noto e spoglio. Di solito hai campi alfabetici, che guardano come se fossero compatibili con l'ordinamento non comparativo, ma poiché le stringhe del mondo reale non sono distribuite uniformemente attraverso l'alfabeto, questo non funziona come dovrebbe teoria.

Altre volte, il criterio è definito solo dal punto di vista operativo (dati due record, puoi decidere quale viene prima, ma non puoi valutare come un "lontano" in fondo alla scala è un record isolato). Quindi il metodo spesso non è applicabile, meno applicabile di quanto si possa credere, o semplicemente non è più veloce di O (n * log (n)).

Lo uso tutto il tempo, in realtà più che tipi di confronto, ma sono certamente uno stravagante che funziona più con i numeri di qualsiasi altra cosa (lavoro quasi mai con le stringhe, e sono generalmente internati se è così che punto l'ordinamento dei radix può essere di nuovo utile per filtrare i duplicati e calcolare le intersezioni dei set, non faccio praticamente mai confronti lessicografici.

Un esempio di base è i punti di ordinamento radix di una determinata dimensione come parte di una divisione mediana o di ricerca o un modo rapido per rilevare punti coincidenti, frammenti di ordinamento in profondità o radix ordinamento di una matrice di indici utilizzati in più loop per fornire più cache modelli di accesso amichevoli (non andare avanti e indietro nella memoria solo per tornare indietro e ricaricare la stessa memoria in una linea di cache). Esiste un'applicazione molto ampia almeno nel mio dominio (computer grafica) solo per l'ordinamento su tasti numerici a 32 bit e 64 bit di dimensioni fisse.

Una cosa che volevo inserire e dire è che radix sort può funzionare su numeri in virgola mobile e negativi, sebbene sia difficile scrivere una versione FP che sia il più portabile possibile. Anche se è O (n * K), K deve essere solo il numero di byte della dimensione della chiave (es .: un milione di numeri interi a 32 bit generalmente richiederebbero 4 passaggi di byte se ci sono 2 ^ 8 voci nel bucket ). Anche il pattern di accesso alla memoria tende ad essere molto più "cache-friendly" rispetto ai quicksorts, anche se ha bisogno di un array parallelo e di un piccolo array di bucket in genere (il secondo solitamente si adatta perfettamente allo stack). QS potrebbe fare 50 milioni di swap per ordinare una matrice di un milione di interi con pattern di accesso casuale sporadici. L'ordinamento digitale può farlo in 4 passaggi lineari e compatibili con la cache dei dati.

Tuttavia, la mancanza di consapevolezza di essere in grado di farlo con una piccola K, su numeri negativi con virgola mobile, potrebbe benissimo contribuire in modo significativo alla mancanza di popolarità dei tipi di radix.

Per quanto riguarda la mia opinione sul perché le persone non la usano più spesso, potrebbe avere a che fare con molti domini che generalmente non hanno bisogno di ordinare numeri o di usarli come chiavi di ricerca. Tuttavia, proprio sulla base della mia esperienza personale, molti miei ex colleghi non l'hanno nemmeno utilizzato nei casi in cui era perfettamente adatto, e in parte perché non erano consapevoli che sarebbe stato possibile lavorare su FP e negativi. Quindi, a parte lavorare solo su tipi numerici, si pensa spesso che sia less generalmente applicabile di quanto non sia in realtà. Non ne avrei nemmeno più l'utilità se pensassi che non funzionasse su numeri in virgola mobile e interi negativi.

Alcuni parametri di riferimento:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

E questo è solo con la mia ingenua implementazione ( mt_sort_int è anche l'ordinamento radix ma con un ramo di codice più veloce dato che può assumere che la chiave sia un intero). Immagina quanto velocemente potrebbe essere una implementazione standard scritta da esperti.

L'unico caso in cui ho trovato che l'ordinamento di radix ha un prezzo peggiore di quello basato su confronto veramente veloce di% C ++ era per un numero veramente piccolo di elementi, diciamo 32, a quel punto credo che std::sort inizi a usare gli ordinamenti più adatti per il minor numero di elementi come heapsorts o tipi di inserimento, anche se a quel punto la mia implementazione utilizza solo std::sort .

Un altro motivo: in questi giorni l'ordinamento viene solitamente implementato con una routine di ordinamento fornita dall'utente associata alla logica di ordinamento fornita dal compilatore. Con un ordinamento digitale questo sarebbe molto più complesso e peggiorerà ulteriormente quando la routine di ordinamento agisce su più chiavi di lunghezza variabile. (Dì, nome e data di nascita.)

Nel mondo reale ho effettivamente implementato un ordinamento digitale una volta . Questo era ai vecchi tempi quando la memoria era limitata, non potevo portare tutti i miei dati in memoria in una volta. Ciò significava che il numero di accessi ai dati era molto più importante di O (n) vs O (n log n). Ho fatto un passaggio attraverso i dati che assegnavano ogni record a un bin (da un elenco di quali record erano in cui bin, in realtà non spostare nulla.) Per ogni bin non vuoto (la mia chiave di ordinamento era testo, ci sarebbe un sacco di contenitori vuoti) Ho controllato se potevo effettivamente portare i dati in memoria - se sì, portalo dentro e usa quicksort. In caso negativo, creare un file temporaneo contenente solo gli elementi nel contenitore e chiamare la routine in modo ricorsivo. (In pratica, alcuni raccoglitori potrebbero traboccare.) Ciò ha causato due letture complete e una scrittura completa sull'archivio di rete e qualcosa come il 10% di questo su memoria locale. Semplicemente quicksorting dell'intero file credo che causi circa 2 * n log n letture e circa la metà di molte scritture - considerevolmente più lento.

In questi giorni problemi di grandi dimensioni di questo tipo sono molto più difficili da trovare, probabilmente non scriverò mai più niente del genere. (Se mi trovassi di fronte agli stessi dati in questi giorni, dovrei semplicemente specificare il SO a 64-bit, aggiungere la RAM se vieni distrutto in quell'editor.)

Se tutti i tuoi parametri sono tutti interi e se hai più di 1024 parametri di input, l'ordinamento digitale è sempre più veloce.

Perché?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

Quindi l'ordinamento radix è più veloce quando

log(n)> max num of digits

Il numero intero massimo in Java è 2147483647. Che è lungo 10 cifre

Quindi l'ordinamento radix è sempre più veloce quando

log(n)> 10

Quindi l'ordinamento radix è sempre più veloce quando n>1024