比较列表理解和显式循环（3个数组生成器比1个for loop快）

Question

我做了家庭作业，不小心发现了算法速度上的一个奇怪的不一致。 这里有两个版本的代码，同一个函数有一个区别：在第一个版本中，我使用3倍数组生成器来过滤一些数组，在第二个版本中，我使用1for循环和3if语句来执行相同的过滤工作。在

这里是第1版代码：

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]

第二版代码：

^{pr2}$

IPython第1版输出：

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

^{pr2}$

但是在您的例子中，for比列表理解要花更多的时间，不是因为for循环太慢。但由于.append()您正在代码中使用。

在for循环中使用append()时：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使用c

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)进行调用来提高性能。在

这也证明，调用存储在变量中的类的函数比直接使用类的对象进行函数调用要快。在

感谢你提醒最后一个案子。

Answer 2

让我们消除这种疑虑： 第二个版本稍快：列表理解更快，但两个数组循环和同样多的条件条件在一次迭代中被丢弃。在

def kth_order_statistic1(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_statistic1(l, k)
    elif k > len(l) + len(m):
        return kth_order_statistic1(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]

def kth_order_statistic3(array,k):
    pivot = (array[0] + array[len(array) - 1]) // 2
    l = []
    m = []
    r = []

    for x in array: 
       if x < pivot: l.append(x)
    for x in array: 
       if x== pivot: m.append(x)
    for x in array: 
       if x > pivot: r.append(x)

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

import time
import random
if __name__ == '__main__':

    A = range(100000)
    random.shuffle(A)
    k = random.randint(1, len(A)-1)

    start_time = time.time()
    for x in range(1000) :
        kth_order_statistic1(A,k)
    print("--- %s seconds ---" % (time.time() - start_time))

    start_time = time.time()
    for x in range(1000) :
        kth_order_statistic2(A,k)
    print("--- %s seconds ---" % (time.time() - start_time))

    start_time = time.time()
    for x in range(1000) :
        kth_order_statistic3(A,k)
    print("--- %s seconds ---" % (time.time() - start_time))

^{pr2}$

时间可能因随机抽签而不同，但三者之间的差异几乎相同。在

Answer 3

让我们定义回答问题所需的函数，并对其计时：

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循环与list理解一样快。实际上，如果我们看一下字节码，我们可以看到，在列表理解的情况下，python可以使用一个名为list_APPEND的内置字节码命令，而不是：

• 加载列表：40加载快速
• 加载属性u43
• 调用加载函数：49 Call_函数
• 卸载列表（？）：52流行上衣

从下面的输出中可以看到，前面的字节码在列表理解和“循环快速”函数中丢失。比较这三种方法的时间，可以清楚地看出，这三种方法的计时不同。在

^{pr2}$