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

问题描述 投票：0回答：4

我做了功课，无意中发现算法的速度出现了奇怪的不一致。 这是相同函数的代码的 2 个版本，但有 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 毫秒）

python arrays python-2.7 time list-comprehension
4个回答
10
投票

使用简单的

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
循环比
list comprehension
花费更多时间不是因为您的
for
循环很慢，而是因为您在代码中使用的
.append()
方法。

在 

append()
循环中使用 
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
循环所用时间的两倍。

但是，将 

list.append()
存储在不同的变量中： 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通知最后一个案例。

7
投票
让我们定义回答问题所需的函数并为其计时：

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”函数缺少前面的字节码。比较这三个函数的 timeit 可以清楚地看出，这三个函数的时间不同。

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
3
投票
让我们打消这个疑虑：

第二个版本稍微快一些：列表理解更快，但是两个数组循环以及在一次迭代中丢弃了尽可能多的条件。

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


python : --- 25.8894710541 seconds --- --- 24.073086977 seconds --- --- 32.9823839664 seconds --- ipython --- 25.7450709343 seconds --- --- 22.7140650749 seconds --- --- 35.2958850861 seconds ---
根据随机抽签，时间可能会有所不同，但三者之间的差异几乎相同。

2
投票
算法结构不同，条件结构要受罪。附加到 r 和 m 的测试可以被先前的测试丢弃。关于 for 循环与

append

 和列表理解的更严格比较将与非最佳以下

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)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.