Python递归生成器性能

问题内容：

在python中，当将纯递归函数更改为递归生成器（而不是普通生成器）时，性能似乎会下降。

例如，这是找到列表的所有组合的两个函数之间的性能比较：

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 一样快，但事实并非如此，它要慢得多。

这是正常现象还是我缺少了什么？

问题答案：

rec_subsets()依然较快（为range(20)），即使result.append(s)添加的就地# do something with s和两者的结果gen_subsets()和rec_subsets()消耗。

PEP 380yield 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。

Python递归生成器性能

微信关注