Per rispondere alla tua domanda circa dict vs list che avrebbe dovuto dare l'esatto informazioni sul numero di elementi, il numero di elementi mancanti, ecc, in modo da tha potremmo stimare esattamente l'utilizzo della memoria della struttura dati due e prova a prevedere e/o verificare le loro prestazioni.
In generale un dict di N coppie di valori-chiave richiede un po 'più memoria piuttosto di un list con N valori:
- Il
dict deve tenere traccia delle chiavi
- Il
dict è mai superiore 2/3 completo. Quando ciò accade, la memoria allocata viene raddoppiata (è necessario che O (1) abbia operazioni temporizzate su dict).
Tuttavia c'è un'alternativa a questi struttura di dati che dovrebbero fornire ottime prestazioni: blist. Il pacchetto blist fornisce un'interfaccia che corrisponde a quella di list, solo che viene implementata utilizzando alberi B. Può gestire in modo efficiente elenchi sparsi. La maggior parte delle operazioni richiede il tempo O(1) o O(log n), quindi sono abbastanza efficienti.
Per esempio si potrebbe creare prima una rada blist facendo:
from blist import blist
seq = blist([None])
seq *= 2**30 # create a 2**30 element blist. Instantaneous!
E allora si può impostare solo gli indici che hanno un valore:
for i, value in zip(indices, values):
seq[i] = value
La documentazione completa è here.
noti che blist fornisce altre operazioni efficienti come:
- Concatenating due
blist s prendono O(log n) tempo
- Prendendo un
[i:j] fetta prende O(log n) tempo
- Inserimento di un elemento in un determinato indice tiene
O(log n) operazioni
- Aprire un elemento (da ogni posizione) richiede operazioni
O(log n)
Dal momento che ti ha dato alcuni numeri, ecco come si confronta con dict s:
>>> from blist import blist
>>> b = blist([None])
>>> b *= 5000
>>> for i in range(100):b[i] = i
...
>>> b.__sizeof__()
2660
>>> d = dict()
>>> for i in range(100):d[i] = i
...
>>> d.__sizeof__()
6216
>>> b = blist([None])
>>> b *= 750
>>> for i in range(30):b[i] = i
...
>>> b.__sizeof__()
1580
>>> d = dict()
>>> for i in range(30):d[i] = i
...
>>> d.__sizeof__()
1608
In entrambi i casi un blist richiede meno memoria (nel primo caso ci vogliono 1/3 della memoria dell'equivalente dict). Si noti che la memoria presa da un blist dipende anche dal fatto che gli indici siano contigui o meno (contiguo è meglio). Tuttavia, anche a mezzo di indici casuali:
>>> b = blist([None])
>>> b *= 5000
>>> import random
>>> for i in range(100):b[random.randint(0, 4999)] = i
...
>>> b.__sizeof__()
2916
E 'ancora molto meglio del dict.
talvolta anche di ricerca sono migliori:
In [1]: from blist import blist
...: import random
...:
In [2]: b = blist([None])
In [3]: b *= 5000
In [4]: for i in range(100):b[random.randint(0, 4999)] = i
In [5]: %timeit b[0]
10000000 loops, best of 3: 50.7 ns per loop
In [6]: d = dict()
In [7]: for i in range(100):d[random.randint(0, 4999)] = i
In [10]: %timeit d[1024] # 1024 is an existing key in this dictionary
10000000 loops, best of 3: 70.7 ns per loop
In [11]: %timeit b[1024]
10000000 loops, best of 3: 50.7 ns per loop
Nota che un list dura circa 47 ns per cercare l'indice sulla mia macchina, così blist è davvero molto vicino a un list in termini di prestazioni di ricerca su piccole liste come cos'hai.
A meno che non si tratti di codice estremamente sensibile alle prestazioni, non mi preoccuperei. Usa un 'dict' - semanticamente è molto più vicino a quello che stai cercando di ottenere. – sapi