Il mio progetto prevede la convalida e la normalizzazione degli indirizzi e-mail in questo formato
[userpart] @ [domainpart]. [TLD]
Dopo la convalida sintattica dell'indirizzo, [tld] viene verificato per esistere, altrimenti la convalida fallisce.
Dopo la convalida, [userpart] e [domainpart] sono normalizzati in un ID numerico a 32 bit chiamato [partid] (uno per ogni parte), partid e la stringa della parte sono memorizzati in modo permanente sul disco quando vengono scoperte nuove stringhe. 4 byte sembra il più sensato per ciascuno come 3 byte non è abbastanza (ci sono circa 200 milioni di nomi di dominio registrati proprio ora).
Per elaborare rapidamente elenchi di nuove e-mail, ho utilizzato gli array Judy (JudySL per l'esattezza, link ), dove la stringa di parti è mappata all'ID parte.
Ho usato Judy Arrays perché so come usarli e generalmente funzionano bene, anche se non sono thread safe che è un leggero inconveniente (io uso mutex per aggirare questo). Non ci sono collisioni che otterrei con una tabella hash ... che riduce in qualche modo la complessità.
Tuttavia sembra che occupino una quantità di memoria molto più ampia di quella che vorrei, quindi la mia domanda è: cosa suggeriresti come migliore metodo di archiviazione?
Esempio di caso:
- Sistema a 64 bit (basato su Debian)
- 150.000.000 "parti", con una media di circa 8 byte ciascuna, 12 byte totali quando include il partid
- ~ 1,67 GB per quei dati in sé
- ~ 5,1 GB utilizzato da Judy
- Forse vale la pena notare che le e-mail vengono valutate dopo essere state convertite in formato punycode.
- L'input verrebbe in elenchi che variano tra le righe 10K e 1M
- Inserisce su richiesta, quando viene trovata una nuova [parte], ++ partid viene assegnato come partid e partid, parte viene scritta sul disco
- Nessuna eliminazione richiesta, solo inserimenti e ricerche
Quindi ho bisogno di circa 3 volte più memoria dello spazio su disco per convertire [~ 8-byte-string] in un int.
Esistono strutture dati migliori (*) che dovrei considerare?
(* meglio, spero che sia ragionevolmente veloce, con un footprint di memoria più piccolo e preferibilmente qualcosa di pre-scritto come una libreria ...)
Aggiorna
Il TL; DR della mia domanda originale ... conversione di una stringa di lunghezza variabile in INT a 32 bit
In senso stretto l'utente parte è case sensitive ma da quello che capisco l'implementazione standard è ignorare il caso. In tal caso (nessun gioco di parole), ci sono 56 caratteri validi nella parte di dominio punycoded, o 6 bit di valore.
Sto pensando di poter sacrificare 1 bit per indicare la conversione diretta di string- > int senza una tabella di ricerca, che consentirà anche la conversione. Il bit verrebbe attivato quando ciò può verificarsi e impedirebbe collisioni con ricerche, lasciando 31 bit per i dati e 2 ^ 31 ID per tutte le altre parti del dominio che non si adattano.
Stavo scherzando con codici di lunghezza 4-5-6 bit di lunghezza fissa basati sul carattere meno frequente, ma la codifica di Huffman sembrerebbe (ovviamente?) vincere a lungo termine ed evitare un secondo passaggio della stringa di input . Ecco alcuni dati basati sulla distribuzione del carico su quelle parti da 150 m.
Huffman riesce ad avere yahoo, gmail e persino hotmail spremuti in 31 bit, il che è eccellente. Il 6,1% di tutte le parti può essere mappato in questo modo.
Con la stessa codifica di Huffman, un ulteriore 70,5% può essere mappato a 63 bit che consentirebbero un elenco di valori chiave int e gt; a lunghezza fissa. Questo dovrebbe essere salvato in memoria (proverò a ripeterlo)
Questo lascia meno del 25% di tutte le parti da mappare ancora.
Questo nuovo layout dovrebbe essere di grande aiuto per il salvataggio in memoria, grazie per i suggerimenti fino ad ora.