Utilizzo di Hash Maps per rappresentare una fonte di dati estremamente grande

Question

Ho un set di dati possibile molto grande che sto provando a visualizzare subito. L'insieme stesso è costituito da centinaia di migliaia di segmenti, ognuno dei quali è mappato su un ID.

Ho ricevuto una seconda fonte di dati che fornisce maggiori informazioni in tempo reale per ogni segmento, ma l'id non corrisponde all'ID che ho.

Ho una mappatura 1: 1 dell'id dati (stringhe di 9 caratteri) sull'id corrente (numeri interi lunghi). Il problema è che ci sono molti ID e che i dati che arrivano non hanno un ordine specifico.

La soluzione che mi è venuta in mente è quella di avere una mappa hash che mappasse le stringhe sull'ID della strada. Il problema è che non so se la mappa hash sarà abbastanza efficiente da contenere tutte le 166k voci di dati.

Qualcuno ha suggerimenti e / o algoritmi di hashing che posso usare per questo?

Answer 1

Se hai a che fare solo con centinaia di migliaia di punti dati, probabilmente non sarà un problema seguire la strada ingenua e limitarti a seguire una mappa hash.

Anche se hai 500.000 stringhe di 9 caratteri e un uguale numero di lunghi , che rimangono solo 16 byte per elemento o 8.000.000 di byte in totale. Anche se lo raddoppi per overhead, 16 MB non sono quasi troppo grandi per essere in memoria contemporaneamente.

Fondamentalmente, prova prima il modo semplice e preoccupati solo quando la tua profilazione ti dice che sta impiegando troppo tempo.

Answer 2

Judy Arrays sono progettati per questo tipo di cose: " I vantaggi chiave di Judy sono scalabilità, alte prestazioni ed efficienza della memoria. [...] Judy può sostituire molte strutture di dati comuni, come array, array sparsi, tabelle hash, alberi B, alberi binari, liste lineari, skiplist, altri algoritmi di ordinamento e ricerca e funzioni di conteggio. & Quot;

Answer 3

Poiché i commenti sulla domanda indicano che la preoccupazione principale potrebbe essere l'utilizzo della memoria:

• Utilizza un raggruppamento o altro allocatore ottimizzato per piccoli oggetti ; supponendo che tu abbia accesso a boost probabilmente troverai una sostituzione drop-in in Pool . L'uso di un allocatore di oggetti di piccole dimensioni migliore è probabilmente la più grande vincita di memoria che troverai.
• Se sai che le tue stringhe sono a larghezza fissa, potresti voler assicurarti di allocare solo spazio sufficiente per memorizzarle. Ad esempio, una struttura racchiusa in un carattere a lunghezza fissa [] con un operatore di confronto personalizzato può funzionare meglio di uno std :: string. std :: string viene fornito con un'allocazione dinamica aggiuntiva (e utilizza lo spazio per il puntatore corrispondente) e un sovraccarico di tracciamento di dimensioni e capacità. (In genere, prova a ridurre il numero di allocazioni che restano ferme; riduce le spese generali.)
• (Supponendo STL) Osserva la differenza generale tra std :: map e std :: unordered_map (quest'ultima potrebbe non essere disponibile al momento); una std :: map basata su RBtree potrebbe essere abbastanza vicina alle caratteristiche di prestazione della ricerca del tuo "hashmap" e può (o meno) essere più efficiente in termini di memoria a seconda dell'implementazione della libreria standard.

Quale percorso prendi dovrebbe essere influenzato dalle informazioni che puoi raccogliere: prova a ottenere un'immagine del numero di allocazioni e allo scopo di allocare le dimensioni / l'allineamento.

Puoi strumentare il tuo allocatore o inserire alcuni elementi e vedere come stai rispetto a come pensi che dovresti fare in termini di utilizzo della memoria.

Answer 4

Poiché le tue stringhe sono conosciute in anticipo e hanno una lunghezza fissa, teoricamente e praticamente la soluzione migliore è un hash perfetto . È possibile utilizzare cmph per generarlo.

Secondo Wikipedia, le tue chiavi richiederebbero 2,5 bit / chiave, o circa 50 KB. È trascurabile rispetto ai 664 KB per i valori.

Answer 5

Sebbene 166k voci di dati siano IMO piuttosto piccole, puoi dare un'occhiata a google-sparsehash