3

Python では、純粋な再帰関数を再帰ジェネレーター (単純なジェネレーターではない) に変更すると、パフォーマンスが低下するようです。

たとえば、リストのすべての組み合わせを見つける 2 つの関数のパフォーマンス比較を次に示します。

from datetime import datetime as dt

def rec_subsets(ms, i=0, s=[]):
    if i == len(ms):
        # do something with s
        return
    rec_subsets(ms, i+1, s)
    rec_subsets(ms, i+1, s + [ms[i]])

def gen_subsets(ms, i=0, s=[]):
    if i == len(ms):
        yield s
        return
    for a in gen_subsets(ms, i+1, s): yield a
    for a in gen_subsets(ms, i+1, s + [ms[i]]): yield a

t1 = dt.now()
rec_subsets(range(20))
t2 = dt.now()
print t2 - t1

t1 = dt.now()
for _ in gen_subsets(range(20)): pass
t2 = dt.now()
print t2 - t1

次の出力で：

0:00:01.027000  # rec_subsets
0:00:02.860000  # gen_subsets

当然のことながら、gen_subsetsはrec_subsetsとほぼ同じ速度であると予想されますが、そうではなく、はるかに低速です。

これは正常ですか、それとも何か不足していますか?

4

1 に答える 1

4

rec_subsets()の代わりに が追加され、と の両方の結果が消費されたとしても、 ( のrange(20)場合)はさらに高速です。result.append(s)# do something with sgen_subsets()rec_subsets()

PEP 380 (yield from構文サポート)からの次の引用によって説明されるかもしれません:

特殊な構文を使用すると、ジェネレーターのチェーンが長い場合に最適化の可能性が開かれます。このようなチェーンは、たとえば、ツリー構造を再帰的にトラバースするときに発生する可能性があります。__next__()呼び出しと生成された値をチェーンの上下に渡すオーバーヘッドにより、最悪の場合、 O (n)操作がO(n**2)になる可能性があります。

次を使用してパワーセットを生成できますitertools.combinations()。

from itertools import combinations

def subsets_comb(lst):
    return (comb for r in range(len(lst)+1) for comb in combinations(lst, r))

range(20)私のマシンでは高速です：

name                    time ratio comment
subsets_comb        227 msec  1.00 [range(0, 20)]
subsets_ipowerset   476 msec  2.10 [range(0, 20)]
subsets_rec         957 msec  4.22 [range(0, 20)]
subsets_gen_pep380 2.34  sec 10.29 [range(0, 20)]
subsets_gen        2.63  sec 11.59 [range(0, 20)]

結果を再現するには、 を実行しtime-subsets.pyます。

于 2013-05-25T18:04:57.960 に答える