Ordinamento di Radice sul posto

Questo è un lungo testo. Per favore, sopportami. Ridotto, la domanda è: esiste un algoritmo di ordinamento radix funzionante sul posto ?


Preliminare

Ho un numero enorme di stringhe di lunghezza fissa che usano solo le lettere “A”, “C”, “G” e “T” (sì, avete indovinato: DNA ) che voglio ordinare.

Al momento, utilizzo std::sort che utilizza l’ introsort in tutte le implementazioni comuni di STL . Funziona abbastanza bene. Tuttavia, sono convinto che radix sort si adatti perfettamente al mio problema e dovrebbe funzionare molto meglio nella pratica.

Dettagli

Ho provato questa ipotesi con un’implementazione molto ingenua e per input relativamente piccoli (dell’ordine di 10.000) questo era vero (beh, almeno più del doppio). Tuttavia, il runtime degrada in modo abissale quando la dimensione del problema aumenta ( N > 5.000.000).

La ragione è ovvia: radix sort richiede la copia di tutti i dati (più di una volta nella mia ingenua implementazione, in realtà). Ciò significa che ho messo ~ 4 GiB nella mia memoria principale che ovviamente uccide le prestazioni. Anche se così non fosse, non posso permettermi di usare questa quantità di memoria in quanto le dimensioni dei problemi diventano ancora più grandi.

    Casi d’uso

    Idealmente, questo algoritmo dovrebbe funzionare con qualsiasi lunghezza di stringa compresa tra 2 e 100, per DNA e DNA5 (che consente un carattere jolly aggiuntivo “N”), o anche DNA con codici di ambiguità IUPAC (risultanti in 16 valori distinti). Tuttavia, mi rendo conto che tutti questi casi non possono essere coperti, quindi sono soddisfatto del miglioramento della velocità che ottengo. Il codice può decidere dynamicmente a quale algoritmo inviare.

    Ricerca

    Sfortunatamente, l’ articolo di Wikipedia su Radix sort è inutile. La sezione su una variante sul posto è completa spazzatura. La sezione NIST-DADS su ordinamento digitale è accanto a inesistente. C’è un documento dal suono promettente chiamato Ordinamento Rapido Diretto Adattivo Efficace che descrive l’algoritmo “MSL”. Sfortunatamente, anche questo documento è deludente.

    In particolare, ci sono le seguenti cose.

    Innanzitutto, l’algoritmo contiene diversi errori e lascia molto inspiegabile. In particolare, non dettaglia la chiamata di ricorsione (presumo semplicemente che incrementi o riduca alcuni puntatori per calcolare i valori di spostamento e maschera correnti). Inoltre, usa le funzioni dest_group e dest_address senza dare definizioni. Non riesco a vedere come implementarli in modo efficiente (vale a dire, in O (1), almeno dest_address non è banale).

    Ultimo ma non meno importante, l’algoritmo raggiunge in-place-ness scambiando gli indici di array con gli elementi all’interno della matrice di input. Questo ovviamente funziona solo su array numerici. Ho bisogno di usarlo su stringhe. Certo, potrei solo battere forte la digitazione e andare avanti assumendo che la memoria tolleri la mia memorizzazione di un indice a cui non appartiene. Ma questo funziona solo finché riesco a spremere le mie stringhe in 32 bit di memoria (assumendo numeri interi a 32 bit). Sono solo 16 caratteri (ignoriamo per il momento che 16> log (5.000.000)).

    Un altro articolo di uno degli autori non fornisce affatto una descrizione accurata, ma fornisce il runtime di MSL come sub-lineare che è completamente sbagliato.

    Per ricapitolare : C’è qualche speranza di trovare un’implementazione di riferimento di lavoro o almeno un buon pseudocodice / descrizione di un ordinamento radix sul posto di lavoro che funzioni su stringhe di DNA?

    Bene, ecco una semplice implementazione di un ordinamento digitale MSD per DNA. È scritto in D perché è la lingua che uso di più e quindi è meno probabile che faccia errori stupidi, ma potrebbe essere facilmente tradotto in un’altra lingua. È sul posto ma richiede 2 * seq.length passa attraverso l’array.

     void radixSort(string[] seqs, size_t base = 0) { if(seqs.length == 0) return; size_t TPos = seqs.length, APos = 0; size_t i = 0; while(i < TPos) { if(seqs[i][base] == 'A') { swap(seqs[i], seqs[APos++]); i++; } else if(seqs[i][base] == 'T') { swap(seqs[i], seqs[--TPos]); } else i++; } i = APos; size_t CPos = APos; while(i < TPos) { if(seqs[i][base] == 'C') { swap(seqs[i], seqs[CPos++]); } i++; } if(base < seqs[0].length - 1) { radixSort(seqs[0..APos], base + 1); radixSort(seqs[APos..CPos], base + 1); radixSort(seqs[CPos..TPos], base + 1); radixSort(seqs[TPos..seqs.length], base + 1); } } 

    Ovviamente, questo è un po 'specifico per il DNA, invece di essere generale, ma dovrebbe essere veloce.

    Modificare:

    Sono curioso di sapere se questo codice funzioni effettivamente, quindi l'ho testato / debuggato in attesa che il mio codice bioinformatico fosse in esecuzione. La versione sopra ora è effettivamente testata e funziona. Per 10 milioni di sequenze di 5 basi ciascuna, è circa 3 volte più veloce di un introsort ottimizzato.

    Non ho mai visto una sorta di radix sul posto, e dalla natura del tipo di radix dubito che sia molto più veloce di un ordinamento fuori posto purché l’array temporaneo si adatti alla memoria.

    Ragionare:

    L’ordinamento esegue una lettura lineare sull’array di input, ma tutte le scritture saranno quasi casuali. Da una certa N verso l’alto questo si riduce a un errore di cache per scrittura. Questa mancanza della cache è ciò che rallenta il tuo algoritmo. Se è presente o no, non cambierà questo effetto.

    So che questo non risponderà direttamente alla tua domanda, ma se l’ordinamento è un collo di bottiglia potresti voler dare un’occhiata agli algoritmi di ordinamento come una fase di pre-elaborazione (la pagina wiki sull’heap morbido potrebbe farti iniziare).

    Ciò potrebbe dare una bella spinta alla localizzazione della cache. Un ordinamento di tipo “out-of-place” per i libri di testo avrà quindi un rendimento migliore. Le scritture saranno ancora quasi casuali ma almeno si raggrupperanno attorno agli stessi blocchi di memoria e come tali aumenteranno il rapporto di riscontri nella cache.

    Non ho idea se funziona in pratica però.

    Btw: Se hai a che fare solo con le stringhe di DNA: puoi comprimere un carattere in due bit e impacchettare molto i tuoi dati. Ciò ridurrà il requisito di memoria per il fattore quattro su una rappresentazione naiiva. L’indirizzamento diventa più complesso, ma l’ALU della tua CPU ha comunque molto tempo da dedicare a tutte le cache-miss.

    Sulla base del codice di dsimcha, ho implementato una versione più generica che si adatta bene al framework che usiamo (SeqAn). In realtà, il porting del codice era completamente semplice. Solo in seguito ho scoperto che in realtà ci sono pubblicazioni su questo argomento. La cosa bella è che sostanzialmente dicono lo stesso di voi ragazzi. Un articolo di Andersson e Nilsson sull’implementazione di Radixsort merita sicuramente la lettura. Se ti capita di conoscere il tedesco, assicurati di leggere anche la tesi di diploma di David Weese in cui implementa un indice di sottostringa generico. La maggior parte della tesi è dedicata a un’analisi dettagliata del costo di costruzione dell’indice, considerando la memoria secondaria e file estremamente grandi. I risultati del suo lavoro sono stati effettivamente implementati in Seqan, solo non nelle parti in cui ne avevo bisogno.

    Solo per divertimento, ecco il codice che ho scritto (non penso che nessuno che usi SeqAn possa usarlo). Si noti che non considera ancora i radix 4. Considero che ciò avrebbe un impatto enorme sulle prestazioni, ma sfortunatamente non ho il tempo proprio ora di implementarlo.

    Il codice esegue più di due volte la velocità di Introsort per le stringhe brevi. Il punto di pareggio ha una lunghezza di circa 12-13. Il tipo di stringa (ad esempio se ha 4, 5 o 16 valori diversi) è relativamente poco importante. L’ordinamento> 6.000.000 letture di DNA dal cromosoma 2 del genoma umano richiede poco più di 2 secondi sul mio PC. Solo per la cronaca, è veloce ! Soprattutto considerando che non utilizzo SIMD o altre accelerazioni hardware. Inoltre, valgrind mi mostra che il collo di bottiglia principale è l’ operator new nelle assegnazioni di stringhe. Viene chiamato circa 65.000.000 di volte, dieci volte per ogni stringa! Questo è un omaggio che lo swap potrebbe essere ottimizzato per queste stringhe: invece di fare copie, potrebbe semplicemente scambiare tutti i caratteri. Non ho provato questo, ma sono convinto che farebbe una grande differenza. E, solo per dirlo di nuovo, nel caso qualcuno non stesse ascoltando: la dimensione della radix non ha praticamente alcuna influenza sul tempo di esecuzione – il che significa che dovrei assolutamente provare a implementare il suggerimento di FryGuy, Stephan e EvilTeach.

    Ah sì, a proposito: la localizzazione della cache è un fattore evidente : a partire da stringhe 1M, il runtime non aumenta più linearmente. Tuttavia, questo potrebbe essere risolto abbastanza facilmente: utilizzo l’ordinamento di inserimento per piccoli sottoinsiemi (<= 20 stringhe) - invece di mergesort come suggerito dall'hacker casuale. Apparentemente, questo si comporta anche meglio di mergesort per liste così piccole (vedi il primo articolo che ho linkato).

     namespace seqan { template  inline void prescan(It front, It back, F op, T const& id) { using namespace std; if (front == back) return; typename iterator_traits::value_type accu = *front; *front++ = id; for (; front != back; ++front) { swap(*front, accu); accu = op(accu, *front); } } template  inline void radix_permute(TIter front, TIter back, TSize (& bounds)[RADIX], TSize base) { for (TIter i = front; i != back; ++i) ++bounds[static_cast((*i)[base])]; TSize fronts[RADIX]; std::copy(bounds, bounds + RADIX, fronts); prescan(fronts, fronts + RADIX, std::plus(), 0); std::transform(bounds, bounds + RADIX, fronts, bounds, plus()); TSize active_base = 0; for (TIter i = front; i != back; ) { if (active_base == RADIX - 1) return; while (fronts[active_base] >= bounds[active_base]) if (++active_base == RADIX - 1) return; TSize current_base = static_cast((*i)[base]); if (current_base <= active_base) ++i; else std::iter_swap(i, front + fronts[current_base]); ++fronts[current_base]; } } template  inline void insertion_sort(TIter front, TIter back, TSize base) { typedef typename Value::Type T; struct { TSize base, len; bool operator ()(T const& a, T const& b) { for (TSize i = base; i < len; ++i) if (a[i] < b[i]) return true; else if (a[i] > b[i]) return false; return false; } } cmp = { base, length(*front) }; // No closures yet. :-( for (TIter i = front + 1; i != back; ++i) { T value = *i; TIter j = i; for ( ; j != front && cmp(value, *(j - 1)); --j) *j = *(j - 1); if (j != i) *j = value; } } template  inline void radix(TIter top, TIter front, TIter back, TSize base, TSize (& parent_bounds)[RADIX], TSize next) { if (back - front > 20) { TSize bounds[RADIX] = { 0 }; radix_permute(front, back, bounds, base); // Sort current bucket recursively by suffix. if (base < length(*front) - 1) radix(front, front, front + bounds[0], base + 1, bounds, static_cast(0)); } else if (back - front > 1) insertion_sort(front, back, base); // Sort next buckets on same level recursively. if (next == RADIX - 1) return; radix(top, top + parent_bounds[next], top + parent_bounds[next + 1], base, parent_bounds, next + 1); } template  inline void radix_sort(TIter front, TIter back) { typedef typename Container::Type TStringSet; typedef typename Value::Type TString; typedef typename Value::Type TChar; typedef typename Size::Type TSize; TSize const RADIX = ValueSize::VALUE; TSize bounds[RADIX]; radix(front, front, back, static_cast(0), bounds, RADIX - 1); } } // namespace seqan 

    È certamente ansible eliminare i requisiti di memoria codificando la sequenza in bit. Stai guardando le permutazioni quindi, per la lunghezza 2, con “ACGT” cioè 16 stati o 4 bit. Per la lunghezza 3, questo è 64 stati, che possono essere codificati in 6 bit. Quindi sembra 2 bit per ogni lettera nella sequenza, o circa 32 bit per 16 caratteri come hai detto tu.

    Se esiste un modo per ridurre il numero di “parole” valide, può essere ansible un’ulteriore compressione.

    Quindi, per le sequenze di lunghezza 3, si potrebbero creare 64 bucket, magari uint32 o uint64. Inizializzali a zero. Scorri la tua lista molto grande di 3 sequenze di caratteri e li codifica come sopra. Usalo come pedice e incrementa quel secchio.
    Ripeti fino a quando tutte le tue sequenze sono state elaborate.

    Quindi, rigenerare la tua lista.

    Eseguire l’iterazione dei 64 bucket in ordine, per il conteggio trovato in quel bucket, generare così tante istanze della sequenza rappresentata da quel bucket.
    quando tutti i bucket sono stati ripetuti, hai la matrice ordinata.

    Una sequenza di 4, aggiunge 2 bit, quindi ci sarebbero 256 bucket. Una sequenza di 5, aggiunge 2 bit, quindi ci sarebbero 1024 bucket.

    Ad un certo punto il numero di secchi si avvicina ai tuoi limiti. Se leggi le sequenze da un file, invece di tenerle in memoria, più memoria sarebbe disponibile per i bucket.

    Penso che sarebbe più veloce di fare il genere in situ, poiché è probabile che i secchi rientrino nel set di lavoro.

    Ecco un trucco che mostra la tecnica

     #include  #include  #include  using namespace std; const int width = 3; const int bucketCount = exp(width * log(4)) + 1; int *bucket = NULL; const char charMap[4] = {'A', 'C', 'G', 'T'}; void setup ( void ) { bucket = new int[bucketCount]; memset(bucket, '\0', bucketCount * sizeof(bucket[0])); } void teardown ( void ) { delete[] bucket; } void show ( int encoded ) { int z; int y; int j; for (z = width - 1; z >= 0; z--) { int n = 1; for (y = 0; y < z; y++) n *= 4; j = encoded % n; encoded -= j; encoded /= n; cout << charMap[encoded]; encoded = j; } cout << endl; } int main(void) { // Sort this sequence const char *testSequence = "CAGCCCAAAGGGTTTAGACTTGGTGCGCAGCAGTTAAGATTGTTT"; size_t testSequenceLength = strlen(testSequence); setup(); // load the sequences into the buckets size_t z; for (z = 0; z < testSequenceLength; z += width) { int encoding = 0; size_t y; for (y = 0; y < width; y++) { encoding *= 4; switch (*(testSequence + z + y)) { case 'A' : encoding += 0; break; case 'C' : encoding += 1; break; case 'G' : encoding += 2; break; case 'T' : encoding += 3; break; default : abort(); }; } bucket[encoding]++; } /* show the sorted sequences */ for (z = 0; z < bucketCount; z++) { while (bucket[z] > 0) { show(z); bucket[z]--; } } teardown(); return 0; } 

    Se il tuo set di dati è così grande, allora penserei che un approccio al buffer basato su disco sarebbe il migliore:

     sort(List elements, int prefix) if (elements.Count < THRESHOLD) return InMemoryRadixSort(elements, prefix) else return DiskBackedRadixSort(elements, prefix) DiskBackedRadixSort(elements, prefix) DiskBackedBuffer[] buckets foreach (element in elements) buckets[element.MSB(prefix)].Add(element); List ret foreach (bucket in buckets) ret.Add(sort(bucket, prefix + 1)) return ret 

    Vorrei anche sperimentare il raggruppamento in un numero maggiore di bucket, ad esempio, se la stringa era:

     GATTACA 

    la prima chiamata MSB restituirebbe il bucket per GATT (256 bucket totali), in questo modo si creano meno rami del buffer basato su disco. Questo può o non può migliorare le prestazioni, quindi sperimentalo.

    Ho intenzione di uscire su un arto e suggerisco di passare a un’implementazione heap / heapsort . Questo suggerimento viene fornito con alcune ipotesi:

    1. Controlli la lettura dei dati
    2. Puoi fare qualcosa di significativo con i dati ordinati non appena inizi a ottenerli ordinati.

    La bellezza dell’heap / heap-sort è che puoi creare l’heap mentre leggi i dati, e puoi iniziare a ricevere risultati nel momento in cui hai costruito l’heap.

    Facciamo un passo indietro. Se sei così fortunato da poter leggere i dati in modo asincrono (cioè, puoi postare qualche tipo di richiesta di lettura e ricevere una notifica quando alcuni dati sono pronti), e poi puoi build un blocco dell’heap mentre stai aspettando il prossimo pezzo di dati per entrare – anche dal disco. Spesso, questo approccio può seppellire la maggior parte del costo di metà del tuo ordinamento dietro il tempo impiegato per ottenere i dati.

    Una volta letti i dati, il primo elemento è già disponibile. A seconda di dove stai inviando i dati, questo può essere ottimo. Se lo si invia a un altro lettore asincrono o a un modello di “evento” parallelo o all’interfaccia utente, è ansible inviare blocchi e blocchi mentre si procede.

    Detto questo, se non si ha il controllo su come i dati vengono letti, e viene letto in modo sincrono, e non si ha alcun uso per i dati ordinati fino a quando non è completamente scritto, ignorare tutto questo. 🙁

    Vedi gli articoli di Wikipedia:

    • heapsort
    • Heap binario

    Per quanto riguarda le prestazioni, si potrebbe voler considerare un algoritmo di ordinamento di confronto a stringhe più generale.

    Attualmente finisci per toccare ogni elemento di ogni stringa, ma puoi fare di meglio!

    In particolare, un burst type è un ottimo adattamento per questo caso. Come bonus, dato che burstsort si basa sui tentativi, funziona in modo ridicolo per le piccole dimensioni dell’alfabeto utilizzate in DNA / RNA, poiché non è necessario creare alcun tipo di nodo di ricerca ternario, hash o altro schema di compressione del nodo trio nel trie implementazione. I tentativi possono essere utili anche per il tuo objective finale simile a un suffisso.

    Un’implementazione decente per scopi generali di burstsort è disponibile su source forge su http://sourceforge.net/projects/burstsort/ – ma non è sul posto.

    A scopo di confronto, l’implementazione C-burstsort coperta dai benchmark http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf 4-5x più veloce rispetto a quicksort e radix sort per alcuni carichi di lavoro tipici.

    Potresti provare a usare un trie . L’ordinamento dei dati sta semplicemente iterando il set di dati e inserendolo; la struttura è ordinata in modo naturale, e si può pensare ad essa come simile a un albero B (eccetto che fare confronti, si usa sempre puntatori indiretti).

    Il comportamento del caching favorirà tutti i nodes interni, quindi probabilmente non migliorerai su questo; ma puoi anche manipolare il fattore di ramificazione del tuo trie (assicurati che ogni nodo si adatti a una singola linea di cache, alloca i nodes simili a un heap, come un array contiguo che rappresenta un attraversamento di ordine di livello). Poiché i tentativi sono anche strutture digitali (O (k) insert / find / delete per elementi di lunghezza k), dovresti avere prestazioni competitive per un ordinamento di tipo radix.

    Vorrei creare una rappresentazione a pugno pieno delle stringhe. Si sostiene che Burstsort abbia una localizzazione molto migliore rispetto ai tipi di radix, mantenendo l’utilizzo di spazio aggiuntivo verso il basso con tentativi di burst al posto di tentativi classici. La carta originale ha misurazioni.

    Dovrai dare un’occhiata all’elaborazione della sequenza del genoma su larga scala di Drs. Kasahara e Morishita.

    Le stringhe composte dalle quattro lettere nucleotidiche A, C, G e T possono essere codificate in modo specifico in numeri interi per un’elaborazione molto più rapida. Ordinamento Radix è tra i molti algoritmi discussi nel libro; dovresti essere in grado di adattare la risposta accettata a questa domanda e vedere un grande miglioramento delle prestazioni.

    ” L’ordinamento digitale senza spazio extra ” è un documento che risolve il problema.

    Radix-Sort non è sensibile alla cache e non è l’algoritmo di ordinamento più veloce per i set di grandi dimensioni. Puoi guardare:

    • ti7qsort . ti7qsort è l’ordinamento più veloce per numeri interi (può essere utilizzato per stringhe di dimensioni minime fisse).
    • QSORT in linea
    • Ordinamento delle stringhe

    Puoi anche utilizzare la compressione e codificare ciascuna lettera del tuo DNA in 2 bit prima di archiviarla nell’array di ordinamento.

    L’ordinamento radix di MSR di dsimcha sembra carino, ma Nils si avvicina al cuore del problema con l’osservazione che la localizzazione della cache è ciò che ti sta uccidendo a grandi dimensioni dei problemi.

    Suggerisco un approccio molto semplice:

    1. Stima empiricamente la dimensione maggiore m per la quale un ordinamento di radix è efficiente.
    2. Leggere i blocchi di m elementi alla volta, radix ordinarli e scriverli (su un buffer di memoria se si dispone di memoria sufficiente, ma altrimenti di file), fino a quando non si esaurisce l’input.
    3. Mescola i blocchi ordinati risultanti.

    Mergesort è l’algoritmo di ordinamento più cache-friendly di cui sono a conoscenza: “Leggi l’elemento successivo da entrambi gli array A o B, quindi scrivi un elemento nel buffer di output”. Funziona in modo efficiente su unità nastro . Richiede 2n spazio per ordinare n elementi, ma la mia scommessa è che la località cache molto migliorata che vedrai renderà tutto ciò non importante – e se stavi usando un ordinamento radix non sul posto, avevi bisogno di quello spazio extra Comunque.

    Si noti infine che il mergesort può essere implementato senza ricorsione, e infatti farlo in questo modo rende chiaro il vero pattern di accesso alla memoria lineare.

    Sembra che tu abbia risolto il problema, ma per la cronaca, sembra che una versione di un ordinamento radix utilizzabile sul posto sia “Ordinamento bandiera americana”. È descritto qui: Engineering Radix Sort . L’idea generale è di eseguire 2 passaggi su ciascun personaggio: per prima cosa conta quanti ne hai, in modo da poter suddividere l’array di input in bin. Quindi ripetere di nuovo, scambiando ogni elemento nel cestino corretto. Ora ordina ricorsivamente ciascun contenitore nella posizione del prossimo carattere.

    In primo luogo, pensa alla codifica del tuo problema. Sbarazzati delle stringhe, sostituiscile con una rappresentazione binaria. Usa il primo byte per indicare la lunghezza + la codifica. In alternativa, utilizzare una rappresentazione di lunghezza fissa a un limite di quattro byte. Quindi il tipo di radix diventa molto più semplice. Per un ordinamento digitale, la cosa più importante è non avere la gestione delle eccezioni nel punto caldo del ciclo interno.

    OK, ho pensato un po ‘di più al problema dei 4 nani. Vuoi una soluzione come un Judy tree per questo. La prossima soluzione può gestire stringhe di lunghezza variabile; per la lunghezza fissa basta rimuovere i bit di lunghezza, che in realtà rende più facile.

    Assegna blocchi di 16 puntatori. Il bit meno significativo dei puntatori può essere riutilizzato, poiché i blocchi saranno sempre allineati. Si potrebbe desiderare uno speciale allocatore di memoria per esso (suddividere l’archiviazione di grandi dimensioni in blocchi più piccoli). Esistono diversi tipi di blocchi:

    • Codifica con 7 bit di lunghezza di stringhe di lunghezza variabile. Quando si riempiono, li sostituisci con:
    • La posizione codifica i prossimi due caratteri, hai 16 puntatori ai blocchi successivi, che terminano con:
    • Codifica bitmap degli ultimi tre caratteri di una stringa.

    Per ogni tipo di blocco, è necessario memorizzare diverse informazioni negli LSB. Poiché hai stringhe di lunghezza variabile, devi memorizzare anche end-of-string e l’ultimo tipo di blocco può essere utilizzato solo per le stringhe più lunghe. I 7 bit di lunghezza dovrebbero essere sostituiti da meno man mano che ti addentri nella struttura.

    Ciò fornisce una memoria ragionevolmente veloce e molto efficiente in termini di memoria delle stringhe ordinate. Si comporterà un po ‘come un trie . Per farlo funzionare, assicurati di build abbastanza test unitari. Vuoi la copertura di tutte le transizioni di blocco. You want to start with only the second kind of block.

    For even more performance, you might want to add different block types and a larger size of block. If the blocks are always the same size and large enough, you can use even fewer bits for the pointers. With a block size of 16 pointers, you already have a byte free in a 32-bit address space. Take a look at the Judy tree documentation for interesting block types. Basically, you add code and engineering time for a space (and runtime) trade-off

    You probably want to start with a 256 wide direct radix for the first four characters. That provides a decent space/time tradeoff. In this implementation, you get much less memory overhead than with a simple trie; it is approximately three times smaller (I haven’t measured). O(n) is no problem if the constant is low enough, as you noticed when comparing with the O(n log n) quicksort.

    Are you interested in handling doubles? With short sequences, there are going to be. Adapting the blocks to handle counts is tricky, but it can be very space-efficient.