Pushing Radix Sort (e python) ai suoi limiti

Question

Sono stato immensamente frustrato con molte delle implementazioni di Python Radix sort là fuori sul web.

Essi utilizzano costantemente una radice di 10 e ottengono le cifre dei numeri su cui iterano suddividendo dividendo per una potenza di 10 o prendendo il log10 del numero. Questo è incredibilmente inefficiente, dato che log10 non è un'operazione particolarmente veloce rispetto al cambio di bit, che è quasi 100 volte più veloce!

Un'implementazione molto più efficiente utilizza una radice di 256 e ordina il numero byte per byte. Ciò consente di eseguire tutto il "byte get" utilizzando gli operatori di bit ridicolmente rapidi. Sfortunatamente, sembra che nessuno in assoluto abbia implementato un ordinamento per la radix in python che utilizza operatori bit anziché logaritmi.

Così, ho preso le cose nelle mie mani e si avvicinò con questa bestia, che corre a circa la metà della velocità di ordinato in piccoli array e funziona quasi più rapidamente su quelli più grandi (ad esempio len intorno 10.000.000):

import itertools 

def radix_sort(unsorted): 
    "Fast implementation of radix sort for any size num." 
    maximum, minimum = max(unsorted), min(unsorted) 

    max_bits = maximum.bit_length() 
    highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 

    min_bits = minimum.bit_length() 
    lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 

    sorted_list = unsorted 
    for offset in xrange(lowest_byte, highest_byte): 
     sorted_list = radix_sort_offset(sorted_list, offset) 

    return sorted_list 

def radix_sort_offset(unsorted, offset): 
    "Helper function for radix sort, sorts each offset." 
    byte_check = (0xFF << offset*8) 

    buckets = [[] for _ in xrange(256)] 

    for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

    return list(itertools.chain.from_iterable(buckets)) 

Questa versione di radix sort funziona individuando quali byte deve ordinare (se si passano solo interi inferiori a 256, si ordina solo un byte, ecc.) Quindi si ordina ciascun byte da LSB verso l'alto scaricandoli nei secchi per poi mettere insieme i secchi. Ripeti questo per ogni byte che deve essere ordinato e hai la tua bella matrice ordinata in tempo O (n).

Tuttavia, non è veloce come potrebbe essere, e mi piacerebbe renderlo più veloce prima di scrivere su di esso come una sorta di radix migliore rispetto a tutti gli altri tipi di radix in circolazione.

esecuzione cProfile su questo mi dice che un sacco di tempo viene speso sul metodo append per gli elenchi, che mi fa pensare che questo blocco:

for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

in radix_sort_offset sta mangiando un sacco di tempo. Questo è anche il blocco che, se lo si guarda veramente, fa il 90% del lavoro per l'intero genere. Sembra che questo codice potrebbe essere numpy -ized, che a mio avviso porterebbe a un notevole incremento delle prestazioni. Sfortunatamente, non sono molto bravo con le funzioni più complesse di numpy, quindi non sono stato in grado di capirlo. L'aiuto sarebbe molto apprezzato

Attualmente sto usando itertools.chain.from_iterable per appiattire il buckets, ma se qualcuno ha un suggerimento più veloce sono sicuro che sarebbe di aiuto pure.

Originariamente, avevo una funzione get_byte che restituiva il numero n di un numero, ma l'inlining del codice mi ha dato un enorme aumento di velocità, quindi l'ho fatto.

Anche altri commenti sull'implementazione o sui modi per spremere più prestazioni sono apprezzati. Voglio sentire tutto e tutto quello che hai.

Answer 1

È già capito che

for num in unsorted: 
    byte_at_offset = (num & byte_check) >> offset*8 
    buckets[byte_at_offset].append(num) 

è dove la maggior parte del tempo va - buono ;-)

Ci sono due trucchi standard per accelerare questo genere di cose, sia a che fare con invarianti in movimento out of loop:

1. Calcolare "offset * 8" al di fuori del ciclo.Conservalo in una variabile locale. Salva una moltiplicazione per iterazione.
2. Aggiungi bucketappender = [bucket.append for bucket in buckets] fuori dal ciclo. Salva una ricerca del metodo per iterazione.

combinarli, e il ciclo si presenta come:

for num in unsorted: 
    bucketappender[(num & byte_check) >> ofs8](num) 

Crollare a un'istruzione salva anche un paio di negozio VRBL local/recuperare codici operativi per ogni iterazione.

Ma, a un livello superiore, il metodo standard per accelerare l'ordinamento digitale è utilizzare un radix più grande. Cosa c'è di magico nel 256? Niente, a parte questo è conveniente per il bit-shifting. Ma lo sono anche 512, 1024, 2048 ... è un classico compromesso tempo/spazio.

PS: per i numeri molto lunghi,

(num >> offset*8) & 0xff 

sarà più veloce. Questo perché il tuo num & byte_check richiede tempo proporzionale a log(num) - in genere deve creare un numero intero pari a num.

Answer 2

Si potrebbe semplicemente utilizzare uno dei C esistente o implementazioni C++, ad esempio come esempio, integer_sort da Boost.Sort o u4_sort da usort. È sorprendentemente facile chiamare codice C o C++ nativo da Python, vedere How to sort an array of integers faster than quicksort?

Ho totalmente la tua frustrazione. Anche se sono passati più di 2 anni, numpy still does not have radix sort. Lascerò che gli sviluppatori di NumPy sappiano che potrebbero semplicemente prendere una delle implementazioni esistenti; la licenza non dovrebbe essere un problema.

Answer 3

Questo è un thread vecchio, ma ho trovato questo quando si cerca di radix ordinare una matrice di numeri interi positivi. Stavo cercando di vedere se potevo fare qualcosa di meglio del timsort già incredibilmente veloce (ancora una volta per te, Tim Peters) che implementa l'ordinamento e l'ordinamento di python! O non capisco alcuni aspetti del codice di cui sopra, o se lo faccio, il codice come presentato sopra ha alcuni problemi IMHO.

1. Ordina solo byte che iniziano con il byte più alto dell'elemento più piccolo e termina con il byte più alto dell'elemento più grande. Questo può essere ok in alcuni casi di dati speciali. Ma in generale l'approccio non riesce a differenziare gli articoli che differiscono a causa dei bit più bassi. Ad esempio:

   arr=[65535,65534] 
   radix_sort(arr) 
   

   produce potenza errata:

   [65535, 65534] 
   

2. L'intervallo utilizzato al ciclo sopra la funzione di supporto non è corretto. Quello che intendo è che se lower_byte e highest_byte sono uguali, l'esecuzione della funzione helper è del tutto saltata. A proposito ho dovuto cambiare xrange a range in 2 posti.

3. Con le modifiche apportate ai suddetti 2 punti, ho avuto modo di funzionare. Ma sta prendendo 10-20 volte il tempo di python integrato o ordinato! So che Timsort è molto efficiente e sfrutta trazioni già ordinate nei dati. Ma stavo cercando di vedere se posso usare la conoscenza precedente che i miei dati sono tutti interi positivi con qualche vantaggio nel mio ordinamento. Perché l'ordinamento digitale funziona così male rispetto al timsort? Le dimensioni dell'array che stavo utilizzando sono nell'ordine di 80 K elementi.È perché l'implementazione di timsort oltre alla sua efficienza algoritmica ha anche altre efficienze derivanti dal possibile utilizzo di librerie di basso livello? O mi manca qualcosa del tutto? Il codice modificato che ho usato è qui sotto:

   import itertools 
   
   def radix_sort(unsorted): 
       "Fast implementation of radix sort for any size num." 
       maximum, minimum = max(unsorted), min(unsorted) 
   
       max_bits = maximum.bit_length() 
       highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 
   
   # min_bits = minimum.bit_length() 
   # lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 
   
       sorted_list = unsorted 
   # xrange changed to range, lowest_byte deleted from the arguments 
       for offset in range(highest_byte): 
        sorted_list = radix_sort_offset(sorted_list, offset) 
   
       return sorted_list 
   
   def radix_sort_offset(unsorted, offset): 
       "Helper function for radix sort, sorts each offset." 
       byte_check = (0xFF << offset*8) 
   
   # xrange changed to range 
       buckets = [[] for _ in range(256)] 
   
       for num in unsorted: 
        byte_at_offset = (num & byte_check) >> offset*8 
        buckets[byte_at_offset].append(num) 
   
       return list(itertools.chain.from_iterable(buckets))