Quale struttura dati dovrei utilizzare per memorizzare i valori hash?

https://stackoverflow.com/questions/1957390

21-09-2019
|

Domanda

Ho una tabella hash che voglio archiviare su disco.L'elenco è simile al seguente:

<16-byte key                   > <1-byte result>
a7b4903def8764941bac7485d97e4f76 04
b859de04f2f2ff76496879bda875aecf 03
etc...

Ci sono 1-5 milioni di voci.Attualmente li sto semplicemente memorizzando in un file, 17 byte per voce moltiplicati per il numero di voci.Quel file è di decine di megabyte.Il mio obiettivo è archiviarli in modo da ottimizzare prima lo spazio su disco e poi il tempo di ricerca.Il tempo di inserimento non è importante.

Qual è il modo migliore per farlo?Vorrei che il file fosse il più piccolo possibile.Anche più file andrebbero bene.Patrizia ci provi?Prova radicale?

Qualunque buon suggerimento riceva, lo implementerò e lo testerò.Pubblicherò qui i risultati affinché tutti possano vederli.

Soluzione

Si può solo ordinare le voci di chiave e fare una ricerca binaria.

chiavi di dimensione fissa e immissioni di dati significa che si può saltare molto rapidamente da una fila all'altra, e memorizzare solo la chiave ed i dati significa che non siete sprecare spazio sul meta-dati.

Non credo che farete meglio lo spazio su disco, e tempi di ricerca sono O (log (n)). tempi di inserzione sono pazzi a lungo, ma lei ha detto che non importava.

Se siete davvero disposti a tollerare tempi di accesso lunghi, fare ordinare la tabella, ma poi pezzo in blocchi di una certa dimensione e comprimerli. Conservare l'offset * e avviare / chiavi fine di ogni blocco in una sezione del file alla partenza. Utilizzando questo schema, è possibile trovare il blocco che contiene la chiave è necessario in un tempo lineare e quindi si esegue una ricerca binaria all'interno del blocco decompresso. Scegliere il blocco size basato su quanto del file che si è disposti a caricare in memoria in una sola volta.

Utilizzando un off lo schema di compressione scaffale (come GZIP) è possibile regolare il rapporto di compressione, se necessario; i file più grandi avranno presumibilmente avere tempi di ricerca più veloci.

Non ho dubbi che il risparmio di spazio sarà poi così grande, come la struttura sembra essere per lo più gli hash. Se essi sono in realtà hash, sono casuali e non comprimere troppo bene. Ordinamento contribuirà ad aumentare il rapporto di compressione, ma non da una tonnellata.

_{* Utilizzare l'intestazione di ricercare l'offset di un blocco per decomprimere e utilizzare.}

Altri suggerimenti

5 milioni di record sono circa 81 MB: accettabili per lavorare con l'array in memoria.

Come hai descritto il problema, si tratta di chiavi più univoche che di valori hash.Prova a utilizzare la tabella hash per accedere ai valori (guarda questo link).

Se c'è un mio malinteso e questo è un vero hash, prova a costruire un secondo livello di hash sopra questo.

La tabella hash può essere organizzata con successo anche su disco (ad es.come file separato).

Aggiunta

La soluzione con buone prestazioni di ricerca e poco sovraccarico è:

Definire la funzione hash, che produce valori interi dalle chiavi.
Ordina i record nel file in base ai valori prodotti da questa funzione
Memorizza gli offset dei file dove inizia ciascun valore hash
Per individuare il valore:
4.1.calcola l'hash con la funzione
4.2.cercare l'offset nel file
4.3.legge i record dal file a partire da questa posizione fino alla chiave trovata o all'offset della chiave successiva non raggiunto o alla fine del file.

Ci sono alcune cose aggiuntive che devono essere puntualizzate:

La funzione hash deve essere veloce per essere efficace
La funzione hash deve produrre valori distribuiti lineari o vicini a quelli
La tabella degli offset dei valori hash può essere inserita in un file separato
La tabella degli offset dei valori hash può essere prodotta dinamicamente con la lettura sequenziale dell'intero file ordinato all'avvio dell'applicazione e archiviata in memoria
al punto 4.3.i record devono essere letti per blocchi, non uno per uno, per essere efficaci.Idealmente legge tutti i valori con hash calcolato in memoria contemporaneamente.

Puoi trovare alcuni esempi di funzioni hash Qui.

Sarebbe il lavoro semplice approccio e memorizzarli in un database SQLite ? Non credo che sarà ottenere qualsiasi piccolo, ma si dovrebbe ottenere ottime prestazioni di ricerca, ed è molto facile da implementare.

Prima di tutto - più file non sono OK se si desidera ottimizzare lo spazio su disco, a causa della dimensione dei cluster - quando si creano file con dimensioni ~ 100 byte, gli spazi del disco diminuisce ogni dimensione del cluster - 2kB ad esempio

In secondo luogo - nel tuo caso vorrei memorizzare tutti tabella nel singolo file binario, ordinate semplicemente ASC da valori byte di chiavi. Vi darà file con lunghezza uguale esattamente a entriesNumber * 17, che è minimo se non si desidera utilizzare l'archiviazione, e in secondo luogo, è possibile utilizzare la ricerca molto veloce con il tempo ~ log2 (entriesNumber), quando si esegue una ricerca per il file di demarcazione chiave in due parti e la chiave sul loro confine con la chiave necessaria a confronto. Se "chiave di confine" è più grande, si prende prima parte del file, se più grande - allora seconda parte. E ancora dividere partecipate in due parti, etc. Quindi sarà necessario circa log2 (entriesNumber) le operazioni di lettura per cercare chiave singola.

La chiave è di 128 bit, ma se si dispone di un massimo di 10 ^ 7 voci, ci vogliono solo 24 bit per indicizzarlo.

Si potrebbe fare una tabella hash, o
Usa in stile Bentley srotolato ricerca binaria (al massimo 24 confronti), come in

Ecco il loop srotolato (con interi a 32 bit).

int key[4];
int a[1<<24][4];

#define COMPARE(key, i) (key[0]>=a[i][0] && key[1]>=a[i][1] && key[2]>=a[i][2] && key[3]>=a[i][3])

i = 0;
if (COMPARE(key, (i+(1<<23))) >= 0) i += (1<<23);
if (COMPARE(key, (i+(1<<22))) >= 0) i += (1<<22);
if (COMPARE(key, (i+(1<<21))) >= 0) i += (1<<21);
...
if (COMPARE(key, (i+(1<<3))) >= 0) i += (1<<3);
if (COMPARE(key, (i+(1<<2))) >= 0) i += (1<<2);
if (COMPARE(key, (i+(1<<1))) >= 0) i += (1<<3);

Come sempre con il design di file, più si conosce (e ci dicono) sulla distribuzione dei dati, meglio è. Partendo dal presupposto che i valori chiave sono distribuiti uniformemente in tutto l'insieme di tutte le chiavi di 16 byte - che dovrebbe essere vero se si archiviano una tabella di hash - Suggerisco una combinazione di ciò che altri hanno già suggerito:

i dati binari, come è offerto in un file binario; non lasciare che il fatto che la rappresentazione semplice delle vostre hash ed i valori sono come stringhe di cifre esadecimali ingannare a pensare che si tratta di dati string;
la dimensione del file è tale che tutta la baracca può essere mantenuto in memoria su qualsiasi PC moderno o server e un sacco di altri dispositivi di troppo;
principali 4 byte di chiavi dividono il set di chiavi possibili in 16 ^ 4 (= 65536) sottoinsiemi; se le chiavi sono uniformemente distribuiti e si dispone di 5x10 ^ 6 voci, che è di circa 76 voci per sottoinsieme; in modo da creare un file con lo spazio per, diciamo, 100 voci per sottoinsieme; poi:
all'offset 0 inizio crei tutte le voci con i principali 4 byte 0x0000; pad al totale di 100 voci (1700 byte credo) con 0s;
all'offset 1700 inizia a scrivere tutte le voci con i principali 4 byte 0x0001, pad,
ripetere fino a quando hai scritto tutti i dati.

Ora la vostra ricerca diventa un calcolo per capire l'offset nel file seguito da una scansione di un massimo di 100 voci per trovare quello che si desidera. Se questo non è abbastanza veloce quindi utilizzare 16 ^ 5 sottoinsiemi, permettendo circa 6 voci per sottoinsieme (6x16 ^ 5 = 6.291.456). Credo che questo sarà più veloce di ricerca binaria - ma è solo un'ipotesi

L'inserimento è un po 'un problema, tocca a voi con la vostra conoscenza dei vostri dati per decidere se le nuove iscrizioni (a) richiedono la ri-ordinamento di un sottoinsieme o (b) possono essere semplicemente aggiunti alla fine del elenco di voci a tale indice (che significa scansione dell'intero sottoinsieme su ogni ricerca).

Se lo spazio è molto importante che si può, naturalmente, eliminare i principali 4 byte dalle vostre voci, dal momento che sono calcolati dal calcolo per l'offset nel file.

Quello che sto descrivendo, non troppo bene, è un tabella hash .

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow