列表预分配空间的锅

Python 2018-10-16

起步

两个存储元素内容相同的列表占用内存空间可能会不一样。

20181015102116.png

甚至 a == b 都是成立的。是什么导致了占用的空间不一致的呢?

列表对象的存储方式

Python 中 list 的实现方式和 C++ 的 vector 类似,它并不是存多少东西就申请多少内存,它会申请一块较大的内存,避免每次新增元素都要进行内存申请和元素拷贝。当空间不足以容纳新元素时会进行扩容。

20181016094214.png

上图中 [0] 时是确定的元素个数,就只申请容纳一个元素空间,而 append 追加的方式会导致 list 对象扩容。

解答

为了解释最开始图片里的问题,还要先知道乘法 **= 是两个不同的操作符。这点上可以通过字节码来得到:

import dis
def fun():
    a = [0]
    a = a * 10
    b = [0]
    b *= 10

dis.dis(fun)

相关的字节码为:

 6 LOAD_FAST                0 (a)
 8 LOAD_CONST               2 (10)
10 BINARY_MULTIPLY          # * 操作符
12 STORE_FAST               0 (a)
...
20 LOAD_FAST                1 (b)
22 LOAD_CONST               2 (10)
24 INPLACE_MULTIPLY         # *= 操作符
26 STORE_FAST               1 (b)

我们初学时总是会将 a *= n 理解为 a = a * n (当然这里理解是没错的),深入后就会发现他们的不同了。用 Python 中的魔术方法来说就是一个会调用 __mul__ 一个会调用 __imul__

而 list 对象是 C 实现的,自然是调用 C 函数了,乘法操作会调用 list_repeat()*= 会调用 list_inplace_repeat()

[listobject.c  v3.6.5]
static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    ...
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);  // 创建容纳size个空间的列表
    ...
}

从这可以看出 list_repeat 需要多少空间就申请多少空间,从这里也可以看出乘法操作是返回一个新的列表对象。

再来看看 list_inplace_repeat

[listobject.c  v3.6.5]
static PyObject *
list_inplace_repeat(PyListObject *self, Py_ssize_t n)
{
    ...
    size = PyList_GET_SIZE(self);
    ...
    if (list_resize(self, size*n) < 0)
        return NULL;
    ...
}

代码中试图通过 list_resize 来进行扩容,并告诉它这个列表需要容纳 size * n 个元素,那么 resize 函数里面会申请比所需的空间还要大点的内存吗?显然是的:

[listobject.c  v3.6.5]
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    ...
    new_allocated = newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    ...
}

resize 后的空间 总是 比所需要的大的。按照这里的扩容规则,如果一个空列表通过 append 不断往里面添加元素,那么空间占用会是 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

所以这个 *= 会引起列表 resize,而比 * 的方式占用空间大;解释完毕。

延伸

为了验证空间增长规律,看看下面的例子:

20181016102526.png

这里只要说变量 e 就可以了,它不同其实是因为它不是从空列表增长上来的。它的初始大小是 1。那么知道 resize 规则,应该能列出变量 e 的增长顺序了吧。

扩展阅读:https://www.hongweipeng.com/index.php/archives/1229/


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!