内存中列表的大小

我只是在内存中试验了python数据结构的大小。 我写了下面的代码片断：

import sys lst1=[] lst1.append(1) lst2=[1] print(sys.getsizeof(lst1), sys.getsizeof(lst2)) 

我testing了以下configuration的代码：

• Windows 7 64bit，Python3.1：输出是： 52 40所以lst1有52个字节，而lst2有40个字节。
• 使用Python3.2的Ubuntu 11.4 32bit：输出是48 32
• Ubuntu 11.4 32bit Python2.7： 48 36

任何人都可以向我解释为什么这两个大小不同，尽pipe两个列表都包含1？

在getsizeof函数的python文档中，我发现了以下内容： ...adds an additional garbage collector overhead if the object is managed by the garbage collector. 在我的小例子中是这样吗？

Answer 1

下面是一个更完整的交互式会话，它将帮助我解释发生了什么事情（Windows XP 32位上的Python 2.6，但实际上并不重要）：

 >>> import sys >>> sys.getsizeof([]) 36 >>> sys.getsizeof([1]) 40 >>> lst = [] >>> lst.append(1) >>> sys.getsizeof(lst) 52 >>> 

请注意，空列表比它中的[1]一点。 然而，当一个元素被追加时，它会变得更大。

其原因是在CPython的源文件Objects/listobject.c的实现细节。

空的清单

当创build一个空的列表[] ，没有分配元素的空间 – 这可以在PyList_New看到。 36字节是32位机器上列表数据结构本身所需的空间量。

列出一个元素

当创build具有单个元素[1]的列表时，除了列表数据结构本身所需的存储器之外，还分配一个元素的空间。 再次，这可以在PyList_Newfind。 给定size作为论据，它计算：

 nbytes = size * sizeof(PyObject *); 

然后有：

 if (size <= 0) op->ob_item = NULL; else { op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); if (op->ob_item == NULL) { Py_DECREF(op); return PyErr_NoMemory(); } memset(op->ob_item, 0, nbytes); } Py_SIZE(op) = size; op->allocated = size; 

所以我们看到size = 1 ，分配一个指针的空间。 4个字节（在我的32位盒子上）。

追加到一个空的列表

当在空列表上调用append时，会发生以下情况：

• PyList_Append调用app1
• app1要求列表的大小（并得到0作为答案）
• app1然后调用size+1 list_resize （在我们的例子中是1）
• list_resize有一个有趣的分配策略，从源头上总结了这个评论。

这里是：

 /* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); /* check for integer overflow */ if (new_allocated > PY_SIZE_MAX - newsize) { PyErr_NoMemory(); return -1; } else { new_allocated += newsize; } 

我们来做一些math

让我们来看看我在文章开头所引用的数字是如何达到的。

所以36字节是32位的列表数据结构本身所需的大小。 对于单个元素，空间分配给一个指针，所以这是4个额外的字节 – 总共40个字节。 好，至今。

当在空列表上调用app1 ，会调用size=1 list_resize 。 根据list_resize的过度分配algorithm，1之后的最大可用大小是4，因此将分配4个指针的地方。 4 * 4 = 16字节，36 + 16 = 52。

事实上，一切都有道理:-)

Answer 2

对不起，以前的评论有点简单。

发生了什么事情是你在查看如何分配列表（我想也许你只是想看看有多大的东西 – 在这种情况下，使用sys.getsizeof() ）

当一些东西被添加到列表中时，可能会发生以下两件事之一：

1. 额外的项目适合闲置的空间

2. 需要额外的空间，所以创build一个新的列表，并复制内容，并添加额外的东西。

因为（2）是昂贵的（复制东西，即使是指针，需要的时间与要复制的东西的数量成正比，所以随着列表变大而增长），我们不经常这样做。 所以不是只增加一点点空间，而是增加一个整块。 通常所添加的数量的大小与已经使用的数量相似 – 这样，math计算出的分配内存的平均成本（分布在许多用途上）仅与列表大小成比例。

所以你看到的是与这种行为有关。 我不知道确切的细节，但如果[]或[1] （或两者）是特殊情况，只分配了足够的内存（以在这些常见情况下节省内存），然后追加上面描述的“抓住一个新的块”增加了更多。

但我不知道确切的细节 – 这是dynamic数组的工作原理。 Python中列表的确切实现将被精细调整，以便它对于典型的Python程序是最佳的。 所以我真正说的是，你不能相信列表的大小，以确切地告诉你它包含多less – 它可能包含额外的空间，额外的自由空间的数量很难判断或预测。

一个简单的替代方法是将列表作为(value, pointer)对，其中每个指针指向下一个元组。 通过这种方式，您可以逐渐增加列表，尽pipe使用的总内存更高。 这是一个链表（python使用更像是一个向量或dynamic数组）。

[更新]见Eli的优秀答案。 他/她解释说， []和[1]都是完全分配的，但附加到[]分配一个额外的块。 代码中的评论就是我上面所说的（这就是所谓的“超额分配”，这个额度是我们所拥有的，使得平均（“摊销”）成本与大小成正比）。

Answer 3

以下是列表增长模式的快速演示。 在range（）中改变第三个参数会改变输出，所以它看起来不像listobject.c中的注释，但是简单地追加一个元素的结果似乎是非常准确的。

 allocated = 0 for newsize in range(0,100,1): if (allocated < newsize): new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6) allocated = newsize + new_allocated; print newsize, allocated