Modo memoria efficiente per memorizzare le stringhe

Presupponendo che disponga di milioni di stringhe. Ogni stringa ha un valore int. Voglio recuperare questo valore inserendo una stringa, ma non voglio memorizzare tutte queste stringhe perché occupano molto spazio. Non riesco a utilizzare la tabella hash perché è necessario memorizzare tutte o almeno molte stringhe in memoria. Quindi, qual è la buona struttura dati per il mio caso (non ho bisogno di aggiungere o eliminare stringhe, ho già preparato i dati e ho letto solo operazioni consentite)Modo memoria efficiente per memorizzare le stringhe

fonte

2013-03-29 Neir0

Che linguaggio di programmazione? Inoltre, ci sono molte stringhe identiche? –

@ jdv-Jan de Vaan Nessuna stringa è unica. Non penso che la mia domanda sia specifica per la lingua, ma preferisco il C#. – Neir0

Non è chiaro cosa devi fare. Hai solo bisogno di estrarre quei numeri e salvare in un altro file? O hai bisogno di eseguire alcuni calcoli con loro? Va bene se l'ordine di input non viene mantenuto? –

Il tuo motivo per non usare una tabella hash non suono valido in base alle informazioni limitate nella tua domanda attualmente. È abbastanza efficiente se implementato bene. Può anche avere il vantaggio di non sprecare memoria memorizzando stringhe duplicate se questo è accettabile per le tue esigenze, riducendo ulteriormente il consumo di memoria se sono possibili stringhe duplicate.

Si potrebbe anche archiviare un modulo compresso di ogni stringa nella tabella hash se si è creativi su come si eseguono le ricerche. Quanto sono lunghe le stringhe?

fonte

2013-03-29 15:26:23

La lunghezza media è di 10 lettere. Almeno io non posso memorizzare stringhe con un solo oggetto del mio hashtable. Quindi penso che esista un modo per rafforzare questo approccio. – Neir0

Utilizzare un trie per evitare la memorizzazione di stringhe comuni ..

fonte

2013-03-29 15:27:10

Trie è una buona idea, ma è molto più lenta di quella hashtable. – Neir0

@larsmans Heh!Ho pensato a qualcosa di simile per massimizzare l'efficienza di un pattern regex molto grande, anche se ora mi chiedo se questo viene fatto automaticamente quando viene analizzata una stringa regex. Bello sapere come si chiama. – Nolo

una tabella hash non è un modo efficiente di memoria per memorizzare stringhe, anche se – argentage

Si consiglia di guardare il Judy tree, che è stato progettato per essere sia veloce e compatto, e dispone di una versione progettata per le chiavi di stringa. La sua implementazione è disponibile su sourceforge.

fonte

2013-03-29 23:55:36 comingstorm

Se è possibile pre-elaborare l'elenco di parole, osservare gli hash perfetti, ad esempio CMPH. (gperf è un altro, ma sembra ottimizzato per i set di dati più piccoli.)

Dalla documentazione CMPH:

Una funzione hash perfetta associa un insieme statico di n chiavi in una serie di numeri interi m senza collisioni, dove m è maggiore o uguale a n. Se m è uguale a n, la funzione è chiamata minima.

...

La Biblioteca CMPH racchiude le più recenti e più efficienti algoritmi in un facile da usare, la produzione di qualità, API veloce. La libreria è stata progettata per funzionare con voci grandi che non possono essere contenute nella memoria principale. È stato utilizzato con successo per la costruzione di funzioni hash minime per set con più di 100 milioni di chiavi, ...

fonte

2013-03-30 00:17:48

Modo memoria efficiente per memorizzare le stringhe

risposta

Problemi correlati