Ottimizzazione ordinamento Radix

Stavo cercando di ottimizzare il codice di ordinamento Radix, perché sentivo che c’era spazio perché i codici tradizionali nei libri e sul web sembrano una copia diretta l’uno dell’altro e inoltre funzionano molto lentamente poiché prendono un numero arbitrario come 10 per modulo operazione. Ho ottimizzato il codice per quanto ho potuto andare, forse avrei perso alcune tecniche di ottimizzazione. In tal caso per favore mi illumini.

Motivazione per l’ottimizzazione:
http://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html
Non sono stato in grado di implementare tutte le ottimizzazioni negli articoli, per lo più era al di là delle mie capacità, comprensione e mancanza di tempo sufficiente, se puoi sentirti libero di implementarle.

MODIFICA 4
Questa versione Java di Radix Sort calcola tutti gli istogrammi in 1 lettura e non ha bisogno di riempire l’array Z con zeri dopo ogni ordinamento LSB insieme alla solita capacità di saltare l’ordinamento e passare all’ordinamento LSB successivo se tutti gli LSB precedenti sono uguali. Come al solito questo è solo per interi a 32 bit, ma una versione a 64 bit può essere creata da esso.

protected static int[] DSC(int A[])// Sorts in descending order { int tmp[] = new int[A.length] ; int Z[] = new int[1024] ; int i, Jump, Jump2, Jump3, Jump4, swap[] ; Jump = A[0] & 255 ; Z[Jump] = 1 ; Jump2 = ((A[0] >> 8) & 255) + 256 ; Z[Jump2] = 1 ; Jump3 = ((A[0] >> 16) & 255) + 512 ; Z[Jump3] = 1 ; Jump4 = (A[0] >> 24) + 768 ; Z[Jump4] = 1 ; // Histograms creation for (i = 1 ; i > 8) & 255) + 256] ; ++Z[((A[i] >> 16) & 255) + 512] ; ++Z[(A[i] >> 24) + 768] ; } // 1st LSB Byte Sort if( Z[Jump] != A.length ) { Z[0] = A.length - Z[0]; for (i = 1; i < 256; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (i = 0; i < A.length; ++i) { tmp[Z[A[i] & 255]++] = A[i]; } swap = A ; A = tmp ; tmp = swap ; } // 2nd LSB Byte Sort if( Z[Jump2] != A.length ) { Z[256] = A.length - Z[256]; for (i = 257; i < 512; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (i = 0; i > 8) & 255) + 256]++] = A[i]; } swap = A ; A = tmp ; tmp = swap ; } // 3rd LSB Byte Sort if( Z[Jump3] != A.length ) { Z[512] = A.length - Z[512]; for (i = 513; i < 768; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (i = 0; i > 16) & 255) + 512]++] = A[i]; } swap = A ; A = tmp ; tmp = swap ; } // 4th LSB Byte Sort if( Z[Jump4] != A.length ) { Z[768] = A.length - Z[768]; for (i = 769; i < Z.length; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (i = 0; i > 24) + 768]++] = A[i]; } return tmp ; } return A ; } 

La versione di Java è più veloce con segno! = Segno di ==

 if( Z[Jump] != A.length ) { // lines of code }... 

ma in C la versione inferiore era in media il 25% più veloce (con il segno di equalto) rispetto alla sua controparte con segno! =. Il tuo hardware potrebbe reactjs in modo diverso.

     if( Z[Jump] == A.length ); else { // lines of code }... 

    Di seguito è riportato il codice C (“long” sulla mia macchina è a 32 bit)

     long* Radix_2_ac_long(long *A, size_t N, long *Temp)// Sorts in ascending order { size_t Z[1024] = {0}; long *swp; size_t i, Jump, Jump2, Jump3, Jump4; // Sort-circuit set-up Jump = *A & 255; Z[Jump] = 1; Jump2 = ((*A >> 8) & 255) + 256; Z[Jump2] = 1; Jump3 = ((*A >> 16) & 255) + 512; Z[Jump3] = 1; Jump4 = (*A >> 24) + 768; Z[Jump4] = 1; // Histograms creation for(i = 1 ; i > 8) & 255) + 256]; ++Z[((*(A+i) >> 16) & 255) + 512]; ++Z[(*(A+i) >> 24) + 768]; } // 1st LSB byte sort if( Z[Jump] == N ); else { for( i = 1 ; i < 256 ; ++i ) { Z[i] = Z[i-1] + Z[i]; } for( i = N-1 ; i < N ; --i ) { *(--Z[*(A+i) & 255] + Temp) = *(A+i); } swp = A; A = Temp; Temp = swp; } // 2nd LSB byte sort if( Z[Jump2] == N ); else { for( i = 257 ; i < 512 ; ++i ) { Z[i] = Z[i-1] + Z[i]; } for( i = N-1 ; i > 8) & 255) + 256] + Temp) = *(A+i); } swp = A; A = Temp; Temp = swp; } // 3rd LSB byte sort if( Z[Jump3] == N ); else { for( i = 513 ; i < 768 ; ++i ) { Z[i] = Z[i-1] + Z[i]; } for( i = N-1 ; i > 16) & 255) + 512] + Temp) = *(A+i); } swp = A; A = Temp; Temp = swp; } // 4th LSB byte sort if( Z[Jump4] == N ); else { for( i = 769 ; i < 1024 ; ++i ) { Z[i] = Z[i-1] + Z[i]; } for( i = N-1 ; i > 24) + 768] + Temp) = *(A+i); } return Temp; } return A; } 

    MODIFICA 5
    L’ordinamento ora gestisce anche i numeri negativi. Lo ha fatto solo alcune modifiche minori o trascurabili al codice. Ne risulta un po ‘più lento, ma l’effetto non è significativo. Codificato in C, sotto (“long” sul mio sistema è a 32 bit)

     long* Radix_Sort(long *A, size_t N, long *Temp) { size_t Z[1024] = {0}; long *swp; size_t Jump, Jump2, Jump3, Jump4; long i; // Sort-circuit set-up Jump = *A & 255; Z[Jump] = 1; Jump2 = ((*A >> 8) & 255) + 256; Z[Jump2] = 1; Jump3 = ((*A >> 16) & 255) + 512; Z[Jump3] = 1; Jump4 = ((*A >> 24) & 255) + 768; Z[Jump4] = 1; // Histograms creation for(i = 1 ; i > 8) & 255) + 256]; ++Z[((*(A+i) >> 16) & 255) + 512]; ++Z[((*(A+i) >> 24) & 255) + 768]; } // 1st LSB byte sort if( Z[Jump] == N ); else { for( i = 1 ; i = 0 ; --i ) { *(--Z[*(A+i) & 255] + Temp) = *(A+i); } swp = A; A = Temp; Temp = swp; } // 2nd LSB byte sort if( Z[Jump2] == N ); else { for( i = 257 ; i = 0 ; --i ) { *(--Z[((*(A+i) >> 8) & 255) + 256] + Temp) = *(A+i); } swp = A; A = Temp; Temp = swp; } // 3rd LSB byte sort if( Z[Jump3] == N ); else { for( i = 513 ; i = 0 ; --i ) { *(--Z[((*(A+i) >> 16) & 255) + 512] + Temp) = *(A+i); } swp = A; A = Temp; Temp = swp; } // 4th LSB byte sort and negative numbers sort if( Z[Jump4] == N ); else { for( i = 897 ; i < 1024 ; ++i )// -ve values frequency starts after index 895, ie at 896 ( 896 = 768 + 128 ), goes upto 1023 { Z[i] = Z[i-1] + Z[i]; } Z[768] = Z[768] + Z[1023]; for( i = 769 ; i = 0 ; --i ) { *(--Z[((*(A+i) >> 24) & 255) + 768] + Temp) = *(A+i); } return Temp; } return A; } 

    MODIFICA 6
    Di seguito è riportata la versione ottimizzata del puntatore (accede alle posizioni dell’array tramite puntatori) che richiede in media circa il 20% in meno di tempo per l’ordinamento rispetto a quella sopra. Utilizza inoltre 4 array separati per il calcolo dell’indirizzo più veloce (“long” sul mio sistema è a 32 bit).

     long* Radix_Sort(long *A, size_t N, long *Temp) { long Z1[256] ; long Z2[256] ; long Z3[256] ; long Z4[256] ; long T = 0 ; while(T != 256) { *(Z1+T) = 0 ; *(Z2+T) = 0 ; *(Z3+T) = 0 ; *(Z4+T) = 0 ; ++T; } size_t Jump, Jump2, Jump3, Jump4; // Sort-circuit set-up Jump = *A & 255 ; Z1[Jump] = 1; Jump2 = (*A >> 8) & 255 ; Z2[Jump2] = 1; Jump3 = (*A >> 16) & 255 ; Z3[Jump3] = 1; Jump4 = (*A >> 24) & 255 ; Z4[Jump4] = 1; // Histograms creation long *swp = A + N; long *i = A + 1; for( ; i != swp ; ++i) { ++Z1[*i & 255]; ++Z2[(*i >> 8) & 255]; ++Z3[(*i >> 16) & 255]; ++Z4[(*i >> 24) & 255]; } // 1st LSB byte sort if( Z1[Jump] == N ); else { swp = Z1+256 ; for( i = Z1+1 ; i != swp ; ++i ) { *i = *(i-1) + *i; } swp = A-1; for( i = A+N-1 ; i != swp ; --i ) { *(--Z1[*i & 255] + Temp) = *i; } swp = A; A = Temp; Temp = swp; } // 2nd LSB byte sort if( Z2[Jump2] == N ); else { swp = Z2+256 ; for( i = Z2+1 ; i != swp ; ++i ) { *i = *(i-1) + *i; } swp = A-1; for( i = A+N-1 ; i != swp ; --i ) { *(--Z2[(*i >> 8) & 255] + Temp) = *i; } swp = A; A = Temp; Temp = swp; } // 3rd LSB byte sort if( Z3[Jump3] == N ); else { swp = Z3 + 256 ; for( i = Z3+1 ; i != swp ; ++i ) { *i = *(i-1) + *i; } swp = A-1; for( i = A+N-1 ; i != swp ; --i ) { *(--Z3[(*i >> 16) & 255] + Temp) = *i; } swp = A; A = Temp; Temp = swp; } // 4th LSB byte sort and negative numbers sort if( Z4[Jump4] == N ); else { swp = Z4 + 256 ; for( i = Z4+129 ; i != swp ; ++i ) { *i = *(i-1) + *i; } *Z4 = *Z4 + *(Z4+255) ; swp = Z4 + 128 ; for( i = Z4+1 ; i != swp ; ++i ) { *i = *(i-1) + *i; } swp = A - 1; for( i = A+N-1 ; i != swp ; --i ) { *(--Z4[(*i >> 24) & 255] + Temp) = *i; } return Temp; } return A; } 

    La versione edit 4 è abbastanza buona se gli array originali e temporanei si adattano alla cache. Se la dimensione dell’array è molto maggiore della dimensione della cache, la maggior parte del sovraccarico è dovuta alle scritture degli ordini casuali sugli array. Un ordinamento radicale ibrido msb / lsb può evitare questo problema. Ad esempio, dividere l’array in 256 bin in base al byte più significativo, quindi eseguire un ordinamento su lsb su ciascuno dei 256 bin. L’idea qui è che una coppia (originale e temp) di bin si adatterà alla cache, dove le scritture degli ordini casuali non sono un problema (per la maggior parte delle implementazioni della cache).

    Per una cache da 8 MB, l’objective è che ciascuno dei bin sia <4 MB di dimensione = 1 milione di numeri interi a 32 bit se gli interi si distribuiscono uniformemente nei raccoglitori. Questa strategia funzionerebbe per dimensioni di array fino a 256 milioni di interi a 32 bit. Per gli array più grandi, la fase msb potrebbe suddividere l'array in 1024 bin, per un massimo di 1 miliardo di interi a 32 bit. Sul mio sistema, l'ordinamento di 16.777.216 (2 ^ 24) numeri interi a 32 bit con un classico ordinamento di 8,8,8,8 lsb ha richiesto 0,45 secondi, mentre l'ibrido 8 msb: 8,8,8 lsb ha impiegato 0,24 secondi.

     // split array into 256 bins according to most significant byte void RadixSort(uint32_t * a, size_t count) { size_t aIndex[260] = {0}; // count / array uint32_t * b = new uint32_t [count]; // allocate temp array size_t i; for(i = 0; i < count; i++) // generate histogram aIndex[1+((size_t)(a[i] >> 24))]++; for(i = 2; i < 257; i++) // convert to indices aIndex[i] += aIndex[i-1]; for(i = 0; i < count; i++) // sort by msb b[aIndex[a[i]>>24]++] = a[i]; for(i = 256; i; i--) // restore aIndex aIndex[i] = aIndex[i-1]; aIndex[0] = 0; for(i = 0; i < 256; i++) // radix sort the 256 bins RadixSort3(&b[aIndex[i]], &a[aIndex[i]], aIndex[i+1]-aIndex[i]); delete[] b; } // sort a bin by 3 least significant bytes void RadixSort3(uint32_t * a, uint32_t *b, size_t count) { size_t mIndex[3][256] = {0}; // count / matrix size_t i,j,m,n; uint32_t u; if(count == 0) return; for(i = 0; i < count; i++){ // generate histograms u = a[i]; for(j = 0; j < 3; j++){ mIndex[j][(size_t)(u & 0xff)]++; u >>= 8; } } for(j = 0; j < 3; j++){ // convert to indices m = 0; for(i = 0; i < 256; i++){ n = mIndex[j][i]; mIndex[j][i] = m; m += n; } } for(j = 0; j < 3; j++){ // radix sort for(i = 0; i < count; i++){ // sort by current lsb u = a[i]; m = (size_t)(u>>(j<<3))&0xff; b[mIndex[j][m]++] = u; } std::swap(a, b); // swap ptrs } } 

    Codice di esempio per i classici tipi di lsb radix:

    Esempio di ordinamento digitale lsb C ++ con campi di 8,8,8,8 bit:

     typedef unsigned int uint32_t; void RadixSort(uint32_t * a, size_t count) { size_t mIndex[4][256] = {0}; // count / index matrix uint32_t * b = new uint32_t [count]; // allocate temp array size_t i,j,m,n; uint32_t u; for(i = 0; i < count; i++){ // generate histograms u = a[i]; for(j = 0; j < 4; j++){ mIndex[j][(size_t)(u & 0xff)]++; u >>= 8; } } for(j = 0; j < 4; j++){ // convert to indices m = 0; for(i = 0; i < 256; i++){ n = mIndex[j][i]; mIndex[j][i] = m; m += n; } } for(j = 0; j < 4; j++){ // radix sort for(i = 0; i < count; i++){ // sort by current lsb u = a[i]; m = (size_t)(u>>(j<<3))&0xff; b[mIndex[j][m]++] = u; } std::swap(a, b); // swap ptrs } delete[] b; } 

    Esempio di codice C ++ utilizzando campi 16,16 bit:

     typedef unsigned int uint32_t; uint32_t * RadixSort(uint32_t * a, size_t count) { size_t mIndex[2][65536] = {0}; // count / index matrix uint32_t * b = new uint32_t [count]; // allocate temp array size_t i,j,m,n; uint32_t u; for(i = 0; i < count; i++){ // generate histograms u = a[i]; for(j = 0; j < 2; j++){ mIndex[j][(size_t)(u & 0xffff)]++; u >>= 16; } } for(j = 0; j < 2; j++){ // convert to indices m = 0; for(i = 0; i < 65536; i++){ n = mIndex[j][i]; mIndex[j][i] = m; m += n; } } for(j = 0; j < 2; j++){ // radix sort for(i = 0; i < count; i++){ // sort by current lsb u = a[i]; m = (size_t)(u>>(j<<4))&0xffff; b[mIndex[j][m]++] = u; } std::swap(a, b); // swap ptrs } delete[] b; return(a); } 

    N & 15, N e 31, N e 63 …. e così via, quale di queste operazioni bit a bit richiede meno tempo?

    Sono uguali. Non prendercanvas male, ma ottimizzandoti per la velocità senza sapere quanto dureranno le cose potrebbero finire male. E anche quando conosci i tempi, l’hardware è molto complicato al giorno d’oggi e abbastanza imprevedibile. Programmate in java, che è un altro strato di sistema follemente complesso. Lo stesso codice potrebbe essere più veloce oggi e più lento domani. Dite approximately 2.232891909840167 times faster . In realtà, si dispone di misurazioni su una configurazione hardware e software con un set di dati e si può solo sperare che la misurazione sia sufficientemente rappresentativa. Sfortunatamente, non è sempre il caso.

    Ho riscritto la tua funzione. È più breve e più semplice, ma non sembra essere più lento. I compilatori tendono ad apprezzare il codice che non è troppo intelligente, in quanto vi sono molte ottimizzazioni per i casi semplici. La correzione per i numeri negativi non è particolarmente piacevole, puoi eliminarla se non ti piace. Sembra funzionare meglio per 8 bit e 11 bit, probabilmente a causa delle dimensioni della cache, dai un’occhiata ai commenti di rcgldr.

    MODIFICARE

    @ytoamn hai ragione, se tutto è nel primo bucket il ciclo dovrebbe continuare, non rompere. Quello era un bug. Per gli altri cambiamenti, preferirei evitare il contratto che hai fatto ora. Penso che ci siano tre contratti naturali per la funzione di smistamento. Il primo è ordinare l’array originale e restituire null. Il secondo è ordinare l’array originale e restituirlo. Il terzo sta restituendo nuovo array ordinato e mantenendo intatto l’array originale. Mi piace il primo, poiché il suo comportamento è inequivocabile. Il modo in cui ora è necessario aggiungere un grande avvertimento alla documentazione, che l’array originale è cambiato e viene restituito dalla funzione è alcuni casi e in altri no. La seconda cosa che eviterei è il vecchio stile del codice C. Dovresti definire la variabile di ciclo nel ciclo se ne hai bisogno solo lì. Definirlo globalmente inietta la dipendenza che può portare a bug. E qui non ha alcun vantaggio, dal momento che le variabili del loop opportunamente definite condivideranno comunque lo spazio alla fine. Il compilatore è ben consapevole dello scopo, è necessario utilizzare l’ambito più piccolo necessario.

    EDIT2

    Sentiti libero di commentare direttamente sotto il mio post 🙂 Le variabili locali sono solo gli indirizzi in pila. Alloca la memoria quando costruisci un object che non è il caso qui. Per quanto riguarda l’array, pensa a questo codice:

     public static void Tst(int[] A) { int[] tmp = new int[A.length]; A[0] = 6; A = tmp; // changes what parameter A contains A[0] = 7; } public static void main(String[] args) { int[] A = new int[1]; A[0] = 5; Tst(A); System.out.println(A[0]); //prints 6 } 

    Stampa 6. Il numero 7 è scritto solo nell’array tmp. La matrice A in main non è influenzata.

     protected static void ASC2(int A[], int bits) { int[] origA = A; int[] tmp = new int[A.length]; int[] Z = new int[1 << bits]; int mask = (1 << bits) - 1; for (int shift = 0; shift < 32; shift += bits) { if (shift > 0) { Arrays.fill(Z, 0); } for (int i = 0; i < A.length; ++i) { Z[(A[i] >> shift) & mask]++; } if (Z[0] == A.length) { continue; // all in first bucket } Z[Z.length - 1] = A.length - Z[Z.length - 1]; for (int i = Z.length - 2; i >= 0; --i) { Z[i] = Z[i + 1] - Z[i]; } if (shift + bits > 31) { // negative numbers correction int halfLength = Z.length / 2; int positSum = Z[halfLength]; int negSum = A.length - positSum; if (negSum > 0) { for (int i = 0; i < halfLength; ++i) { Z[i] += negSum; } for (int i = halfLength; i < Z.length; ++i) { Z[i] -= positSum; } } } for (int i = 0; i < A.length; ++i) { tmp[Z[(A[i] >> shift) & mask]++] = A[i]; } int[] swap = A; A = tmp; tmp = swap; } if (A != origA) { System.arraycopy(A, 0, origA, 0, A.length); } } 

    Edit3

    Loop Unroll è una tecnica valida, il miglioramento del cortocircuito è davvero piacevole. Ma con l’utilizzo di lunghezze di array come costanti si inizia decisamente ad essere troppo intelligente. Se hai codificato con difficoltà la dimensione base, perché non il codice hard è tutto così:

     protected static int[] DSC2(int A[])// sorts in descending order { int tmp[] = new int[A.length]; int Z[] = new int[256]; int sample, swap[]; // 1st LSB byte extraction sample = A[0] & 255; for (int i = 0; i < A.length; ++i) { Z[A[i] & 255]++; } if (Z[sample] != A.length) { Z[0] = A.length - Z[0]; for (int i = 1; i < Z.length; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (int i = 0; i < A.length; ++i) { tmp[Z[A[i] & 255]++] = A[i]; } swap = A; A = tmp; tmp = swap; Arrays.fill(Z, 0); } else { Z[sample] = 0; } // 2nd LSB byte extraction sample = (A[0] >> 8) & 255; for (int i = 0; i < A.length; ++i) { Z[(A[i] >> 8) & 255]++; } if (Z[sample] != A.length) { Z[0] = A.length - Z[0]; for (int i = 1; i < Z.length; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (int i = 0; i < A.length; ++i) { tmp[Z[(A[i] >> 8) & 255]++] = A[i]; } swap = A; A = tmp; tmp = swap; Arrays.fill(Z, 0); } else { Z[sample] = 0; } // 3rd LSB byte extraction sample = (A[0] >> 16) & 255; for (int i = 0; i < A.length; ++i) { Z[(A[i] >> 16) & 255]++; } if (Z[sample] != A.length) { Z[0] = A.length - Z[0]; for (int i = 1; i < Z.length; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (int i = 0; i < A.length; ++i) { tmp[Z[(A[i] >> 16) & 255]++] = A[i]; } swap = A; A = tmp; tmp = swap; Arrays.fill(Z, 0); } else { Z[sample] = 0; } // 4th LSB byte extraction sample = (A[0] >> 24) & 255; for (int i = 0; i < A.length; ++i) { Z[(A[i] >> 24) & 255]++; } if (Z[sample] != A.length) { Z[0] = A.length - Z[0]; for (int i = 1; i < Z.length; ++i) { Z[i] = Z[i - 1] - Z[i]; } for (int i = 0; i < A.length; ++i) { tmp[Z[(A[i] >> 24) & 255]++] = A[i]; } A = tmp; } return A; }