Python3.x 预分配一个无列表

发布于03月06日

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

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

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

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

[None] * n→ 分配两个列表
[None for x in range(n)]-或Python 中的xrange→ 建造另一个物体

一个明显比另一个好吗？

如果我们是n = len(input)人呢？既然input已经存在，那么[None for x in input]会有更好的表现吗？

推荐答案

在这两个选项之间，第一个显然更好，因为不涉及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

Update:

list.append也有一个O(1) complexity，如果你把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