3

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

这是正常的还是我错过了什么？

4

1 回答 1

4

rec_subsets()仍然更快（对于range(20)），即使result.append(s)添加了# do something with s和 的结果并且两者的结果都gen_subsets()被rec_subsets()消耗了。

它可以通过PEP 380（yield from语法支持）的以下引用来解释：

当存在一长串生成器时，使用专门的语法为优化提供了可能性。例如，当递归遍历树结构时，可能会出现这种链。向下和向上传递__next__()调用和产生值的开销可能导致本应为O(n)的操作在最坏的情况下变为O(n**2)。

您可以使用以下方法生成 powerset 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 回答