[*a]如何过度分配?

[*a] 在内部执行C等价的 :

因此,如果您将测试扩展到:

来自sys import getsizeof

对于范围(13)中的n:
a=[无]*n
print(n,getsizeof(list(a)),
getsizeof([x代表a中的x]),
获取大小(l))

您将看到 getsizeof([*a]) 和 l=[];l.extend(a);getsizeof(l) 的结果是相同的

这通常是正确的做法;当 扩展 时,您通常希望稍后添加更多内容,对于一般化的解包,假设将一个接一个地添加多个内容。 [*a] 不是正常情况;Python假设有多个项或iterable被添加到 列表中( [*a,b,c,*d] ),因此在常见情况下,过度分配可以节省工作

很明显,这些都不是语言保证。这就是CPython如何实现它。Python语言规范通常与 list 中的特定增长模式无关(除了从末尾保证摊销 O(1) append s和 pop s)。如注释中所述,3.9中的具体实现再次发生变化;虽然它不会影响 [*a] ,但它可能会影响其他情况,即“构建单个项的临时 元组 ,然后使用 元组 扩展,现在变成了 LIST-APPEND 的多个应用程序,当过度分配发生时,这一点会发生变化,计算中会用到哪些数字

因此,如果您将测试扩展到:

from sys import getsizeof

for n in range(13):
    a = [None] * n
    l = []
    l.extend(a)
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]),
             getsizeof(l))

上网试试吧!

getsizeof([*a]) 和 l = []; l.extend(a); getsizeof(l) 都是一样的。

extend 通常您希望以后添加更多内容,对于一般的解包,假设将一个接一个地添加多个内容。 [*a] 列表 [*a, b, c, *d] ),因此在一般情况下,过度分配可以节省工作。

相比之下,a 从一个单一的,预先定好尺寸的 list() Python recently fixed a bug that made the constructor overallocate even for inputs with known size .

至于 列表 理解,它们实际上相当于重复 append

很明显,这些都不是语言保证。这就是CPython如何实现它。Python规范中的增长通常与特定的模式无关 列表 O(1) 追加 s和 pop ,这可能会影响到以前“建立临时的 tuple 然后 延伸 和 “现在变成了 LIST_APPEND ,当过度分配发生时,它可能会发生变化,计算中会用到哪些数字。

全貌 什么 ShadowRanger's answer 为什么? 就是这样做的)。

拆解表明 BUILD_LIST_UNPACK

>>> import dis
>>> dis.dis('[*a]')
  1           0 LOAD_NAME                0 (a)
              2 BUILD_LIST_UNPACK        1
              4 RETURN_VALUE

处理好了 in ceval.c a ):

        case TARGET(BUILD_LIST_UNPACK): {
            ...
            PyObject *sum = PyList_New(0);
              ...
                none_val = _PyList_Extend((PyListObject *)sum, PEEK(i));

_PyList_Extend uses list_extend

_PyList_Extend(PyListObject *self, PyObject *iterable)
{
    return list_extend(self, iterable);
}

哪个 calls list_resize with the sum of the sizes :

list_extend(PyListObject *self, PyObject *iterable)
    ...
        n = PySequence_Fast_GET_SIZE(iterable);
        ...
        m = Py_SIZE(self);
        ...
        if (list_resize(self, m + n) < 0) {

还有那个 overallocates

list_resize(PyListObject *self, Py_ssize_t newsize)
{
  ...
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

让我们检查一下。用上面的公式计算出预期的点的数量,并通过乘以8来计算预期的字节大小(正如我在这里使用的是64位Python)并添加一个空列表的字节大小(即列表对象的常量开销):

from sys import getsizeof
for n in range(13):
    a = [None] * n
    expected_spots = n + (n >> 3) + (3 if n < 9 else 6)
    expected_bytesize = getsizeof([]) + expected_spots * 8
    real_bytesize = getsizeof([*a])
    print(n,
          expected_bytesize,
          real_bytesize,
          real_bytesize == expected_bytesize)

输出:

0 80 56 False
1 88 88 True
2 96 96 True
3 104 104 True
4 112 112 True
5 120 120 True
6 128 128 True
7 136 136 True
8 152 152 True
9 184 184 True
10 192 192 True
11 200 200 True
12 208 208 True

匹配,除了 n = 0 ,哪个 事实上 shortcuts

        if (n == 0) {
            ...
            Py_RETURN_NONE;
        }
        ...
        if (list_resize(self, m + n) < 0) {

这些将是CPython解释器的实现细节,因此在其他解释器之间可能不一致。

list(a)

https://github.com/python/cpython/blob/master/Objects/listobject.c#L36

特别是为了理解:

 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
...

new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

就在这些线下面,有 list_preallocate_exact .