Python 列表理解性能

Question

我做了一些实验，用两种方法来初始化一个二维列表。

我在本地 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)

Answer 1

请注意，您正在做两件不同的事情。你打算使用:

[[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源代码如下:

https://github.com/python/cpython/blob/48ed88a93bb0bbeaae9a4cfaa533e4edf13bcb51/Objects/listobject.c#L504

如您所见，它将底层缓冲区分配到它需要的确切大小:

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++;
    }
}