Il modo migliore per ottenere le cifre individuali da int per radix sort in C / C ++

Question

Qual è il modo migliore per ottenere le singole cifre da un int con il numero n di cifre per l'utilizzo in un algoritmo di ordinamento di radice? Mi chiedo se c'è un modo particolarmente efficace di farlo in C / C ++, se non ciò che è la migliore soluzione generale?

modifica:. Solo per chiarire, ero alla ricerca di una soluzione diversa da convertirlo in una stringa e trattandolo come un array di cifre

Answer 1

Utilizzare le cifre del formato 2^k. Per estrarre la cifra nth:

#define BASE (2<<k)
#define MASK (BASE-1)

inline unsigned get_digit(unsigned word, int n) {
    return (word >> (n*k)) & MASK;
}

Utilizzando lo spostamento e la maschera (abilitato da base essendo una potenza di 2) evita costosi istruzioni interi dividono.

Dopo di che, scegliendo la migliore base è una questione sperimentale (tempo / spazio compromesso per il vostro particolare hardware). Probabilmente k==3 (base 8) funziona bene e limita il numero di secchi, ma k==4 (base 16) sembra più attraente perché divide la dimensione della parola. Tuttavia, non c'è davvero niente di sbagliato con una base che non divide la dimensione della parola, e si potrebbe scoprire che di base 32 o base 64 prestazioni migliori. E 'una domanda sperimentale e può probabilmente differire di hardware, in base a come le si comporta di cache e quanti elementi ci sono nel vostro array.

Nota finale: se si esegue l'ordinamento firmato vita interi è un dolore molto più grande, perché si vuole trattare il bit più significativo in quanto firmato. Mi consiglia di trattare tutto come unsigned, e poi se si ha realmente bisogno registrato, nell'ultimo passaggio della vostra radix sort si scambierà i secchi, in modo che secchi con un più significativo 1 vengono prima di un più significativo 0. Questo problema è sicuramente più facile se si divide k la dimensione della parola.

Answer 2

Non utilizzare base 10, base 16 uso.

for (int i = 0; i < 8; i++) {
    printf("%d\n", (n >> (i*4)) & 0xf);
}

Poiché interi sono memorizzati internamente in binario, questo sarà più efficiente rispetto dividere per 10 per determinare decimale cifre.