预分配无列表

Question

假设您要编写一个产生对象列表的函数,并且事先知道此n列表的长度.

在python中,列表支持O(1)中的索引访问,因此可以预先分配列表并使用索引访问它而不是分配空列表并使用该append()方法.这是因为如果空间不足,我们可以避免扩展整个列表的负担.

如果我正在使用python,那么在任何情况下表演都不是那么相关,但是预先分配列表的更好方法是什么？

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

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

一个明显优于另一个？

如果我们是这样的话n = len(input)怎么办？既然input已经存在,[None for x in input]会有更好的表现[None] * len(input)吗？

Answer 1

当您将项附加到列表时,Python'over-allocation',请参阅列表对象的源代码.这意味着,例如,当将1个项目添加到8个项目的列表中时,它实际上为8个新项目腾出空间,并且仅使用其中的第一个项目.接下来的7个附加是"免费".

在许多语言(例如Matlab)中,总是告诉您需要预先分配向量,因为在循环期间追加非常昂贵.在最坏的情况下,将单个项目附加到长度列表可能会n花费O(n)时间,因为您可能必须创建更大的列表并复制所有现有项目.您需要在每次迭代时执行此操作,因此添加n项目的总成本是O(n^2)ouch.Python的预分配方案将阵列的成本分摊到许多单一附加(参见摊销成本),有效地降低了单个附加O(1)的成本和添加n项目的总成本O(n).

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

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

Answer 2

在这两个选项之间,第一个选项明显更好,因为不涉及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具有O(1)复杂性,如果将list.append方法分配给变量,它可能是比预创建列表更好的选择.

>>> 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