Python 3：创建 [func(i) for i in range(N)] 列表推导的最有效方法
假设我有一个函数 func(i)，它可以为一个整数 i 创建一个对象，而 N 是一个非负整数。那么，最快的方式来创建一个列表（不是范围）与这个列表相等是什么呢？
mylist = [func(i) for i in range(N)]
我不想使用一些高级的方法，比如在 C 语言中创建一个函数。我主要担心上面的列表推导式，因为我不确定 Python 是否知道 range(N) 的长度，从而能够提前分配 mylist 的空间，因此可能需要逐步重新分配列表。是这样吗？还是说 Python 足够聪明，能够先为 mylist 分配长度 N，然后再计算它的元素？如果不是，创建 mylist 的最佳方法是什么呢？也许这样？
mylist = [None]*N
for i in range(N): mylist[i] = func(i)
重新编辑：删除了之前编辑中误导的信息。
6 个回答
使用自动调整大小的数组和预先分配的数组在计算复杂度上没有区别。最坏情况下，它的成本大约是 O(2N)。具体可以参考这里：
函数调用的成本加上你函数里发生的事情，会让这个额外的 n 显得微不足道。这不是你需要担心的事情。直接使用列表推导式就可以了。
如果你使用 timeit 模块，你可能会得出一个相反的结论：列表推导式比预分配要快。
f=lambda x: x+1
N=1000000
def lc():
return [f(i) for i in range(N)]
def prealloc():
mylist = [None]*N
for i in range(N): mylist[i]=f(i)
return mylist
def xr():
return map(f,xrange(N))
if __name__=='__main__':
lc()
警告：这些结果是我电脑上的测试结果。你应该自己试试这些测试，因为你的结果可能会因为你使用的Python版本和硬件不同而有所不同。（见评论。）
% python -mtimeit -s"import test" "test.prealloc()"
10 loops, best of 3: 370 msec per loop
% python -mtimeit -s"import test" "test.lc()"
10 loops, best of 3: 319 msec per loop
% python -mtimeit -s"import test" "test.xr()"
10 loops, best of 3: 348 msec per loop
注意，与哈维尔的回答不同，我在使用“预分配”方法时，把 mylist = [None]*N 也算在 timeit 测试的时间里。（这不仅仅是准备工作的一部分，因为这段代码只有在使用预分配时才需要。）
PS. time 模块（和 time（unix）命令）可能会给出不可靠的结果。如果你想测量Python代码的执行时间，我建议你使用 timeit 模块。
有人说：“Python很聪明。只要你正在遍历的对象有一个__len__或__length_hint__的方法，Python就会调用它来确定大小，并提前分配数组。”
但据我所知，在列表推导式中并没有提前分配空间。Python无法从输入的大小判断输出的大小会是多少。
看看这段Python 2.6的代码：
>>> def foo(func, iterable):
... return [func(i) for i in iterable]
...
>>> import dis; dis.dis(foo)
2 0 BUILD_LIST 0 #### build empty list
3 DUP_TOP
4 STORE_FAST 2 (_[1])
7 LOAD_FAST 1 (iterable)
10 GET_ITER
>> 11 FOR_ITER 19 (to 33)
14 STORE_FAST 3 (i)
17 LOAD_FAST 2 (_[1])
20 LOAD_FAST 0 (func)
23 LOAD_FAST 3 (i)
26 CALL_FUNCTION 1
29 LIST_APPEND #### stack[-2].append(stack[-1]); pop()
30 JUMP_ABSOLUTE 11
>> 33 DELETE_FAST 2 (_[1])
36 RETURN_VALUE
这段代码只是创建了一个空列表，然后把遍历得到的内容一个个添加进去。
现在看看这段代码，它在列表推导式中加了一个'if'条件：
>>> def bar(func, iterable):
... return [func(i) for i in iterable if i]
...
>>> import dis; dis.dis(bar)
2 0 BUILD_LIST 0
3 DUP_TOP
4 STORE_FAST 2 (_[1])
7 LOAD_FAST 1 (iterable)
10 GET_ITER
>> 11 FOR_ITER 30 (to 44)
14 STORE_FAST 3 (i)
17 LOAD_FAST 3 (i)
20 JUMP_IF_FALSE 17 (to 40)
23 POP_TOP
24 LOAD_FAST 2 (_[1])
27 LOAD_FAST 0 (func)
30 LOAD_FAST 3 (i)
33 CALL_FUNCTION 1
36 LIST_APPEND
37 JUMP_ABSOLUTE 11
>> 40 POP_TOP
41 JUMP_ABSOLUTE 11
>> 44 DELETE_FAST 2 (_[1])
47 RETURN_VALUE
>>>
这段代码和之前的差不多，只是多了一些代码来避免使用列表的添加操作。
在Python 3.X中，你需要更深入地理解：
>>> import dis
>>> def comprehension(f, iterable): return [f(i) for i in iterable]
...
>>> dis.dis(comprehension)
1 0 LOAD_CLOSURE 0 (f)
3 BUILD_TUPLE 1
6 LOAD_CONST 1 (<code object <listcomp> at 0x00C4B8D
8, file "<stdin>", line 1>)
9 MAKE_CLOSURE 0
12 LOAD_FAST 1 (iterable)
15 GET_ITER
16 CALL_FUNCTION 1
19 RETURN_VALUE
>>> dis.dis(comprehension.__code__.co_consts[1])
1 0 BUILD_LIST 0
3 LOAD_FAST 0 (.0)
>> 6 FOR_ITER 18 (to 27)
9 STORE_FAST 1 (i)
12 LOAD_DEREF 0 (f)
15 LOAD_FAST 1 (i)
18 CALL_FUNCTION 1
21 LIST_APPEND 2
24 JUMP_ABSOLUTE 6
>> 27 RETURN_VALUE
>>>
其实还是老套路：先创建一个空列表，然后遍历可迭代对象，根据需要往列表里添加内容。我在这里没有看到提前分配空间的情况。
你想的那种优化其实是在某个单独的操作码内部使用的，比如list.extend(iterable)的实现可以提前分配空间，如果iterable能准确报告它的长度。而list.append(object)只接收一个单独的对象，而不是一个可迭代的对象。