内存中列表的大小

Question

我只是试验了内存中 python 数据结构的大小。我写了以下片段：

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

我在以下配置上测试了代码：

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

谁能向我解释为什么这两个大小不同，尽管它们都是包含 1 的列表？

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

原文由 halex 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 中的实现细节。

空列表

创建空列表 [] 时，不会为元素分配空间 - 这可以在 PyList_New 中看到。 36 字节是列表数据结构本身在 32 位机器上所需的空间量。

包含一个元素的列表

当创建具有单个元素的列表 [1] 时，除了列表数据结构本身所需的内存之外，还会为一个元素分配空间。同样，这可以在 PyList_New 中找到。给定 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 然后调用 list_resize size+1 （在我们的例子中是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;
}

让我们做一些数学

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

所以 36 字节是列表数据结构本身在 32 位上所需的大小。对于单个元素，空间被分配给一个指针，所以这是 4 个额外的字节——总共 40 个字节。好的到目前为止。

当在空列表上调用 app1 时，它调用 list_resize 和 size=1 。根据 list_resize 的过度分配算法，1 之后的下一个最大可用大小是 4，因此将分配 4 个指针的位置。 4 * 4 = 16 字节，36 + 16 = 52。

确实，一切都说得通:-)

原文由 Eli Bendersky 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

抱歉，之前的评论有点生硬。

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

将某物添加到列表时，可能会发生以下两种情况之一：

1. 多余的物品适合备用空间

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

因为 (2) 很昂贵（复制东西，甚至指针，花费的时间与要复制的东西的数量成正比，所以随着列表变大而增长）我们希望不经常这样做。所以我们不只是增加一点空间，而是增加一整块。通常，添加的数量的大小与已经使用的数量相似——这样数学就可以计算出分配内存的平均成本，分布在许多用途中，仅与列表大小成正比。

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

但我不知道确切的细节——这就是动态数组的一般工作方式。将对 Python 中列表的确切实现进行微调，使其最适合典型的 Python 程序。所以我真正要说的是，您不能相信列表的大小可以准确地告诉您它包含多少——它可能包含额外的空间，而额外的可用空间量很难判断或预测。

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

[更新] 查看 Eli 的出色回答。他/她解释说 [] 和 [1] 都被准确分配了，但是附加到 [] 分配了一个额外的块—代码中的注释就是我上面所说的（这称为“过度分配”，数量与我们拥有的数量成正比，因此平均（“摊销”）成本与规模成正比）。

原文由 andrew cooke 发布，翻译遵循 CC BY-SA 3.0 许可协议