我跑了这个:
import sys
diii = {'key1':1,'key2':2,'key3':1,'key4':2,'key5':1,'key6':2,'key7':1}
print sys.getsizeof(diii)
# output: 1048
diii = {'key1':1,'key2':2,'key3':1,'key4':2,'key5':1,'key6':2,'key7':1,'key8':2}
print sys.getsizeof(diii)
# output: 664
在询问之前,我重新启动了我的python shell,并在网上进行了尝试,得到了相同的结果。
我认为一个多元素的字典将给出与输出相同的字节或更多的字节,而不是一个少元素的字典。
知道我做错什么了吗?
最佳答案
前面的答案已经提到了您不必担心,所以我将深入了解一些更详细的技术细节。很长,但请你忍受我。
这与调整大小的算法有关。每个resize都分配2**i
内存,其中2**i > requested_size; 2**i >= 8
,但是如果有2/3的槽被填满,那么每个insert都会进一步调整基础表的大小,但这次是new_size = old_size * 4
。这样,您的第一个字典最终分配了32个单元格,而第二个字典则只分配了16个(因为前面的初始大小更大)。
答:正如@snakecharmerb在评论中指出的,这取决于词典的创建方式。为了简洁起见,让我参考一下this, excellent blog post,它解释了在python字节码和cpython实现级别上,dict()
构造函数和dict literal{}
之间的区别。
让我们从8把钥匙的神奇数字开始。结果发现它是一个常量,在头文件中为python的2.7实现预定义。
-python字典的最小大小:
/* 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).
*/
#define PyDict_MINSIZE 8
因此,在特定的Python实现之间可能会有所不同,但我们假设都使用相同的cpython版本。不过,8号的dict预计只包含5个元素;不要担心,因为这种特定的优化对我们来说并不像看上去那么重要。
现在,当您使用dict literal创建字典时,cpython使用快捷方式(与调用
{}
构造函数时的显式创建相比)。简化一点,字节码操作会得到解决,它会导致调用dict
函数,该函数将构造一个字典,我们已经预先知道其大小:/* Create a new dictionary pre-sized to hold an estimated number of elements.
Underestimates are okay because the dictionary will resize as necessary.
Overestimates just mean the dictionary will be more sparse than usual.
*/
PyObject *
_PyDict_NewPresized(Py_ssize_t minused)
{
PyObject *op = PyDict_New();
if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
Py_DECREF(op);
return NULL;
}
return op;
}
此函数调用普通dict构造函数(
BUILD_MAP
)并请求调整新创建的dict的大小-但前提是该函数应包含5个以上的元素。这是由于一种优化,允许python通过将数据保存在预先分配的“smalltable”中来加快某些速度,而无需调用昂贵的内存分配和取消分配函数。然后,
_PyDict_NewPresized
将尝试确定新字典的最小大小。它还将使用幻数8-作为起点,并迭代乘以2,直到找到大于请求大小的最小大小。对于第一个字典,这仅仅是8,但是对于第二个字典(以及所有由dict literal创建的、键数少于15的字典),它是16。现在,在
PyDict_New
函数中,前者的dictobject.h更小,这意味着要提出前面提到的优化(使用“小表”来减少内存操作操作)。但是,因为不需要调整新创建的dict的大小(例如,到目前为止没有删除任何元素,因此表是“干净的”),所以实际上什么都不会发生。相反,当
dictresize
时,通常会执行重新分配哈希表的过程。最后会分配一个新表来存储“大”字典。虽然这是直观的(更大的口述有一个更大的桌子),这似乎还没有推动我们前进到观察到的行为-但是,请再忍受我一分钟。
一旦我们有了预先分配的dict,store-map optcodes就会告诉解释器插入连续的键值对。这是通过
dictresize
函数实现的,如果超过2/3的槽已经用完,该函数在每次增加大小(即成功插入)后,都会调整字典的大小。大小将增加x4(a special case,对于大型dict,仅增加x2)。下面是使用7个元素创建dict时所发生的情况:
# note 2/3 = 0.(6)
BUILD_MAP # initial_size = 8, filled = 0
STORE_MAP # 'key_1' ratio_filled = 1/8 = 0.125, not resizing
STORE_MAP # 'key_2' ratio_filled = 2/8 = 0.250, not resizing
STORE_MAP # 'key_3' ratio_filled = 3/8 = 0.375, not resizing
STORE_MAP # 'key_4' ratio_filled = 4/8 = 0.500, not resizing
STORE_MAP # 'key_5' ratio_filled = 5/8 = 0.625, not resizing
STORE_MAP # 'key_6' ratio_filled = 6/8 = 0.750, RESIZING! new_size = 8*4 = 32
STORE_MAP # 'key_7' ratio_filled = 7/32 = 0.21875
最后得到的是哈希表中总大小为32个元素的dict。
但是,当添加八个元素时,初始大小将是原来的两倍(16),因此我们永远不会调整大小,因为条件永远不会满足。
这就是为什么在第二种情况下你会得到一张小桌子。
关于python - 字典大小在增加一个元素时减少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56313195/