efficiente della memoria int-int dict in Python

Question

ho bisogno di un efficiente della memoria int-int dict in Python che avrebbe sostenuto le seguenti operazioni in O (log n) tempo:

d[k] = v # replace if present 
v = d[k] # None or a negative number if not present 

ho bisogno di tenere ~ Coppie 250M, quindi è davvero deve essere stretto.

Ti capita di conoscere un'implementazione adatta (Python 2.7)?

EDIT Requisito impossibile rimosso e altre assurdità. Grazie, Craig e Kylotan!

---

di riformulare. Ecco un dizionario int-int banale con coppie di 1M:

>>> import random, sys 
>>> from guppy import hpy 
>>> h = hpy() 
>>> h.setrelheap() 
>>> d = {} 
>>> for _ in xrange(1000000): 
...  d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint) 
... 
>>> h.heap() 
Partition of a set of 1999530 objects. Total size = 49161112 bytes. 
Index Count %  Size % Cumulative % Kind (class/dict of class) 
    0  1 0 25165960 51 25165960 51 dict (no owner) 
    1 1999521 100 23994252 49 49160212 100 int 

In media, una coppia di interi utilizza 49 byte.

Ecco un array di interi 2M:

>>> import array, random, sys 
>>> from guppy import hpy 
>>> h = hpy() 
>>> h.setrelheap() 
>>> a = array.array('i') 
>>> for _ in xrange(2000000): 
...  a.append(random.randint(0, sys.maxint)) 
... 
>>> h.heap() 
Partition of a set of 14 objects. Total size = 8001108 bytes. 
Index Count %  Size % Cumulative % Kind (class/dict of class) 
    0  1 7 8000028 100 8000028 100 array.array 

In media, una coppia di numeri interi utilizza 8 byte.

Accetto che 8 byte/coppia in un dizionario sia piuttosto difficile da ottenere in generale. Domanda ripubblicata: esiste un'implementazione efficiente della memoria del dizionario int-int che utilizza molto meno di 49 byte/coppia?

Answer 1

Si potrebbe utilizzare i IIBtree da Zope

Answer 2

8 byte per chiave/valore pari sarebbe piuttosto difficile sotto qualsiasi implementazione, Python o in altro modo. Se non si ha la garanzia che le chiavi siano contigue allora si sprecerebbe molto spazio tra le chiavi usando una rappresentazione di matrice (oltre a richiedere una sorta di valore morto per indicare una chiave nulla), oppure Dovevo mantenere un indice separato per coppie chiave/valore che, per definizione, supererebbero gli 8 byte per coppia (anche se solo di una piccola quantità).

Ti suggerisco di utilizzare il metodo dell'array, ma l'approccio migliore dipenderà dalla natura dei tasti che mi aspetto.

Answer 3

Non so se questa è una soluzione one-shot, o parte di un progetto in corso, ma se è la prima, sta lanciando più ram a meno del tempo di sviluppo necessario per ottimizzare l'utilizzo della memoria? Anche a 64 byte per coppia, stai ancora guardando solo 15 GB, che si adatteranno abbastanza facilmente nella maggior parte dei desktop box.

Penso che la risposta corretta risieda probabilmente nelle librerie SciPy/NumPy, ma non sono abbastanza familiare con la libreria per dirti esattamente dove cercare.

http://docs.scipy.org/doc/numpy/reference/

Si potrebbe anche trovare alcune idee utili in questa discussione: Memory Efficient Alternatives to Python Dictionaries

Answer 4

Ho implementato il mio dizionario Int-Int, available here (licenza BSD). In breve, io uso array.array('i') per archiviare le coppie chiave-valore ordinate per chiavi.Infatti, invece di un array di grandi dimensioni, tengo un dizionario di array più piccoli (una coppia chiave-valore è memorizzata nell'array key/65536) per accelerare lo spostamento durante l'inserimento e la ricerca binaria durante il recupero. Ogni array memorizza le chiavi ei valori nel modo seguente:

key0 value0 key1 value1 key2 value2 ... 

In realtà, non è solo un dizionario int-int, ma un dizionario oggetto int generale con oggetti ridotti ai loro hash. Pertanto, il dizionario hash-int può essere usato come una cache di un dizionario memorizzato in modo persistente.

Esistono tre possibili strategie di gestione delle "collisioni di chiavi", ovvero tentativi di assegnare un valore diverso alla stessa chiave. La strategia predefinita lo consente. La "cancellazione" rimuove la chiave e la contrassegna come collisione, in modo che qualsiasi ulteriore tentativo di assegnargli un valore non abbia alcun effetto. La strategia "urlando" genera un'eccezione durante qualsiasi tentativo di sovrascrittura e su qualsiasi ulteriore accesso a qualsiasi chiave in collisione.

Si prega di vedere my answer a a related question per una descrizione in modo diverso del mio approccio.

Answer 5

Guardando i tuoi dati sopra, non è 49 byte per int, è 25. Gli altri 24 byte per voce sono gli oggetti int stessi. Quindi è necessario qualcosa che sia significativamente più piccolo di byte per voce. A meno che tu non abbia intenzione di reimplementare gli oggetti int, che è possibile per gli hash della chiave, almeno. Oppure implementalo in C, dove puoi saltare completamente gli oggetti (questo è ciò che fa Zopes IIBTree, menzionato sopra).

Per essere onesti, il dizionario Python è ottimizzato in vari modi. Non sarà facile batterlo, ma buona fortuna.

Answer 6

Che ne dici di un array Judy se stai mappando da ints? È una specie di array sparse ... Usa 1/4 dello spazio di implementazione del dizionario.

Judy:

$ cat j.py ; time python j.py 
import judy, random, sys 
from guppy import hpy 
random.seed(0) 
h = hpy() 
h.setrelheap() 
d = judy.JudyIntObjectMap() 
for _ in xrange(4000000): 
    d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint) 

print h.heap() 
Partition of a set of 4000004 objects. Total size = 96000624 bytes. 
Index Count %  Size % Cumulative % Kind (class/dict of class) 
    0 4000001 100 96000024 100 96000024 100 int 
    1  1 0  448 0 96000472 100 types.FrameType 
    2  1 0  88 0 96000560 100 __builtin__.weakref 
    3  1 0  64 0 96000624 100 __builtin__.PyJudyIntObjectMap 

real 1m9.231s 
user 1m8.248s 
sys  0m0.381s 

dizionario:

$ cat d.py ; time python d.py 
import random, sys 
from guppy import hpy 
random.seed(0) 
h = hpy() 
h.setrelheap() 
d = {} 
for _ in xrange(4000000): 
    d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint) 

print h.heap() 
Partition of a set of 8000003 objects. Total size = 393327344 bytes. 
Index Count %  Size % Cumulative % Kind (class/dict of class) 
    0  1 0 201326872 51 201326872 51 dict (no owner) 
    1 8000001 100 192000024 49 393326896 100 int 
    2  1 0  448 0 393327344 100 types.FrameType 

real 1m8.129s 
user 1m6.947s 
sys  0m0.559s 

~ 1/4 ° lo spazio:

$ echo 96000624/393327344 | bc -l 
.24407309958089260125 

(sto usando 64bit python, btw, così i miei numeri di base può essere gonfiato a causa di puntatori a 64 bit)