python - 比较列表理解和显式循环(3 个数组生成器比 1 个 for 循环更快)

Question

做作业的时候无意中发现了算法速度的奇怪不一致。这是具有相同功能的 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 毫秒)

Answer 1

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

使用列表理解: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 比列表理解花费更多时间，这并不是因为您的 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 循环的两倍。

但是，将“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

在上述比较中，与最后一种情况相比，性能有了巨大的提高，结果与列表理解的结果相当。这意味着，不是每次都调用 my_list.append()，而是可以通过将函数的引用存储在另一个变量中来提高性能，即 append_func = my_list.append 并使使用该变量 append_func(i) 的调用。

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

谢谢 Stefan通知最后一个案例。