Mappa stringa-stringa efficiente in termini di memoria in Python (o C)

https://stackoverflow.com/questions/4026359

26-09-2019
|

Domanda

Ho bisogno di una struttura dati efficiente in termini di memoria per archiviare circa un milione di coppie chiave-valore, dove le chiavi sono stringhe di circa 80 byte e i valori sono stringhe di circa 200 byte, la dimensione totale di chiave e valore è di circa 280 MB.Ho anche bisogno di una ricerca efficiente del valore per chiave, preferibilmente una mappa hash.Il sovraccarico della memoria dovrebbe essere il minimo possibile, ad es.per 280 MB di dati utili, la struttura dati non deve utilizzare più di 300 MB di memoria virtuale (inclusi malloc() spese generali e tutto il resto).Lo schema di utilizzo è il seguente:iniziamo con una struttura dati vuota e la popoliamo gradualmente, senza mai cambiare le chiavi e senza mai modificare la lunghezza dei valori.Inoltre, la struttura dei dati può supportare la modifica della lunghezza dei valori, a scapito di un sovraccarico del valore del 100% (il che significa che per x byte di valore, x byte potrebbero essere temporaneamente sprecati nello spazio buffer inutilizzato).

Ho bisogno di un modulo Python puro, o di un modulo Python integrato, o di un'implementazione C preferibilmente con collegamenti (C)Python.Preferirei che fosse possibile serializzare l'intera struttura dei dati su disco e rileggerla molto rapidamente.

Giusto per dimostrare che è possibile un sovraccarico così ridotto, ho creato un design semplice con indirizzamento aperto, la tabella hash di 1,25 milioni di elementi contenente puntatori da 4 byte a blocchi di dati da 1 MB, i blocchi di dati contenenti la chiave e la lunghezza del valore come varianti base-128.Questo design ha una limitazione importante:non consente di rimuovere o modificare coppie senza sprecare la loro area di memoria.Secondo i miei calcoli con 1 milione di coppie chiave-valore da 280 byte ciascuna, il sovraccarico è inferiore al 3,6% (10 080 000 byte).I limiti sopra indicati sono più generosi e consentono 20.000.000 di byte di sovraccarico.

Ho appena trovato http://www.pytables.org/ , che fornisce un accesso rapido e un imballaggio dei dati efficiente in termini di memoria.Devo esaminarlo più da vicino per verificare se soddisfa le mie esigenze.

Soluzione 10

Dal momento che non sono riuscito a trovare alcuna soluzione esistenti che affolleranno la memoria saldamente, ho deciso di implementarlo in C per me stesso. Vedere il mio design con indirizzamento aperto nella questione.

Altri suggerimenti

Ok, l'approccio allo sporco semplice.

Usa un dizionario Python per la struttura dei dati. Ho riempito un dizionario Python con 1 milione di coppie chiave-valore casuale in cui la chiave era 80 caratteri e il valore di 200 caratteri. Ci sono voluti 360.844 Kb sul mio computer, che è al di fuori della vostra specifica di non più di 300 MB, ma io lo offrono come una soluzione in ogni caso, perché è ancora abbastanza efficiente della memoria.

Questa fallisce anche la vostra esigenza di avere un'API C. Io non sono sicuro perché avete bisogno di C, ma come la questione è aggiunto Python e manca un tag C, ti offro il puro Python per vedere se è solo potrebbe andare bene il disegno di legge.

Per quanto riguarda la persistenza. Utilizzare il modulo cPickle. E 'molto veloce e, ancora una volta, la sporcizia-semplice. Per salvare il dizionario:

cPickle.dump(mydict, "myfile.pkl")

Per ricaricare il dizionario:

mydict = cPickle.load("myfile.pkl")

Una seconda idea sporco semplice è quello di utilizzare il modulo shelve, che è fondamentalmente dizionario Python basata su disco. Memoria overhead è molto basso (è tutto su disco). Ma è anche molto più lento.

Martijn menzionato questo in un commento (non so perché la gente commento con le risposte), ma sono d'accordo: l'uso SQLite. Si dovrebbe dare una prova e vedere se soddisferà le vostre esigenze.

Se non si prevede di avere una grande quantità di eliminazioni, allora questo non è così difficile. Elimina portano alla frammentazione.

È inoltre necessario impegnarsi per una chiave di lunghezza fissa. Lei ha parlato di 80 byte. Sono le chiavi permesso di duplicare? In caso contrario, è ancora più facile.

Quindi, ecco quello che fate.

È possibile creare una vasta gamma di:

struct {
    char value[80];
    char *data;
} key;

E si mantiene questo array ordinato.

Se i tasti possibile duplicare, quindi è necessario:

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

(La mia C è arrugginito, ma questa è l'essenza di esso) Quest'ultimo ha ogni punta chiave per una lista concatenata di valori.

Poi una ricerca è una semplice ricerca binaria. Il "dolore" è a mantenere questo allineamento e l'inserimento / cancellazione dei tasti. Non è così doloroso come sembra, ma fa risparmiare un sacco di memoria, in particolare su sistemi a 64 bit.

Che cosa si vuole ridurre il numero di puntatori. I puntatori sono costosi quando si hanno un sacco di strutture piene di puntatori. In un sistema a 64 bit, un puntatore è di 8 byte. Così, per un singolo puntatore, ci va 8MB di memoria di vostro budget.

Quindi, la spesa è nella costruzione della matrice, la copia e la compattazione di memoria (se si "sapere" si avrà un milione di righe e possono impegnarsi a che, poi malloc (1000000 * sizeof (chiave)) subito,' ll risparmiare un po 'di copia durante l'espansione).

Ma non abbiate paura, una volta che è installato e funzionante, le prestazioni sono abbastanza buone. CPU moderne sono in realtà abbastanza bravo a copiare 100M blocchi di memoria intorno.

Proprio come un a parte, ho appena fatto qualcosa di molto simile a questo in Java. Su un 64 bit JVM, una mappa con le voci 25M è 2G di RAM. La mia soluzione (utilizzando tecniche simili a questo) ha a circa 600 m). Java utilizza più puntatori di C, ma la premessa è la stessa.

Hai provato a usare un dict semplice? La maggior parte dei dati è nelle stringhe, quindi l'overhead potrebbe adattarsi all'interno le vostre esigenze.

È possibile utilizzare la sha1 della chiave invece della chiave stessa. Se le chiavi sono uniche, quindi l'hash sha1 dei tasti è probabile, anche. Esso fornisce un risparmio di memoria per cercare di squittio sotto il vostro limite.

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

Sulla mia casella di Ubuntu, questa supera fuori a 304 MB di memoria di:

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

Abbastanza vicino? E 'di pitone, non C.

Più tardi: anche, se i dati sono un po 'ridondante, è possibile gzip i valori. E 'un tempo rispetto spazio trade-off.

Usare SQLite è una buona idea.Una rapida implementazione può dire se lo sei abbastanza veloce con poco sforzo.

Se decidi di doverlo creare da solo, ti consiglio quanto segue:

Quanto bene puoi prevedere il numero di coppie o un limite superiore per questo?
Con quanta precisione puoi prevedere la dimensione totale dei dati o un limite superiore?

Assegnatore dell'arena per stringhe e nodi.(Di solito, lavorerai su un elenco di arene, quindi non devi prevedere la dimensione totale).

L'allineamento dipende dai tuoi algoritmi, in linea di principio potresti comprimerlo a tenuta di byte e l'unico sovraccarico è la tua sovraallocazione, che influisce solo in minima parte sul tuo set di lavoro.

Tuttavia, se devi eseguire cmp/copy ecc.operazioni su queste stringhe, ricorda che con le seguenti garanzie, puoi spremere un po' o molto da queste operazioni sulle stringhe:

tutti gli elementi sono allineati alle parole della CPU
tutti i byte pad sono (ad esempio) 0
puoi leggere tranquillamente "oltre" la fine di una stringa purché non attraversi il confine della CPU

Tabella hash per l'indice.Funzionerebbe anche un dizionario, ma avrebbe senso solo se il potenziale degrado/rimodellamento fosse un problema serio.Non conosco alcuna implementazione della tabella hash "stock" per C, ma dovrebbe essercene una, giusto?Giusto?Basta sostituire le allocazioni con le chiamate all'allocatore dell'arena.

Località della memoria

Se puoi garantire che la ricerca non richiederà mai una stringa che non è nella mappa, dovresti archiviare le chiavi in un'arena separata, poiché sono necessarie solo in caso di collisioni di hash.Ciò può migliorare significativamente la località della memoria.(In tal caso, se mai avessi un tavolo "finale", potresti persino copiare le chiavi in collisione in una nuova arena e buttare via tutte le altre.I benefici che ne derivano sono probabilmente marginali, però.)

La separazione può aiutare o danneggiare, a seconda dei modelli di accesso.Se in genere utilizzi il valore una volta dopo ogni ricerca, averli in coppia nella stessa arena è fantastico.Se ad es.cerca alcune chiavi, quindi usa i loro valori ripetutamente, le arene separate hanno senso.

Se devi supportare "caratteri divertenti" / Unicode, normalizza le stringhe prima di memorizzarle.

Si potrebbe utilizzare il modulo struct per il confezionamento di dati binari e scompattarlo in caso di necessità. È possibile implementare un efficiente dello storage di memoria utilizzando questo approccio. Credo che l'accesso sarebbe un dolore.

http://docs.python.org/library/struct.html

Apache Portable Runtime (aka APR) ha una tabella di hash c-based. È possibile consultare la documentazione a http://apr.apache.org/docs/apr/ 0.9 / group_ aprile _hash.html

Con apr_hash_t tutto quello che negozio è void *. Quindi ti dà il pieno controllo su valori. Quindi, se si vuole si può memorizzare puntatore a un blocco di 100 byte invece di lunghezza effettiva della stringa.

Judy dovrebbe essere memoria-efficiente: http://judy.sourceforge.net/
(Parametri di riferimento: http://www.nothings.org/computer/judy/ , vedere " dati Struttura Size ").
Vedi anche: http://www.dalkescientific.com/Python/PyJudy.html

Inoltre,

Per tasti di una dimensione fissa c'è http://panthema.net/2007/stx-btree / in C ++ (sono sicuro che con un costume wrapper C può essere utilizzato da CPython). Se il set di dati lo consente, è possibile memorizzare le chiavi di lunghezza variabile nel valore e utilizzare un hash o un prefisso della chiave di lunghezza variabile come la chiave di lunghezza fissa.

La stessa logica vale per http://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and-time.html e http://code.google.com/p/sparsehash/ - istead di utilizzare un pesante std :: string come una chiave, usare un 32 bit o chiave intero a 64 bit, rendendo in qualche modo dalla vera chiave di lunghezza variabile.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow