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)] 是一个使用附加的 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++;
    }
}

Answer 2

我注意到不同的技术正在生成不同的结构（正如我在评论中指出的那样）这种重写产生了相同的结构，但正如@juanpa arrivillaga 指出的那样，您实际上获得了对单个列表的多个引用，这将当您开始为数组元素赋值时显示。

import time
from pprint import pprint

n = 999 # for time test

# n = 5 # for structure printout test.

t0 = time.time()
arr1 = [[None] * n] * n
t1 = time.time()
print(t1 - t0)

t0 = time.time()
arr2 = [[None] * n for _ in range(n)]
t1 = time.time()
print(t1 - t0)

t2 = time.time()
arr3 = [[None for _ in range(n)] for _ in range(n)]
t3 = time.time()
print(t3 - t2)

if n<20:
    print (len(arr1),len(arr1[0]))
    pprint (arr1)
    print (len(arr2),len(arr2[0]))
    pprint (arr2)
    print (len(arr3),len(arr3[0]))
    pprint (arr3)

Answer 3

只是一个玩具实验，如果元素数据类型与numpy兼容，它可以进一步加快创建数组的速度

%timeit [[None] * n for _ in range(n)]
1.42 ms ± 6.84 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit [[None for _ in range(n)] for _ in range(n)]
17.3 ms ± 109 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit np.zeros((n,n))
148 µs ± 440 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Python 列表理解性能

Python list comprehension performance

python

list-comprehension