在Python中创建一个具有初始容量的列表
像这样的代码经常会出现：
l = []
while foo:
# baz
l.append(bar)
# qux
如果你打算往列表里添加成千上万个元素，这样的做法会非常慢，因为列表需要不断地调整大小来容纳新元素。
在Java中，你可以创建一个初始容量的ArrayList。如果你大概知道你的列表会有多大，这样做会高效得多。
我知道像这样的代码通常可以改写成列表推导式。不过，如果for/while循环非常复杂，那就不太可行了。对于我们Python程序员来说，有没有类似的做法呢？
11 个回答
简短版本：使用
pre_allocated_list = [None] * size
来预先分配一个列表（也就是说，可以直接访问'大小'个元素，而不是通过逐步添加来形成列表）。这个操作是非常快的，即使是对于大列表也是如此。分配新的对象，然后再将它们赋值给列表元素，这个过程会花费更长的时间，并且在性能上会成为你程序的瓶颈。
详细版本：
我认为初始化时间是需要考虑的。
因为在Python中，一切都是引用，所以无论你是把每个元素设置为None还是某个字符串，效果都是一样的——它们都是引用。不过，如果你想为每个元素创建一个新的对象来引用，那就会花费更多时间。
对于Python 3.2：
import time
import copy
def print_timing (func):
def wrapper (*arg):
t1 = time.time()
res = func (*arg)
t2 = time.time ()
print ("{} took {} ms".format (func.__name__, (t2 - t1) * 1000.0))
return res
return wrapper
@print_timing
def prealloc_array (size, init = None, cp = True, cpmethod = copy.deepcopy, cpargs = (), use_num = False):
result = [None] * size
if init is not None:
if cp:
for i in range (size):
result[i] = init
else:
if use_num:
for i in range (size):
result[i] = cpmethod (i)
else:
for i in range (size):
result[i] = cpmethod (cpargs)
return result
@print_timing
def prealloc_array_by_appending (size):
result = []
for i in range (size):
result.append (None)
return result
@print_timing
def prealloc_array_by_extending (size):
result = []
none_list = [None]
for i in range (size):
result.extend (none_list)
return result
def main ():
n = 1000000
x = prealloc_array_by_appending(n)
y = prealloc_array_by_extending(n)
a = prealloc_array(n, None)
b = prealloc_array(n, "content", True)
c = prealloc_array(n, "content", False, "some object {}".format, ("blah"), False)
d = prealloc_array(n, "content", False, "some object {}".format, None, True)
e = prealloc_array(n, "content", False, copy.deepcopy, "a", False)
f = prealloc_array(n, "content", False, copy.deepcopy, (), False)
g = prealloc_array(n, "content", False, copy.deepcopy, [], False)
print ("x[5] = {}".format (x[5]))
print ("y[5] = {}".format (y[5]))
print ("a[5] = {}".format (a[5]))
print ("b[5] = {}".format (b[5]))
print ("c[5] = {}".format (c[5]))
print ("d[5] = {}".format (d[5]))
print ("e[5] = {}".format (e[5]))
print ("f[5] = {}".format (f[5]))
print ("g[5] = {}".format (g[5]))
if __name__ == '__main__':
main()
评估：
prealloc_array_by_appending took 118.00003051757812 ms
prealloc_array_by_extending took 102.99992561340332 ms
prealloc_array took 3.000020980834961 ms
prealloc_array took 49.00002479553223 ms
prealloc_array took 316.9999122619629 ms
prealloc_array took 473.00004959106445 ms
prealloc_array took 1677.9999732971191 ms
prealloc_array took 2729.999780654907 ms
prealloc_array took 3001.999855041504 ms
x[5] = None
y[5] = None
a[5] = None
b[5] = content
c[5] = some object blah
d[5] = some object 5
e[5] = a
f[5] = []
g[5] = ()
如你所见，仅仅创建一个大列表，里面都是指向同一个None对象的引用，所需时间非常少。
在列表前面添加或扩展会花费更长时间（我没有做平均，但运行几次后可以告诉你，扩展和添加大致花费的时间是一样的）。
为每个元素分配新的对象——这才是最耗时间的。而S.Lott的回答就是这样做的——每次都格式化一个新的字符串。这并不是严格要求的——如果你想预先分配一些空间，只需创建一个包含None的列表，然后随意给列表元素赋值。无论如何，生成数据所需的时间总是比添加或扩展列表要长，无论你是在创建列表时生成数据，还是之后生成。但如果你想要一个稀疏填充的列表，那么从一个包含None的列表开始肯定会更快。
Python 的列表没有内置的预分配功能。如果你真的需要创建一个列表，并且想要避免在添加元素时的额外开销（而且你应该确认确实需要这样做），你可以这样做：
l = [None] * 1000 # Make a list of 1000 None's
for i in xrange(1000):
# baz
l[i] = bar
# qux
也许你可以考虑用生成器来代替列表：
def my_things():
while foo:
#baz
yield bar
#qux
for thing in my_things():
# do something with thing
这样的话，列表就不会全部存储在内存中了，而是根据需要动态生成。
警告：这个答案有争议。请查看评论。
def doAppend( size=10000 ):
result = []
for i in range(size):
message= "some unique object %d" % ( i, )
result.append(message)
return result
def doAllocate( size=10000 ):
result=size*[None]
for i in range(size):
message= "some unique object %d" % ( i, )
result[i]= message
return result
结果。（对每个函数进行144次评估，并计算平均时间）
simple append 0.0102
pre-allocate 0.0098
结论。几乎没有影响。
过早的优化是万恶之源。