是什么导致[* a]总体化? [英] What causes [*a] to overallocate?

问题描述

很明显，list(a)不会整体化，[x for x in a]在某些点上整体化，而[*a]一直在整体上

Apparently list(a) doesn't overallocate, [x for x in a] overallocates at some points, and [*a] overallocates all the time?

以下是从0到12的大小n，以及三种方法的结果大小(以字节为单位):

Here are sizes n from 0 to 12 and the resulting sizes in bytes for the three methods:

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 在repl.it上可重现. 8 :

Computed like this, reproducable at repl.it, using 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这样的东西?源代码在哪里?

So: How does this work? How does [*a] overallocate? Actually, what mechanism does it use to create the result list from the given input? Does it use an iterator over a and use something like list.append? Where is the source code?

( ="将数据和代码与Colab一起生成图像.)

(Colab with data and code that produced the images.)

放大到较小的n:

缩小到更大的n:

推荐答案

[*a] 在内部执行C等效于:

1. 新建一个空的list
2. 致电newlist.extend(a)
3. 返回list.

1. Make a new, empty list
2. Call newlist.extend(a)
3. Returns list.

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

So if you expand your test to:

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

you'll see the results for getsizeof([*a]) and l = []; l.extend(a); getsizeof(l) are the same.

这通常是正确的选择；通常，在extend ing中您期望以后再添加更多内容时，对于一般的解压缩，类似的情况是，假设要在一个又一个的基础上添加多个内容. [*a]不是正常情况； Python假定list([*a, b, c, *d])中添加了多个项目或可迭代项，因此在常见情况下，过度分配可以节省工作.

This is usually the right thing to do; when extending you're usually expecting to add more later, and similarly for generalized unpacking, it's assumed that multiple things will be added one after the other. [*a] is not the normal case; Python assumes there are multiple items or iterables being added to the list ([*a, b, c, *d]), so overallocation saves work in the common case.

相比之下，由单个预先确定大小的可迭代对象(带有list())构成的list在使用过程中可能不会增长或收缩，并且积算过早，除非另外证明. Python最近修复了一个错误，该错误使构造函数即使对于已知大小的输入也可以进行整体分配.

By contrast, a list constructed from a single, presized iterable (with list()) may not grow or shrink during use, and overallocating is premature until proven otherwise; Python recently fixed a bug that made the constructor overallocate even for inputs with known size.

对于list理解，它们实际上等效于重复的append，因此您一次看到添加元素时，会看到正常的过度分配增长模式的最终结果.

As for list comprehensions, they're effectively equivalent to repeated appends, so you're seeing the final result of the normal overallocation growth pattern when adding an element at a time.

需要明确的是，这都不是语言保证.这就是CPython实现它的方式. Python语言规范通常与list中的特定增长模式无关(除了保证从最后开始摊销O(1) append s和pop s).如评论中所述，具体实现在3.9中再次更改；虽然它不会影响[*a]，但可能会影响其他情况，这些情况曾经是先构建单个项目的临时tuple然后用tuple构建extend"现在成为LIST_APPEND的多个应用程序，当发生过度分配以及计算中包含哪些数字时，该值可能会发生变化.

To be clear, none of this is a language guarantee. It's just how CPython implements it. The Python language spec is generally unconcerned with specific growth patterns in list (aside from guaranteeing amortized O(1) appends and pops from the end). As noted in the comments, the specific implementation changes again in 3.9; while it won't affect [*a], it could affect other cases where what used to be "build a temporary tuple of individual items and then extend with the tuple" now becomes multiple applications of LIST_APPEND, which can change when the overallocation occurs and what numbers go into the calculation.

这篇关于是什么导致[* a]总体化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！