列表理解vs生成器表達式的奇怪時間結果？

Question

我回答這個question，我在這裏首選發電機表達和用這個，我本以爲這是更快發電機並不需要首先創建一個完整的列表

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

而且捷爾使用列表中理解他solution，

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

但是，當我做了這些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 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) 

創建生成器表達式相當於creating a generator function and calling it。這佔了一個電話<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 

在這種情況下，列表理解爲一個數量級的速度更快！

當然，這隻有在內存不足時纔會保持正確。這使我想到了我的最後一點。使用發生器有兩個主要原因：利用短路並節省內存。對於非常大的序列/迭代序列，生成器是顯而易見的途徑，因爲它們節省了內存。但如果短路不是一個選項，你幾乎不會選擇發電機列表速度。你選擇它們來節省內存，而且它總是一種折衷。

Answer 2

與流行的觀點相反，列表解析對於中等範圍來說相當不錯。迭代器協議暗示了對iterator.next（）的調用，並且Python中的函數調用非常昂貴。

當然，在某些情況下，發生器內存/ CPU的折衷將開始支付，但對於小集列表，解析非常有效。

Answer 3

完全取決於數據。

發電機有一個固定的設置時間，必須在多少個項目被調用時攤銷;列表推導起初速度較快，但會隨着較大數據集使用更多內存而大幅減慢。

回想一下，隨着cPython列表的擴展，列表的大小將調整爲4, 8, 16, 25, 35, 46, 58, 72, 88,...的增長模式。對於更大的列表解析，Python可能會比您的數據大小多分配4倍的內存。一旦你打到虛擬機---真的很滑稽！但是，如前所述，列表解析比小型數據集的生成器更快。

考慮情況下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。

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) 

結果，在這些日子：在這種情況下，我們在列表這種結構的100×97 X 97名單找一個元素

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

正如你所看到的 - 它取決於，這是一個折衷...