Python列表理解性能

Question

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

我在当地的MacBookPro和Leetcode游乐场上进行了测试，结果显示第一种方法比第二种方法快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

我注意到不同的技术生成了不同的结构（正如我在一篇评论中所指出的），这种重写产生了相同的结构，但正如@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 2

这只是一个玩具实验，如果元素数据类型与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)

Answer 3

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

[[None] * n for _ in range(n)]

您已经将内部列表包装在一个额外的列表中，但这不会对计时结果产生很大影响。列表重复版本肯定更快

[None]*n非常快，它精确地分配底层缓冲区，然后执行C级循环[None for _ in range(n)]是一个使用append的python级循环，append是按固定时间摊销的，但会涉及缓冲区重新分配

只需查看字节码就可以给出一个提示：

>>> 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

基本上，所有的工作都是在{}中完成的。对于列表理解：

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