为什么元组在内存中占用的空间少于列表？

Question

一个tuple发生在Python的内存空间少:

>>> a = (1,2,3)
>>> a.__sizeof__()
48

而lists需要更多的内存空间:

>>> b = [1,2,3]
>>> b.__sizeof__()
64

Python内存管理内部会发生什么？

Answer 1

我假设您正在使用CPython和64位(我在CPython 2.7 64位上获得了相同的结果).在其他Python实现中可能存在差异,或者如果您有32位Python.

无论实现如何,lists都是可变大小的,而tuples是固定大小的.

所以tuples可以直接在struct中存储元素,另一方面,list需要一个间接层(它存储一个指向元素的指针).这个间接层是一个指针,在64位系统上是64位,因此是8字节.

但还有另外一件事list:他们过度分配.否则list.append将是一个O(n)操作总是 - 使其摊销O(1)(更快!!!)它过度分配.但现在它必须跟踪分配的大小和填充的大小(tuples只需要存储一个大小,因为分配和填充的大小总是相同).这意味着每个列表必须存储另一个"大小",在64位系统上是64位整数,再为8个字节.

所以list需要至少比tuples 多16个字节的内存.为什么我说"至少"？因为过度分配.过度分配意味着它分配的空间超出了需要.但是,过度分配的数量取决于您创建列表的"方式"以及追加/删除历史记录:

>>> l = [1,2,3]
>>> l.__sizeof__()
64
>>> l.append(4)  # triggers re-allocation (with over-allocation), because the original list is full
>>> l.__sizeof__()
96

>>> l = []
>>> l.__sizeof__()
40
>>> l.append(1)  # re-allocation with over-allocation
>>> l.__sizeof__()
72
>>> l.append(2)  # no re-alloc
>>> l.append(3)  # no re-alloc
>>> l.__sizeof__()
72
>>> l.append(4)  # still has room, so no over-allocation needed (yet)
>>> l.__sizeof__()
72

图片

我决定创建一些图像以配合上面的解释.也许这些都很有帮助

这是(示意性地)在您的示例中存储在内存中的方式.我强调了红色(自由手)循环的差异:

这实际上只是一个近似值,因为int对象也是Python对象,CPython甚至可以重用小整数,因此内存中对象的一个​​可能更准确的表示(虽然不是可读)将是:

有用的链接:

• tuple 用于Python 2.7的CPython存储库中的struct
• list 用于Python 2.7的CPython存储库中的struct
• int 用于Python 2.7的CPython存储库中的struct

注意,__sizeof__并没有真正返回"正确"的大小!它只返回存储值的大小.但是当你使用sys.getsizeof结果时会有所不同:

>>> import sys
>>> l = [1,2,3]
>>> t = (1, 2, 3)
>>> sys.getsizeof(l)
88
>>> sys.getsizeof(t)
72

有24个"额外"字节.这些是真实的,这是方法中没有考虑的垃圾收集器开销__sizeof__.那是因为你通常不应该直接使用魔术方法 - 使用知道如何处理它们的函数,在这种情况下:( sys.getsizeof实际上将GC开销添加到返回的值__sizeof__).

Answer 2

我将深入研究CPython代码库,以便我们可以看到实际计算的大小.在您的具体示例中,没有执行过度分配,因此我不会涉及到这一点.

我将在这里使用64位值.

lists 的大小由以下函数计算list_sizeof:

static PyObject *
list_sizeof(PyListObject *self)
{
    Py_ssize_t res;

    res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
    return PyInt_FromSsize_t(res);
}

这里Py_TYPE(self)是抓住宏ob_type的self(返回PyList_Type),而 _PyObject_SIZE是抓起另一个宏tp_basicsize从该类型.tp_basicsize被计算为sizeof(PyListObject),其中PyListObject是实例结构.

该PyListObject结构有三个领域:

PyObject_VAR_HEAD     # 24 bytes 
PyObject **ob_item;   #  8 bytes
Py_ssize_t allocated; #  8 bytes

这些评论(我修剪)解释它们是什么,按照上面的链接阅读它们.PyObject_VAR_HEAD扩展为三个8字节字段(ob_refcount,ob_type和ob_size)所以一个24字节贡献.

所以现在res是:

sizeof(PyListObject) + self->allocated * sizeof(void*)

要么:

40 + self->allocated * sizeof(void*)

如果列表实例具有已分配的元素.第二部分计算他们的贡献.self->allocated顾名思义,它保存了已分配元素的数量.

没有任何元素,列表的大小计算为:

>>> [].__sizeof__()
40

即实例结构的大小.

tuple对象不定义tuple_sizeof函数.相反,他们object_sizeof用来计算他们的大小:

static PyObject *
object_sizeof(PyObject *self, PyObject *args)
{
    Py_ssize_t res, isize;

    res = 0;
    isize = self->ob_type->tp_itemsize;
    if (isize > 0)
        res = Py_SIZE(self) * isize;
    res += self->ob_type->tp_basicsize;

    return PyInt_FromSsize_t(res);
}

对于lists,这样可以获取tp_basicsize和,如果对象具有非零值tp_itemsize(意味着它具有可变长度实例),它会将元组中的项目数(它通过它Py_SIZE)与之相乘tp_itemsize.

tp_basicsize再次使用sizeof(PyTupleObject)其中的 PyTupleObject结构包含:

PyObject_VAR_HEAD       # 24 bytes 
PyObject *ob_item[1];   # 8  bytes

因此,没有任何元素(即Py_SIZE返回0),空元组的大小等于sizeof(PyTupleObject):

>>> ().__sizeof__()
24

是吧？嗯,这里是我还没有找到一个解释,在一个古怪tp_basicsize的tuples的实际计算公式如下:

sizeof(PyTupleObject) - sizeof(PyObject *)

为什么8要删除额外的字节是tp_basicsize我无法找到的.(有关可能的解释,请参阅MSeifert的评论)

但是,这基本上是您具体示例的不同之处.lists还保留了许多已分配的元素,这有助于确定何时再次进行过度分配.

现在,当添加其他元素时,列表确实会执行此过度分配以实现O(1)追加.这导致更大的尺寸,因为MSeifert在他的回答中很好地涵盖了.

Answer 3

MSeifert答案涵盖范围广泛; 为了保持简单,你可以想到:

tuple是不可改变的.设置后,您无法更改它.因此,您事先知道需要为该对象分配多少内存.

list是可变的.您可以在其中添加或删除项目.它必须知道它的大小(对于内部impl.).它根据需要调整大小.

没有免费餐 - 这些功能需要付费.因此列表的内存开销.