modo efficiente per contenere ed elaborare un grande dict in memoria in python

Question

Come ho fatto un po 'di test, un dt di python int => int (valore diverso) di 30 milioni di elementi può facilmente mangiare> 2G di memoria sul mio mac. Dal momento che lavoro con solo int a int dict, esiste una soluzione migliore rispetto all'utilizzo di python dict?

Alcuni requisiti di cui ho bisogno sono,

1. più efficiente della memoria in possesso di decine di milioni di livello di int a int articoli
2. metodi dict di base come il recupero valore chiave e l'iterazione tutti gli elementi
3. facile puntate a stringa/binario sarebbe un plus

Update, 4. facile da ottenere sottoinsieme dal dato le chiavi, come d.fromkeys ([...])

Grazie.

Answer 1

La soluzione basata su Judy-array sembra l'opzione che dovrei esaminare. Sto ancora cercando una buona implementazione che possa essere utilizzata da Python. Aggiornerà più tardi.

Update,

finalmente sto sperimentando un allineamento involucro Judy a http://code.google.com/p/py-judy/. Non c'è alcun documento lì, ma ho cercato di trovare i suoi metodi semplicemente da dir (...) il suo pacchetto e oggetto, tuttavia funziona.

Lo stesso esperimento mangia ~ 986 MB a ~ 1/3 di dict standard utilizzando judy.JudyIntObjectMap. Fornisce anche JudyIntSet che in alcuni scenari speciali salverà molta più memoria in quanto non ha bisogno di fare riferimento a qualsiasi oggetto Python reale come valore di confronto con JudyIntObjectMap.

(come testato ulteriormente come di seguito, JudyArray utilizza semplicemente diversi MB a decine di MB, la maggior parte di ~ 986MB viene effettivamente utilizzato da oggetti di valore nello spazio di memoria Python.)

Ecco po 'di codice se ti aiuta per voi,

>>> import judy 
>>> dir(judy) 
['JudyIntObjectMap', 'JudyIntSet', '__doc__', '__file__', '__name__', '__package__'] 
>>> a=judy.JudyIntObjectMap() 
>>> dir(a) 
['__class__', '__contains__', '__delattr__', '__delitem__', '__doc__', '__format__', '__getattribute__', '__getitem__', '__hash__', '__init__', '__iter__', '__len__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', '__value_sizeof__', 'by_index', 'clear', 'get', 'iteritems', 'iterkeys', 'itervalues', 'pop'] 
>>> a[100]=1 
>>> a[100]="str" 
>>> a["str"]="str" 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
KeyError: 'non-integer keys not supported' 
>>> for i in xrange(30000000): 
...  a[i]=i+30000000 #finally eats ~986MB memory 
... 

Update,

ok, un JudyIntSet di 30M int come testato.

>>> a=judy.JudyIntSet() 
>>> a.add(1111111111111111111111111) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
ValueError: we only support integers in the range [0, 2**64-1] 

Si utilizza totalmente solo 5.7MB memorizzare 30M sequenziale int array [0,30000000) che può dovuto alla compressione automatica di JudyArray. Sopra 709 MB è bcz ho usato gamma (...) invece di xrange più corretto (...) per generare i dati.

Quindi la dimensione del core JudyArray con 30M int è semplicemente ignorabile.

Se qualcuno conosce un'implementazione di wrapper Judy Array più completa, fatemelo sapere, poiché questo wrapper include solo JudyIntObjectMap e JudyIntSet. Per int-int dict, JudyIntObjectMap richiede ancora un vero oggetto python. Se facciamo solo counter_add e impostiamo i valori, sarebbe una buona idea memorizzare int dei valori nello spazio C piuttosto che usare l'oggetto python. Spero che qualcuno sia interessato a crearne o introdurne uno:)

Answer 2

Se sapessimo un po 'di più su come sarebbe usato potrebbe essere più facile suggerire buone soluzioni. Si dice che si desidera recuperare i valori per chiave e iterare su tutti, ma nulla se è necessario inserire/eliminare i dati.

Un modo abbastanza efficiente di memorizzazione dei dati è con il modulo array. Se non hai bisogno di inserire/rimuovere dati, potresti semplicemente avere due array. La matrice "chiave" sarebbe stata ordinata e si potrebbe fare una ricerca binaria per la chiave giusta. Quindi devi semplicemente scegliere il valore dalla stessa posizione nell'altro array.

Si potrebbe facilmente racchiuderlo in una classe che si comporta in modo simile. Non so se ci sia una soluzione pronta per questo da qualche parte, ma non dovrebbe essere terribilmente difficile da implementare. Questo dovrebbe aiutarti ad evitare di avere molti oggetti Python che consumano memoria.

Ma potresti avere altri requisiti che rendono questa soluzione poco pratica/impossibile.

Answer 3

Ci sono almeno due possibilità:

array

Si potrebbe provare a utilizzare due array. Uno per le chiavi e uno per i valori in modo tale indice (chiave) == indice (valore)

Aggiornamento 2017-01-05: utilizza numeri interi a 4 byte nell'array.

Un array utilizza meno memoria. Su una macchina FreeBSD a 64 bit con python compilato con clang, una matrice di 30 milioni di interi utilizza circa 117 MiB.

Questi sono i comandi Python che ho usato:

Python 2.7.13 (default, Dec 28 2016, 20:51:25) 
[GCC 4.2.1 Compatible FreeBSD Clang 3.8.0 (tags/RELEASE_380/final 262564)] on freebsd11 
Type "help", "copyright", "credits" or "license" for more information. 
>>> from array import array 
>>> a = array('i', xrange(30000000)) 
>>> a.itemsize 
4 

Dopo l'importazione di array, ps rapporti:

USER  PID %CPU %MEM VSZ RSS TT STAT STARTED TIME COMMAND 
rsmith 81023 0.0 0.2 35480 8100 0 I+ 20:35  0:00.03 python (python2.7) 

dopo aver effettuato la matrice:

USER  PID %CPU %MEM VSZ RSS TT STAT STARTED TIME COMMAND 
rsmith 81023 29.0 3.1 168600 128776 0 S+ 20:35  0:04.52 python (python2.7) 

The Resident Set Size è segnalato in 1 unità KiB, quindi (128776 - 8100)/1024 = 117 MiB

Con la comprensione delle liste è possibile ottenere facilmente un elenco di indici in cui la chiave soddisfa una determinata condizione. È quindi possibile utilizzare gli indici in tale elenco per accedere ai corrispondenti valori ...

NumPy

Se avete NumPy a disposizione, utilizzando tale è più veloce, ha un sacco più funzioni ed e usa un po 'meno RAM:

Python 2.7.5 (default, Jun 10 2013, 19:54:11) 
[GCC 4.2.1 Compatible FreeBSD Clang 3.1 ((branches/release_31 156863))] on freebsd9 
Type "help", "copyright", "credits" or "license" for more information. 
>>> import numpy as np 
>>> a = np.arange(0, 30000000, dtype=np.int32) 

Da ps: 6700 KiB dopo l'avvio di Python, 17400 KiB dopo l'importazione NumPy e 134.824 KiB dopo aver creato l'array. Sono circa 114 MiB.

Inoltre, numpy supporta record arrays;

Python 2.7.5 (default, Jun 10 2013, 19:54:11) 
[GCC 4.2.1 Compatible FreeBSD Clang 3.1 ((branches/release_31 156863))] on freebsd9 
Type "help", "copyright", "credits" or "license" for more information. 
>>> import numpy as np 
>>> a = np.zeros((10,), dtype=('i4,i4')) 
>>> a 
array([(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), 
     (0, 0), (0, 0)], 
     dtype=[('f0', '<i4'), ('f1', '<i4')]) 
>>> a.dtype.names 
('f0', 'f1') 
>>> a.dtype.names = ('key', 'value') 
>>> a 
array([(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), 
     (0, 0), (0, 0)], 
     dtype=[('key', '<i4'), ('value', '<i4')]) 
>>> a[3] = (12, 5429) 
>>> a 
array([(0, 0), (0, 0), (0, 0), (12, 5429), (0, 0), (0, 0), (0, 0), (0, 0), 
     (0, 0), (0, 0)], 
     dtype=[('key', '<i4'), ('value', '<i4')]) 
>>> a[3]['key'] 
12 

Qui è possibile accedere ai tasti e ai valori separatamente;

>>> a['key'] 
array([ 0, 0, 0, 12, 0, 0, 0, 0, 0, 0], dtype=int32) 

Answer 4

Un'altra risposta aggiunta se quello che vuoi è solo un contatore simile a un dizionario che è facile da usare.

High performance Counter object from Python standard library