擅长:python、mysql、java
<p>当您向列表追加一个项时,Python“over allocates”,请参见列表对象的<a href="http://svn.python.org/projects/python/trunk/Objects/listobject.c" rel="noreferrer">source-code</a>。这意味着,例如,在一个包含8个项的列表中添加1个项时,它实际上为8个新项腾出了空间,并且只使用其中的第一个项。接下来的7个附录是“免费的”。</p>
<p>在许多语言中(如Matlab),你总是被告知你需要预先分配向量,因为在循环过程中附加是非常昂贵的。在最坏的情况下,将单个项追加到长度为<code>n</code>的列表可能需要<code>O(n)</code>的时间,因为您可能需要创建一个更大的列表并复制所有现有项。每次迭代都需要这样做,所以添加<code>n</code>项的总成本是<code>O(n^2)</code>,哎哟。Python的预分配方案将数组增长的成本分摊到多个单个append上(参见<a href="http://en.wikipedia.org/wiki/Amortized_analysis" rel="noreferrer">amortized costs</a>),有效地降低了单个append的成本<code>O(1)</code>和添加<code>n</code>项的总成本<code>O(n)</code>。</p>
<p>在Python中,其余代码的开销通常很大,因此通过预分配可以获得的微小加速是微不足道的。因此,在大多数情况下,只需忘记预分配,除非探查器告诉您追加到列表是一个瓶颈。</p>
<p>其他的答案显示了列表预分配本身的一些概要,但这是无用的。唯一重要的是分析完整的代码,所有的计算都在循环中,有没有预分配。如果我的预测是正确的,那么差异是如此之小,以至于你赢得的计算时间与花在思考、编写和维护额外的行以预先分配列表上的时间相形见绌。</p>