37

私はこの質問に答えていました。ここでジェネレーター式を好み、これを使用しました。ジェネレーターが最初にリスト全体を作成する必要がないため、これはより高速であると思いました。

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

そして、リーヴォンは彼の解決策でリスト内包表記を使用しました、

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

3 に答える 3

41

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)

ジェネレータ式を作成することは、ジェネレータ関数を作成して呼び出すことと同じです。これは、への1回の呼び出しに相当し<genexpr>ます。次に、最初のケースでnextは、に達するまで4回呼び出さdれ、合計5回の呼び出しが行われます（100000回の反復= ncalls = 500000）。2番目のケースでは、17回呼び出され、合計18回呼び出されます。3回目は24回、合計25回の呼び出しです。

Genexは、最初のケースではリスト内包を上回りnextますが、2番目と3番目のケースでは、リスト内包の速度とジェネレーター式の速度の違いの大部分を説明するための追加の呼び出しがあります。

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

ご覧のとおり、短絡が関係ない場合、リストの理解は、100万アイテムの長さのリストのリストでも一貫して高速になります。明らかに、これらのスケールでの実際の使用では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つあります。短絡を利用するためとメモリを節約するためです。非常に大きなシーケンス/反復可能オブジェクトの場合、ジェネレーターはメモリを節約するため、当然の方法です。しかし、短絡が選択肢にない場合は、速度のリストよりも発電機を選択することはほとんどありません。あなたはメモリを節約するためにそれらを選択しました、そしてそれは常にトレードオフです。

于 2012-08-15T05:21:44.110 に答える
14

完全にデータに依存します。

ジェネレーターのセットアップ時間は固定されており、呼び出されるアイテムの数に応じて償却する必要があります。リスト内包表記は最初は高速ですが、より大きなデータセットでより多くのメモリが使用されると大幅に遅くなります。

cPythonリストが展開されると、リストは4、8、16、25、35、46、58、72、88 、...の成長パターンでサイズ変更されることを思い出してください。リスト内包表記が大きい場合、Pythonはデータのサイズの最大4倍のメモリを割り当てる可能性があります。VMにアクセスしたら、本当にsloowww！ただし、前述のように、リスト内包表記は、小さなデータセットのジェネレーターよりも高速です。

ケース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%       --

ここで、LCとgenの間に大きな差異があるケース2について考えてみます。この場合、リストの種類の構造の100 x 97x97リストで1つの要素を探しています。

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

ご覧のとおり、状況によって異なり、トレードオフになります...

于 2012-08-15T04:54:37.453 に答える
11

一般に信じられていることとは反対に、リスト内包表記は中程度の範囲ではかなり問題ありません。イテレータプロトコルはの呼び出しを意味しiterator.__next__()、Pythonでの関数呼び出しは-言うまでもなく-不快なほど高価です。

もちろん、ある時点で、ジェネレーターのメモリーとCPUのトレードオフが支払われ始めますが、小さなセットの場合、リスト内包表記は非常に効率的です。

于 2012-08-15T04:33:05.367 に答える