3

ラムダでそれを歩くよりも、リストで反復子をラップして長さを取得する方が効率的であることを示す、非常に驚​​くべき結果が得られています。これはどのように可能ですか？直観的には、これらすべてのリストを割り当てると遅くなることが示唆されます。

そしてはい - イテレータは無限になる可能性があるため、常にこれを実行できるとは限りません。:)

from itertools import groupby
from timeit import Timer

data = "abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac" 

def rle_walk(gen):
    ilen = lambda gen : sum(1 for x in gen)
    return [(ch, ilen(ich)) for ch,ich in groupby(data)]

def rle_list(data):
    return [(k, len(list(g))) for k,g in groupby(data)]

# randomy data
t = Timer('rle_walk("abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac")', "from __main__ import rle_walk; gc.enable()")
print t.timeit(1000)

t = Timer('rle_list("abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac")', "from __main__ import rle_list; gc.enable()")
print t.timeit(1000)

# chunky blocks
t = Timer('rle_walk("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc")', "from __main__ import rle_walk; gc.enable()")
print t.timeit(1000)

t = Timer('rle_list("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc")', "from __main__ import rle_list; gc.enable()")
print t.timeit(1000)

1.42423391342
0.145968914032
1.41816806793
0.0165541172028
4

3 に答える 3

6

残念ながらrle_walk、バグがあります。parameter を取りますgenが、 parameter を取る必要があるdataため、間違った入力で動作しています。また、インラインrle_walkで動作するラムダを使用するのは不公平です。rle_list次のように書き換えます。

def rle_walk(data):
    return [(k, sum(1 for _ in g)) for k, g in groupby(data)]

def rle_list(data):
    return [(k, len(list(g))) for k, g in groupby(data)]

およびテスト:

data_block = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc"
data_random = "abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac"
print [[Timer('r("{data}")'.format(data=data),
              "from __main__ import {r} as r; gc.enable()".format(r=r)).timeit(1000)
        for r in ['rle_walk', 'rle_list']]
        for data in (data_block, data_random)]

与える

[[0.02709507942199707, 0.022060155868530273],
 [0.12022995948791504, 0.16360306739807129]]

そのため、ブロック状のデータwalkよりもわずかに遅くなりますlistが、ランダム データではわずかに高速です。その理由は、(Python の) ジェネレーターがリスト コンストラクターと比較してオーバーヘッドを課すためだと思います。また、30 項目のリストのメモリ オーバーヘッドは小さすぎて、重大なペナルティを課すことはできません。

関数を逆アセンブルすると、少し洞察が得られます。

>>> dis.dis(lambda g: (1 for _ in g))
  1           0 LOAD_CONST               0 (<code object <genexpr> at 0x2b9202a6fe40, file "<stdin>", line 1>)
              3 MAKE_FUNCTION            0
              6 LOAD_FAST                0 (g)
              9 GET_ITER            
             10 CALL_FUNCTION            1
             13 RETURN_VALUE        
>>> dis.dis((lambda g: (1 for _ in g)).func_code.co_consts[0])
  1           0 SETUP_LOOP              18 (to 21)
              3 LOAD_FAST                0 (.0)
        >>    6 FOR_ITER                11 (to 20)
              9 STORE_FAST               1 (_)
             12 LOAD_CONST               0 (1)
             15 YIELD_VALUE         
             16 POP_TOP             
             17 JUMP_ABSOLUTE            6
        >>   20 POP_BLOCK           
        >>   21 LOAD_CONST               1 (None)
             24 RETURN_VALUE        
>>> dis.dis(lambda g: len(list(g)))
  1           0 LOAD_GLOBAL              0 (len)
              3 LOAD_GLOBAL              1 (list)
              6 LOAD_FAST                0 (g)
              9 CALL_FUNCTION            1
             12 CALL_FUNCTION            1
             15 RETURN_VALUE

ジェネレーターフォームのコード量がはるかに多いため、ある程度の効果があります。リスト形式には、使い捨てリストを構築するための O(log n) 係数がありますが、さまざまな反復子をループする際に k*O(n) 係数によって支配されます。ここから取り除かなければならないことの 1 つは、少なくともシングルスレッド環境 (CPython は GIL の必要性による) での小さな (サブページ) 割り当ての場合、メモリ割り当てが高速であることです。

于 2012-07-06T09:50:09.490 に答える
2

Python の関数呼び出しのオーバーヘッドは (ほとんどの動的言語と同様) 非常に高くなります。

Python Performance Tipsから:

特に組み込み関数の実行速度と比較すると、Python の関数呼び出しのオーバーヘッドは比較的高くなります。これは、必要に応じて、関数がデータ集計を処理する必要があることを強く示唆しています。

イテレータ バージョンでは、 への関数呼び出しがilen()あり、Python 反復を使用して 1 のリストを作成します。

リスト バージョンでは、ビルトインへの 2 つの呼び出しlist()とlen(). ビルトインは、高度に最適化された C からコンパイルされたネイティブ コードとして実行されます。最も重要なことlist()は、ビルトインを使用して反復子をリストに変換するための反復が、このネイティブ コードを使用して内部的に行われることです。

于 2012-07-06T09:49:39.863 に答える
2

と書き直すrle_walkと

def rle_walk(gen):
    return [(ch, sum(1 for _ in ich)) for ch, ich in groupby(gen)]

リストベースのバージョンよりも高速です。

タイミング (IPython を使用):

>>> def rle_walk(gen):
...     ilen = lambda gen : sum(1 for x in gen)
...     return [(ch, ilen(ich)) for ch,ich in groupby(gen)]
... 
>>> %timeit rle_walk(data)
10000 loops, best of 3: 94.3 us per loop
>>> def ilen(x): return sum(1 for _ in x)
... 
>>> def rle_walk(gen):
...     return [(ch, ilen(ich)) for ch,ich in groupby(gen)]
... 
>>> %timeit rle_walk(data)
10000 loops, best of 3: 93.4 us per loop
>>> def rle_walk(gen):
...     return [(ch, sum(1 for _ in ich)) for ch,ich in groupby(gen)]
... 
>>> %timeit rle_walk(data)
10000 loops, best of 3: 83.8 us per loop
>>> def rle_list(data):
...     return [(k, len(list(g))) for k,g in groupby(data)]
... 
>>> %timeit rle_list(data)
10000 loops, best of 3: 123 us per loop

( to indataの代わりにフィードしていたことに注意してください。)gengroupbyrle_walk

于 2012-07-06T09:46:39.793 に答える