列表推导与生成器表达式的奇怪的时间结果？
- 2025-02-21 08:50:00
- admin 原创
- 54
问题描述：
我正在回答这个问题，我更喜欢这里的生成器表达式并使用这个，我认为这会更快，因为生成器不需要先创建整个列表：
>>> 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
解决方案 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
在这种情况下，列表理解的速度要快一个数量级！
当然，这只在内存耗尽之前才会成立。这让我想到了最后一点。使用生成器有两个主要原因：利用短路和节省内存。对于非常大的序列/可迭代对象，生成器是显而易见的选择，因为它们可以节省内存。但如果短路不是一种选择，你几乎永远不会为了速度而选择生成器而不是列表。你选择它们是为了节省内存，而这总是一种权衡。
解决方案 2：
完全取决于数据。
生成器具有固定的设置时间，该时间必须在调用的项目数上摊销；列表推导最初速度更快，但随着使用更多内存和更大的数据集，速度会明显变慢。
回想一下，随着 cPython 列表的扩展，列表的大小会按照4、8、16、25、35、46、58、72、88等增长模式进行调整。对于较大的列表推导，Python 可能会分配比数据大小多 4 倍的内存。一旦您使用 VM --- 速度就会非常慢！但是，如前所述，对于小型数据集，列表推导比生成器更快。
考虑情况 1，一个 2x26 的列表列表：
LoL=[[c1,c2] for c1,c2 in zip(string.ascii_lowercase,string.ascii_uppercase)]
def lc_d(item='d'):
return item in [i for sub in LoL for i in sub]
def ge_d(item='d'):
return item in (y for x in LoL for y in x)
def any_lc_d(item='d'):
return any(item in x for x in LoL)
def any_gc_d(item='d'):
return any([item in x for x in LoL])
def lc_z(item='z'):
return item in [i for sub in LoL for i in sub]
def ge_z(item='z'):
return item in (y for x in LoL for y in x)
def any_lc_z(item='z'):
return any(item in x for x in LoL)
def any_gc_z(item='z'):
return any([item in x for x in LoL])
cmpthese.cmpthese([lc_d,ge_d,any_gc_d,any_gc_z,any_lc_d,any_lc_z, lc_z, ge_z])
这些时间结果：
rate/sec ge_z lc_z lc_d any_lc_z any_gc_z any_gc_d ge_d any_lc_d
ge_z 124,652 -- -10.1% -16.6% -44.3% -46.5% -48.5% -76.9% -80.7%
lc_z 138,678 11.3% -- -7.2% -38.0% -40.4% -42.7% -74.3% -78.6%
lc_d 149,407 19.9% 7.7% -- -33.3% -35.8% -38.2% -72.3% -76.9%
any_lc_z 223,845 79.6% 61.4% 49.8% -- -3.9% -7.5% -58.5% -65.4%
any_gc_z 232,847 86.8% 67.9% 55.8% 4.0% -- -3.7% -56.9% -64.0%
any_gc_d 241,890 94.1% 74.4% 61.9% 8.1% 3.9% -- -55.2% -62.6%
ge_d 539,654 332.9% 289.1% 261.2% 141.1% 131.8% 123.1% -- -16.6%
any_lc_d 647,089 419.1% 366.6% 333.1% 189.1% 177.9% 167.5% 19.9% --
现在考虑案例 2，该案例显示了 LC 和 gen 之间的巨大差异。在这种情况下，我们在 100 x 97 x 97 列表结构中寻找一个元素：
LoL=[[str(a),str(b),str(c)]
for a in range(100) for b in range(97) for c in range(97)]
def lc_10(item='10'):
return item in [i for sub in LoL for i in sub]
def ge_10(item='10'):
return item in (y for x in LoL for y in x)
def any_lc_10(item='10'):
return any([item in x for x in LoL])
def any_gc_10(item='10'):
return any(item in x for x in LoL)
def lc_99(item='99'):
return item in [i for sub in LoL for i in sub]
def ge_99(item='99'):
return item in (y for x in LoL for y in x)
def any_lc_99(item='99'):
return any(item in x for x in LoL)
def any_gc_99(item='99'):
return any([item in x for x in LoL])
cmpthese.cmpthese([lc_10,ge_10,any_lc_10,any_gc_10,lc_99,ge_99,any_lc_99,any_gc_99],c=10,micro=True)
这些时候的结果：
rate/sec usec/pass ge_99 lc_99 lc_10 any_lc_99 any_gc_99 any_lc_10 ge_10 any_gc_10
ge_99 3 354545.903 -- -20.6% -30.6% -60.8% -61.7% -63.5% -100.0% -100.0%
lc_99 4 281678.295 25.9% -- -12.6% -50.6% -51.8% -54.1% -100.0% -100.0%
lc_10 4 246073.484 44.1% 14.5% -- -43.5% -44.8% -47.4% -100.0% -100.0%
any_lc_99 7 139067.292 154.9% 102.5% 76.9% -- -2.4% -7.0% -100.0% -100.0%
any_gc_99 7 135748.100 161.2% 107.5% 81.3% 2.4% -- -4.7% -100.0% -100.0%
any_lc_10 8 129331.803 174.1% 117.8% 90.3% 7.5% 5.0% -- -100.0% -100.0%
ge_10 175,494 5.698 6221964.0% 4943182.0% 4318339.3% 2440446.0% 2382196.2% 2269594.1% -- -38.5%
any_gc_10 285,327 3.505 10116044.9% 8036936.7% 7021036.1% 3967862.6% 3873157.1% 3690083.0% 62.6% --
正如您所看到的——这取决于情况并且是一种权衡……
解决方案 3：
与普遍的看法相反，列表推导对于中等范围来说相当不错。迭代器协议意味着调用iterator.__next__()，而 Python 中的函数调用 - 说实话 - 非常昂贵。
当然，在某些时候，生成器的内存/CPU 权衡将开始产生效果，但对于小集合来说，列表推导非常有效。
相关推荐
热门文章
项目管理软件有哪些？
热门标签
云禅道AD
