比较列表推导和显式循环(3个数组生成器比1更快地循环)

Question

我做了功课,我意外地发现了算法的速度奇怪的不一致.这是相同功能bur的2个版本的代码bur与1差异:在第一个版本中我使用3次数组生成器来过滤一些数组,在第二个版本中我使用1 for循环与3 if语句来做同样的过滤器工作.

所以,这是第一版的代码:

def kth_order_statistic(array, k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = [x for x in array if x < pivot]
    m = [x for x in array if x == pivot]
    r = [x for x in array if x > pivot]
    if k <= len(l):
            return kth_order_statistic(l, k)
    elif k > len(l) + len(m):
            return kth_order_statistic(r, k - len(l) - len(m))
    else:
            return m[0]

这里是第二版的代码:

def kth_order_statistic2(array, k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = []
    m = []
    r = []
    for x in array:
        if x < pivot:
            l.append(x)
        elif x > pivot:
            r.append(x)
        else:
            m.append(x)

    if k <= len(l):
        return kth_order_statistic2(l, k)
    elif k > len(l) + len(m):
        return kth_order_statistic2(r, k - len(l) - len(m))
    else:
        return m[0]

第一版的IPython输出:

In [4]: %%timeit
   ...: A = range(100000)
   ...: shuffle(A)
   ...: k = randint(1, len(A)-1)
   ...: order_statisctic(A, k)
   ...:
10 loops, best of 3: 120 ms per loop

对于第二版:

In [5]: %%timeit
   ...: A = range(100000)
   ...: shuffle(A)
   ...: k = randint(1, len(A)-1)
   ...: kth_order_statistic2(A, k)
   ...:
10 loops, best of 3: 169 ms per loop

那么为什么第一版比第二版快呢？我还使用filter()函数而不是数组生成器制作了第三个版本,它比第二个版本慢(它每个循环得到218毫秒)

Answer 1

使用简单for比快list comprehesion.它快了近2倍.检查以下结果:

使用list comprehension:58 usec

moin@moin-pc:~$ python -m timeit "[i for i in range(1000)]"
10000 loops, best of 3: 58 usec per loop

使用for循环:37.1 usec

moin@moin-pc:~$ python -m timeit "for i in range(1000): i"
10000 loops, best of 3: 37.1 usec per loop

但在你的情况下,for比列表理解花费更多的时间不是因为你的循环很慢.但是因为.append()你在代码中使用.

with append()in for循环`:114 usec

moin@moin-pc:~$ python -m timeit "my_list = []" "for i in range(1000): my_list.append(i)"
10000 loops, best of 3: 114 usec per loop

这清楚地表明它是循环.append()所花费的时间的两倍for.

但是,在storing the "list.append" in different variable:69.3 usec

moin@moin-pc:~$ python -m timeit "my_list = []; append = my_list.append" "for i in range(1000): append(i)"
10000 loops, best of 3: 69.3 usec per loop

与上述比较中的最后一个案例相比,性能有了很大的提高,结果与之相当list comprehension.这意味着,不是my_list.append()每次调用,而是通过将函数的引用存储在另一个变量中,即append_func = my_list.append使用该变量进行调用,来提高性能append_func(i).

这也证明,与直接使用类的对象进行函数调用相比,调用存储在变量中的类函数更快.

感谢Stefan提出最后一个案例.

Answer 2

让我们定义回答问题所需的函数并将它们计时:

In [18]: def iter():
    l = [x for x in range(100) if x > 10]
   ....:

In [19]: %timeit iter()
100000 loops, best of 3: 7.92 µs per loop

In [20]: def loop():
    l = []
    for x in range(100):
        if x > 10:
            l.append(x)
   ....:

In [21]: %timeit loop()
10000 loops, best of 3: 20 µs per loop

In [22]: def loop_fast():
    l = []
    for x in range(100):
        if x > 10:
            pass
   ....:

In [23]: %timeit loop_fast()
100000 loops, best of 3: 4.69 µs per loop

我们可以看到没有append命令的for循环和列表理解一样快.实际上,如果我们看一下字节码,我们可以看到,在列表解析的情况下,python能够使用一个名为LIST_APPEND的内置字节码命令,而不是:

• 加载列表:40 LOAD_FAST
• 加载属性:43 LOAD_ATTRIBUTE
• 调用加载的函数:49 CALL_FUNCTION
• 卸载列表(？):52 POP_TOP

正如您从下面的输出中看到的那样,列表理解和"loop_fast"函数缺少前一个字节码.比较三个函数的时间显然是那些负责三种方法的不同时间.

In [27]: dis.dis(iter)
  2          0 BUILD_LIST             0
             3 LOAD_GLOBAL            0 (range)
             6 LOAD_CONST             1 (1)
             9 LOAD_CONST             2 (100)
            12 CALL_FUNCTION          2
            15 GET_ITER
       >>   16 FOR_ITER              24 (to 43)
            19 STORE_FAST             0 (x)
            22 LOAD_FAST              0 (x)
            25 LOAD_CONST             2 (100)
            28 COMPARE_OP             4 (>)
            31 POP_JUMP_IF_FALSE     16
            34 LOAD_FAST              0 (x)
            37 LIST_APPEND            2
            40 JUMP_ABSOLUTE         16
       >>   43 STORE_FAST             1 (l)
            46 LOAD_CONST             0 (None)
            49 RETURN_VALUE

In [28]: dis.dis(loop)
  2          0 BUILD_LIST             0
             3 STORE_FAST             0 (1)

  3          6 SETUP_LOOP            51 (to 60)
             9 LOAD_GLOBAL            0 (range)
            12 LOAD_CONST             1 (1)
            15 LOAD_CONST             2 (100)
            18 CALL_FUNCTION          2
            21 GET_ITER
       >>   22 FOR_ITER              34 (to 59)
            25 STORE_FAST             1 (x)

  4         28 LOAD_FAST              1 (x)
            31 LOAD_CONST             3 (10)
            34 COMPARE_OP             4 (>)
            37 POP_JUMP_IF_FALSE     22

  5         40 LOAD_FAST              0 (l)
            43 LOAD_ATTR              1 (append)
            46 LOAD_FAST              1 (x)
            49 CALL_FUNCTION          1
            52 POP_TOP
            53 JUMP_ABSOLUTE         22
            56 JUMP_ABSOLUTE         22
       >>   59 POP_BLOCK
       >>   60 LOAD_CONST             0 (None)
            63 RETURN_VALUE

In [29]: dis.dis(loop_fast)
  2          0 BUILD_LIST             0
             3 STORE_FAST             0 (1)

  3          6 SETUP_LOOP            38 (to 47)
             9 LOAD_GLOBAL            0 (range)
            12 LOAD_CONST             1 (1)
            15 LOAD_CONST             2 (100)
            18 CALL_FUNCTION          2
            21 GET_ITER
       >>   22 FOR_ITER              21 (to 46)
            25 STORE_FAST             1 (x)

  4         28 LOAD_FAST              1 (x)
            31 LOAD_CONST             3 (10)
            34 COMPARE_OP             4 (>)
            37 POP_JUMP_IF_FALSE     22

  5         40 JUMP_ABSOLUTE         22
            43 JUMP_ABSOLUTE         22
       >>   46 POP_BLOCK
       >>   47 LOAD_CONST             0 (None)
            50 RETURN_VALUE