是什么导致[ * a ]过度配置？

很明显，list(a)没有过度分配，[x for x in a]在某些点上过度分配，而 [*a]过度分配 一直都是？

Sizes up to n=100

下面是从0到12的大小 n 以及这三个方法的大小(以字节为单位) :

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

这样计算，可复制，使用 Python 3。 8:

from sys import getsizeof


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

那么: 这是如何工作的？[*a]如何超配？实际上，它使用什么机制来从给定的输入创建结果列表？它是否在 a上使用迭代器并使用类似于 list.append的东西？源代码在哪？

(产生图像的 与数据和代码合作。)

放大到更小的 n:

Sizes up to n=40

放大到更大的 n:

Sizes up to n=1000

5912 次浏览
小开
最佳答案

返回文章页面

  1. 创建一个新的、空的 list
  2. 打电话给 newlist.extend(a)
  3. 返回 list。

因此，如果你将测试扩展到:

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)的结果是相同的。

这通常是正确的做法; 当 extending 通常期望稍后添加更多内容时，类似地，对于广义解包，假设将一个接一个地添加多个内容。[*a]不是通常的情况; Python 假设有多个项或迭代器被添加到 list([*a, b, c, *d]) ，因此在通常情况下，过度分配可以节省工作。

相比之下，由一个单一的、预先调整大小的迭代器(使用 list())构建的 list在使用过程中可能不会增长或收缩，而且过度分配是不成熟的，除非证明不是这样; Python 最近修复了一个 bug，该 bug 使得构造函数甚至对于大小已知的输入也过度分配。

至于 list理解，它们实际上等同于重复的 append，所以当一次添加一个元素时，您将看到正常过度分配增长模式的最终结果。

明确地说，这些都不是语言的保证。这就是 CPython 实现它的方式。Python 语言规范通常不关心 list中的特定增长模式(除了保证从结尾开始分摊的 O(1) append和 pop)。正如在评论中指出的，具体的实现在3.9中再次改变; 虽然它不会影响到 [*a]，但它可能会影响到其他情况，在这些情况下，过去“构建单个项目的临时 tuple，然后 extend与 tuple”现在变成了 LIST_APPEND的多个应用程序，当超额分配发生时，它可以改变，什么数字进入计算。

小开

这些将是 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，它在调用 list(a)时使用。

小开

在其他答案和评论(特别是 暗影游侠的回答，它也解释了 为什么是这样做的)的基础上，完整的 什么图发生了。

反汇编显示使用了 BUILD_LIST_UNPACK:

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

这里处理的是 在 ceval.c，它构建一个空列表并对其进行扩展(使用 a) :

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

返回文章页面

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

其中 用大小之和调用 list_resize:

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

过度分配如下:

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匹配，list_extend实际上是 走捷径，所以实际上也匹配:

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

提交答案