列表理解与生成器表达式的奇怪时间结果？

Question

我正在回答这个问题，在这里我更喜欢生成器表达式并使用了它，我认为这样做会更快，因为生成器不需要先创建整个列表：

>>> lis=[['a','b','c'],['d','e','f']]
>>> 'd' in (y for x in lis for y in x)
True

Levon在解决方案中使用了列表理解功能，

>>> lis = [['a','b','c'],['d','e','f']]
>>> 'd' in [j for i in mylist for j in i]
True

但是当我做这些LC的时间结果比生成器快时：

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f']]" "'d' in (y for x in lis for y in x)"
    100000 loops, best of 3: 2.36 usec per loop
~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f']]" "'d' in [y for x in lis for y in x]"
    100000 loops, best of 3: 1.51 usec per loop

然后我增加了列表的大小，并再次计时：

lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]

这次搜索'd'生成器的时间比LC快，但是当我搜索中间元素（11）和最后一个元素时，LC再次击败了生成器表达式，我不明白为什么？

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "'d' in (y for x in lis for y in x)"
    100000 loops, best of 3: 2.96 usec per loop

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "'d' in [y for x in lis for y in x]"
    100000 loops, best of 3: 7.4 usec per loop

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "11 in [y for x in lis for y in x]"
100000 loops, best of 3: 5.61 usec per loop

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "11 in (y for x in lis for y in x)"
100000 loops, best of 3: 9.76 usec per loop

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "18 in (y for x in lis for y in x)"
100000 loops, best of 3: 8.94 usec per loop

~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "18 in [y for x in lis for y in x]"
100000 loops, best of 3: 7.13 usec per loop

Answer 1

扩展Paulo的答案，由于函数调用的开销，生成器表达式通常比列表理解要慢。在这种情况下，in如果发现的时间很早，则抵消了这种缓慢现象的短路行为，但否则，该模式仍然成立。

我通过探查器运行了一个简单的脚本，以进行更详细的分析。这是脚本：

lis=[['a','b','c'],['d','e','f'],[1,2,3],[4,5,6],
     [7,8,9],[10,11,12],[13,14,15],[16,17,18]]

def ge_d():
    return 'd' in (y for x in lis for y in x)
def lc_d():
    return 'd' in [y for x in lis for y in x]

def ge_11():
    return 11 in (y for x in lis for y in x)
def lc_11():
    return 11 in [y for x in lis for y in x]

def ge_18():
    return 18 in (y for x in lis for y in x)
def lc_18():
    return 18 in [y for x in lis for y in x]

for i in xrange(100000):
    ge_d()
    lc_d()
    ge_11()
    lc_11()
    ge_18()
    lc_18()

以下是相关结果，已重新排序以使模式更清晰。

         5400002 function calls in 2.830 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    0.158    0.000    0.251    0.000 fop.py:3(ge_d)
   500000    0.092    0.000    0.092    0.000 fop.py:4(<genexpr>)
   100000    0.285    0.000    0.285    0.000 fop.py:5(lc_d)

   100000    0.356    0.000    0.634    0.000 fop.py:8(ge_11)
  1800000    0.278    0.000    0.278    0.000 fop.py:9(<genexpr>)
   100000    0.333    0.000    0.333    0.000 fop.py:10(lc_11)

   100000    0.435    0.000    0.806    0.000 fop.py:13(ge_18)
  2500000    0.371    0.000    0.371    0.000 fop.py:14(<genexpr>)
   100000    0.344    0.000    0.344    0.000 fop.py:15(lc_18)

创建生成器表达式等效于创建生成器函数并对其进行调用。占一通电话<genexpr>。然后，在第一种情况下，next被调用4次，直到d达到为止，总共5次调用（时间100000次迭代=
ncalls = 500000次）。在第二种情况下，它被调用了17次，总共有18次调用。第三次，共24次，总共25次通话。

在第一种情况下，genex的性能优于列表理解，但是next在第二和第三种情况下，额外的调用要考虑列表理解的速度与生成器表达式的速度之间的大部分差异。

>>> .634 - .278 - .333
0.023
>>> .806 - .371 - .344
0.091

我不确定剩下的时间是什么？似乎即使没有附加的函数调用，生成器表达式也要慢一些。我想这证实了inspectorG4dget的断言：“创建生成器理解要比列表理解具有更多的本机开销。”
但是无论如何，这很清楚地表明，生成器表达式的执行速度较慢， 主要是 因为对的调用next。

我还要补充一点，当短路无济于事时，即使对于非常大的列表，列表理解 仍然会 更快。例如：

>>> counter = itertools.count()
>>> lol = [[counter.next(), counter.next(), counter.next()] 
           for _ in range(1000000)]
>>> 2999999 in (i for sublist in lol for i in sublist)
True
>>> 3000000 in (i for sublist in lol for i in sublist)
False
>>> %timeit 2999999 in [i for sublist in lol for i in sublist]
1 loops, best of 3: 312 ms per loop
>>> %timeit 2999999 in (i for sublist in lol for i in sublist)
1 loops, best of 3: 351 ms per loop
>>> %timeit any([2999999 in sublist for sublist in lol])
10 loops, best of 3: 161 ms per loop
>>> %timeit any(2999999 in sublist for sublist in lol)
10 loops, best of 3: 163 ms per loop
>>> %timeit for i in [2999999 in sublist for sublist in lol]: pass
1 loops, best of 3: 171 ms per loop
>>> %timeit for i in (2999999 in sublist for sublist in lol): pass
1 loops, best of 3: 183 ms per loop

如您所见，当短路无关紧要时，即使对于一百万个项目长的列表，列表理解也 始终
更快。显然，对于in这些规模的实际使用，由于短路，发电机将更快。但是对于在项目数量上真正线性的其他种类的迭代任务，列表理解 总是
快得多。如果您需要在一个列表上执行多个测试，则尤其如此。您可以 非常快速地 遍历已构建的列表理解：

>>> incache = [2999999 in sublist for sublist in lol]
>>> get_list = lambda: incache
>>> get_gen = lambda: (2999999 in sublist for sublist in lol)
>>> %timeit for i in get_list(): pass
100 loops, best of 3: 18.6 ms per loop
>>> %timeit for i in get_gen(): pass
1 loops, best of 3: 187 ms per loop

在这种情况下，列表理解要快一个数量级！

当然，只有在内存用完之前，情况才会如此。这把我带到了最后一点。使用发生器的主要原因有两个：利用短路的优势并节省内存。对于非常大的序列/可迭代对象，生成器是显而易见的方法，因为它们可以节省内存。但是，如果不能选择短路，那么您几乎
永远不会 在 速度 列表上选择发电机。您选择它们​​来节省内存，这始终是一个权衡。