我做了一些实验,用两种方法来初始化一个二维列表。
我在本地 Macbook Pro 和 Leetcode playground 上都进行了测试,结果显示第一种方法比第二种方法快 4-5 倍。
谁能解释列表理解的性能滞后?
n = 999
t0 = time.time()
arr1 = [[None] * n for _ in range(n)]
t1 = time.time()
print(t1 - t0)
t2 = time.time()
arr2 = [[None for _ in range(n)] for _ in range(n)]
t3 = time.time()
print(t3 - t2)
最佳答案
请注意,您正在做两件不同的事情。你打算使用:
[[None] * n for _ in range(n)]
您已将内部列表包装在一个附加列表中,但这不会对计时结果产生巨大影响。列表重复版本肯定更快。
[None]*n
非常快,它准确分配底层缓冲区,然后执行 C 级循环。 [None for _ in range(n)]
是一个使用 append 的 python 级循环,它是摊销常数时间但会涉及缓冲区重新分配。
只要看一下字节码就可以给出提示:
>>> import dis
>>> dis.dis('[None]*n')
1 0 LOAD_CONST 0 (None)
2 BUILD_LIST 1
4 LOAD_NAME 0 (n)
6 BINARY_MULTIPLY
8 RETURN_VALUE
基本上,所有工作都在 BINARY_MULTIPLY
中完成。对于列表理解:
>>> dis.dis("[None for _ in range(n)]")
1 0 LOAD_CONST 0 (<code object <listcomp> at 0x7fc06e31bea0, file "<dis>", line 1>)
2 LOAD_CONST 1 ('<listcomp>')
4 MAKE_FUNCTION 0
6 LOAD_NAME 0 (range)
8 LOAD_NAME 1 (n)
10 CALL_FUNCTION 1
12 GET_ITER
14 CALL_FUNCTION 1
16 RETURN_VALUE
Disassembly of <code object <listcomp> at 0x7fc06e31bea0, file "<dis>", line 1>:
1 0 BUILD_LIST 0
2 LOAD_FAST 0 (.0)
>> 4 FOR_ITER 8 (to 14)
6 STORE_FAST 1 (_)
8 LOAD_CONST 0 (None)
10 LIST_APPEND 2
12 JUMP_ABSOLUTE 4
>> 14 RETURN_VALUE
>>>
循环工作是在 Python 解释器级别完成的。此外,它通过 .append
增长列表,这在算法上是高效的,但仍然比列表重复完成的慢,后者全部插入 C 层。
C源代码如下:
如您所见,它将底层缓冲区分配到它需要的确切大小:
np = (PyListObject *) PyList_New(size);
然后,它进行快速循环,在不重新分配的情况下填满缓冲区。最一般的情况:
p = np->ob_item;
items = a->ob_item;
for (i = 0; i < n; i++) {
for (j = 0; j < Py_SIZE(a); j++) {
*p = items[j];
Py_INCREF(*p);
p++;
}
}
关于Python 列表理解性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65445377/