Perché la dimensione di un dict vuoto è uguale a quella di un dict non vuoto in Python?

Question

Questo potrebbe essere banale, ma non sono sicuro di aver capito, ho provato a cercare su Google ma non ho trovato una risposta convincente.

>>> sys.getsizeof({}) 
140 
>>> sys.getsizeof({'Hello':'World'}) 
140 
>>> 
>>> yet_another_dict = {} 
>>> for i in xrange(5000): 
     yet_another_dict[i] = i**2 

>>> 
>>> sys.getsizeof(yet_another_dict) 
98444 

Come posso capire questo? Perché un dict vuoto ha le stesse dimensioni di un dict non vuoto?

Answer 1

ci sono due ragioni per questo:

1. dizionario contiene solo riferimenti agli oggetti, non gli oggetti stessi, quindi la sua dimensione non è correlata con le dimensioni degli oggetti che contiene , ma con il numero di riferimenti (elementi) contenuti nel dizionario.

2. Più importante, il dizionario prealloca la memoria per i riferimenti in blocchi. Quindi, quando hai creato un dizionario, già prealloca la memoria per i primi riferimenti n. Quando riempie la memoria, prealloca un nuovo blocco.

È possibile osservare tale comportamento, eseguendo la successiva tranquillità del codice.

d = {} 
size = sys.getsizeof(d) 
print size 
i = 0 
j = 0 
while i < 3: 
    d[j] = j 
    j += 1 
    new_size = sys.getsizeof(d) 
    if size != new_size: 
     print new_size 
     size = new_size 
     i += 1 

che stampa:

280 
1048 
3352 
12568 

Sulla mia macchina, ma questo dipende dalla architettura (32 bit, 64 bit).

Answer 2

I dizionari in CPython allocano una piccola quantità di spazio chiave direttamente nell'oggetto dizionario stesso (4-8 voci in base alle opzioni di versione e di compilazione). Da dictobject.h:

/* PyDict_MINSIZE is the minimum size of a dictionary. This many slots are 
* allocated directly in the dict object (in the ma_smalltable member). 
* It must be a power of 2, and at least 4. 8 allows dicts with no more 
* than 5 active entries to live in ma_smalltable (and so avoid an 
* additional malloc); instrumentation suggested this suffices for the 
* majority of dicts (consisting mostly of usually-small instance dicts and 
* usually-small dicts created to pass keyword arguments). 
*/ 
#ifndef Py_LIMITED_API 
#define PyDict_MINSIZE 8 

---

noti che CPython ridimensiona anche il dizionario in lotti per evitare riassegnazioni frequenti per i dizionari in crescita. Da dictobject.c:

/* If we added a key, we can safely resize. Otherwise just return! 
* If fill >= 2/3 size, adjust size. Normally, this doubles or 
* quaduples the size, but it's also possible for the dict to shrink 
* (if ma_fill is much larger than ma_used, meaning a lot of dict 
* keys have been * deleted). 
* 
* Quadrupling the size improves average dictionary sparseness 
* (reducing collisions) at the cost of some memory and iteration 
* speed (which loops over every possible entry). It also halves 
* the number of expensive resize operations in a growing dictionary. 
* 
* Very large dictionaries (over 50K items) use doubling instead. 
* This may help applications with severe memory constraints. 
*/ 
if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2)) 
    return 0; 
return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);