列表理解与生成器表达式的奇怪 timeit 结果? [英] List comprehension vs generator expression's weird timeit results?
问题描述
我正在回答这个问题，我更喜欢这里的生成器表达式并使用它，我认为它会更快，因为生成器不需要先创建整个列表:
<预><代码>>>>lis=[['a','b','c'],['d','e','f']]>>>'d' in (y for x in lis for y in x)真的Levon 在他的解决方案中使用了列表理解，
<预><代码>>>>lis = [['a','b','c'],['d','e','f']]>>>'d' in [j for i in mylist for j in i]真的但是当我做这些 LC 的 timeit 结果时，它比生成器快:
~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f']]" "'d' in (y for x in lis for y in x)"100000 个循环，最好的 3 个:每个循环 2.36 微秒~$ python -m timeit -s "lis=[['a','b','c'],['d','e','f']]" "'d' in [y for x在 lis 中为 y 在 x]"100000 个循环，最好的 3 个:每个循环 1.51 微秒然后我增加了列表的大小，并再次计时:
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 代表 x 中的 x 代表 x 中的 y)"100000 个循环，最好的 3 个:每个循环 2.96 微秒~$ 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对于 y 在 x]"100000 个循环，最好的 3 个:每个循环 7.4 微秒~$ 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在 x]"100000 个循环，最好的 3 个:每个循环 5.61 微秒~$ 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在 x)"100000 个循环，3 个最佳:每个循环 9.76 微秒~$ 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在 x)"100000 个循环，最好的 3 个:每个循环 8.94 微秒~$ 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在 x]"100000 个循环，最好的 3 个:每个循环 7.13 微秒扩展 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():返回 'd' in [y for x in lis for y in x]def ge_11():返回 11 in (y for x in lis for y in x)def lc_11():返回 11 in [y for x in lis for y in x]def ge_18():返回 18 in (y for x in lis for y in x)def lc_18():返回 18 in [y for x in lis for y in x]对于 xrange(100000) 中的 i:ge_d()lc_d()ge_11()lc_11()ge_18()lc_18()以下是相关结果，重新排序以使模式更清晰.
在 2.830 秒内调用 5400002 次函数订购者:标准名称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)创建一个生成器表达式相当于创建一个生成器函数并调用它.这说明了对 next 被调用 4 次，直到达到 d，总共调用 5 次(100000 次迭代 = ncalls = 500000).第二种情况，调用了17次，总共调用了18次；第三次，24次，共25次.
在第一种情况下，genex 优于列表理解，但是对 next 的额外调用占了列表理解速度和生成器表达式速度之间的大部分差异和第三种情况.
我不确定剩下的时间是什么；即使没有额外的函数调用，生成器表达式似乎也会慢一点.我想这证实了 inspectorG4dget 的断言创建生成器推导式比列表推导式具有更多的本机开销."但无论如何，这很清楚地表明，由于对 next 的调用，生成器表达式主要变慢了.
我要补充一点，当短路没有帮助时，列表推导式仍然更快，即使对于非常大的列表也是如此.例如:
<预><代码>>>>计数器 = itertools.count()>>>大声笑 = [[counter.next(), counter.next(), counter.next()]对于 _ 范围内(1000000)]>>>2999999 in (i for sublist in lol for i in sublist)真的>>>3000000 in(i 表示 lol 中的子列表，i 表示子列表中的 i)错误的>>>%timeit 2999999 in [i for sublist in lol for i in sublist]1 个循环，最好的 3 个:每个循环 312 毫秒>>>%timeit 2999999 in (i for sublist in lol for i in sublist)1 个循环，最好的 3 个:每个循环 351 毫秒>>>%timeit any([2999999 in sublist for sublist in lol])10 个循环，最好的 3 个:每个循环 161 毫秒>>>%timeit any(子列表中的 2999999 子列表中的子列表)10 个循环，最好的 3 个:每个循环 163 毫秒>>>%timeit for i in [2999999 in sublist for sublist in lol]:通过1 个循环，最好的 3 个:每个循环 171 毫秒>>>%timeit for i in (2999999 in sublist for sublist in lol): pass1 个循环，最好的 3 个:每个循环 183 毫秒如您所见，当短路无关紧要时，即使对于一百万个项目长的列表列表，列表解析始终更快.显然，对于 in 在这些规模下的实际使用，由于短路，生成器会更快.但是对于其他类型的迭代任务，它们在项目数量上确实是线性的，列表推导式总是要快得多.如果您需要对列表执行多个测试，则尤其如此；您可以非常快速地迭代一个已经构建的列表推导式:
在这种情况下，列表理解要快一个数量级！
当然，这只会在内存不足之前保持正确.这让我想到了最后一点.使用生成器有两个主要原因:利用短路和节省内存.对于非常大的序列/可迭代对象，生成器是显而易见的方法，因为它们可以节省内存.但是，如果短路不是一种选择，那么您几乎从不为速度选择生成器而不是列表.您选择它们是为了节省内存，这始终是一种权衡.
I was answering this question, I preferred generator expression here and used this, which I thought would be faster as generator doesn't need to create the whole list first:
>>> lis=[['a','b','c'],['d','e','f']]
>>> 'd' in (y for x in lis for y in x)
True
And Levon used list comprehension in his solution,
>>> lis = [['a','b','c'],['d','e','f']]
>>> 'd' in [j for i in mylist for j in i]
True
But when I did the timeit results for these LC was faster than generator:
~$ 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
then I increased the size of list, and timed it again:
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]]
This time for searching 'd' generator was faster than LC, but when I searched a middle element(11) and the last element then LC again beats the generator expression, and I can't understand why?
~$ 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
Expanding on Paulo's answer, generator expressions are often slower than list comprehensions because of the overhead of function calls. In this case, the short-circuiting behavior of in offsets that slowness if the item is found fairly early, but otherwise, the pattern holds.
I ran a simple script through the profiler for a more detailed analysis. Here's the script:
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()
Here are the relevant results, reordered to make the patterns clearer.
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)
Creating a generator expression is equivalent to creating a generator function and calling it. That accounts for one call to <genexpr>. Then, in the first case, next is called 4 times, until d is reached, for a total of 5 calls (times 100000 iterations = ncalls = 500000). In the second case, it is called 17 times, for a total of 18 calls; and in the third, 24 times, for a total of 25 calls.
The genex outperforms the list comprehension in the first case, but the extra calls to next account for most of the difference between the speed of the list comprehension and the speed of the generator expression in the second and third cases.
>>> .634 - .278 - .333
0.023
>>> .806 - .371 - .344
0.091
I'm not sure what accounts for the remaining time; it seems that generator expressions would be a hair slower even without the additional function calls. I suppose this confirms inspectorG4dget's assertion that "creating a generator comprehension has more native overhead than does a list comprehension." But in any case, this shows pretty clearly that generator expressions are slower mostly because of calls to next.
I'll add that when short-circuiting doesn't help, list comprehensions are still faster, even for very large lists. For example:
>>> 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
As you can see, when short circuiting is irrelevant, list comprehensions are consistently faster even for a million-item-long list of lists. Obviously for actual uses of in at these scales, generators will be faster because of short-circuiting. But for other kinds of iterative tasks that are truly linear in the number of items, list comprehensions are pretty much always faster. This is especially true if you need to perform multiple tests on a list; you can iterate over an already-built list comprehension very quickly:
>>> 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
In this case, the list comprehension is an order of magnitude faster!
Of course, this only remains true until you run out of memory. Which brings me to my final point. There are two main reasons to use a generator: to take advantage of short circuiting, and to save memory. For very large seqences/iterables, generators are the obvious way to go, because they save memory. But if short-circuiting is not an option, you pretty much never choose generators over lists for speed. You chose them to save memory, and it's always a trade-off.
这篇关于列表理解与生成器表达式的奇怪 timeit 结果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
