Tại sao kích thước của một dict trống giống như một dict không trống trong Python?

Question

Điều này có thể tầm thường, nhưng tôi không chắc tôi hiểu, tôi đã thử googling xung quanh nhưng không tìm thấy một câu trả lời thuyết phục.

>>> 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 

Làm cách nào để hiểu điều này? Tại sao một dict trống có cùng kích thước với một dict không trống?

Answer 1

Có hai lý do cho điều đó:

1. điển chỉ giữ tham chiếu đến các đối tượng, không phải là đối tượng chính họ, do đó, nó có kích thước không tương quan với kích thước của các đối tượng nó chứa , nhưng với số tham chiếu (các mục) từ điển chứa.

2. Quan trọng hơn, từ điển preallocates bộ nhớ cho các tham chiếu theo khối. Vì vậy, khi bạn tạo một từ điển nó đã preallocates bộ nhớ cho các tài liệu tham khảo n đầu tiên. Khi nó lấp đầy bộ nhớ nó preallocates một đoạn mới.

Bạn có thể quan sát hành vi đó, chạy mã hòa bình tiếp theo.

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 

nào in ra:

280 
1048 
3352 
12568 

Trên máy tính của tôi, nhưng điều này phụ thuộc vào kiến ​​trúc (32bit, 64bit).

Answer 2

Từ điển trong CPython phân bổ một lượng nhỏ không gian khóa trực tiếp trong chính đối tượng từ điển (4-8 mục tùy thuộc vào phiên bản và tùy chọn biên dịch). Từ 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 

---

Lưu ý rằng CPython cũng thay đổi kích thước từ điển theo lô để tránh tái phân bổ thường xuyên cho từ điển ngày càng tăng. Từ 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);