预分配非

Question

假设您要编写一个生成对象列表的函数，并且您预先知道该列表的长度n。

在python中，列表支持O（1）中的索引访问，因此可以说，预先分配列表并用索引访问它是一个好主意，而不是分配空列表并使用append()方法。这是因为如果空间不够，我们可以避免扩展整个列表的负担。

如果我使用的是python，那么在任何情况下，性能可能都没有那么重要，但是预分配列表的更好方法是什么？

我知道这些可能的候选人：

• [None] * n→分配两个列表
• [None for x in range(n)]-或者xrange在python2中→构建另一个对象

一个明显比另一个好吗？

如果我们在这个案子里呢？既然input已经存在，那么[None for x in input]是否具有更好的w.r.t.[None] * len(input)性能？

Answer 1

在这两个选项之间，第一个选项显然更好，因为不涉及Python for循环。

>>> %timeit [None] * 100
1000000 loops, best of 3: 469 ns per loop
>>> %timeit [None for x in range(100)] 
100000 loops, best of 3: 4.8 us per loop

更新：

而且list.append也有一个^{} complexity，如果将list.append方法分配给变量，那么它可能是比预创建list更好的选择。

>>> n = 10**3
>>> %%timeit
lis = [None]*n           
for _ in range(n):
    lis[_] = _
... 
10000 loops, best of 3: 73.2 us per loop
>>> %%timeit
lis = []                 
for _ in range(n):
    lis.append(_)
... 
10000 loops, best of 3: 92.2 us per loop
>>> %%timeit
lis = [];app = lis.append
for _ in range(n):
    app(_)
... 
10000 loops, best of 3: 59.4 us per loop

>>> n = 10**6
>>> %%timeit
lis = [None]*n
for _ in range(n):
    lis[_] = _
... 
10 loops, best of 3: 106 ms per loop
>>> %%timeit
lis = []      
for _ in range(n):
    lis.append(_)
... 
10 loops, best of 3: 122 ms per loop
>>> %%timeit
lis = [];app = lis.append
for _ in range(n):
    app(_)
... 
10 loops, best of 3: 91.8 ms per loop

Answer 2

当您向列表追加一个项时，Python“over allocates”，请参见列表对象的source-code。这意味着，例如，在一个包含8个项的列表中添加1个项时，它实际上为8个新项腾出了空间，并且只使用其中的第一个项。接下来的7个附录是“免费的”。

在许多语言中（如Matlab），你总是被告知你需要预先分配向量，因为在循环过程中附加是非常昂贵的。在最坏的情况下，将单个项追加到长度为n的列表可能需要O(n)的时间，因为您可能需要创建一个更大的列表并复制所有现有项。每次迭代都需要这样做，所以添加n项的总成本是O(n^2)，哎哟。Python的预分配方案将数组增长的成本分摊到多个单个append上（参见amortized costs），有效地降低了单个append的成本O(1)和添加n项的总成本O(n)。

在Python中，其余代码的开销通常很大，因此通过预分配可以获得的微小加速是微不足道的。因此，在大多数情况下，只需忘记预分配，除非探查器告诉您追加到列表是一个瓶颈。

其他的答案显示了列表预分配本身的一些概要，但这是无用的。唯一重要的是分析完整的代码，所有的计算都在循环中，有没有预分配。如果我的预测是正确的，那么差异是如此之小，以至于你赢得的计算时间与花在思考、编写和维护额外的行以预先分配列表上的时间相形见绌。

Answer 3

显然，是第一个版本。让我解释一下原因。

1. 当您执行[None] * n操作时，Python会在内部创建一个大小为n的列表对象，并且它会将相同的对象（这里是None）复制到所有内存位置（这是原因，您应该仅在处理不可变对象时才使用此方法）。所以内存分配只做一次。在那之后，通过一次迭代列表将对象复制到所有元素。^{}是与此类列表创建相对应的函数。

   # Creates the list of specified size
   np = (PyListObject *) PyList_New(size);
   ....
   ...
   items = np->ob_item;
   if (Py_SIZE(a) == 1) {
       elem = a->ob_item[0];
       for (i = 0; i < n; i++) {
           items[i] = elem;       // Copies the same item
           Py_INCREF(elem);
       }
       return (PyObject *) np;
   }
   

2. 当您使用列表理解来构建列表时，Python无法知道正在创建的列表的实际大小，因此它最初会分配一块内存，而对象的一个新副本存储在列表中。当列表超出分配的长度时，它必须再次分配内存并继续创建新对象并将其存储在列表中。