Python递归生成器的性能表现

Question

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

这是正常的吗？还是我漏掉了什么？

- Rabih Kodeih

---

在进行有意义的计时之前，您需要在＃ do something with s位置放置一些代码。 - Janne Karila

不需要，gen_subsets同样什么也没做。我在两种情况下都做了类似的事情，以防万一（将其添加到一个空的全局列表中），并获得了相同的结果。 - Rabih Kodeih

但是为什么您会期望添加yield语句会使代码更快呢？ - Janne Karila

这就是我发问的初衷，想知道这是否是一个有效/合理的假设。相较于纯递归，递归生成器更加优秀和多才多艺。如果它们的性能也很好的话，那就再好不过了。 - Rabih Kodeih

我认为这是由于生成器函数中的那些循环引起的。我认为这使得gen和rec变体不相等。 - Gill Bates

Answer 1

即使在将 # do something with s 替换为 result.append(s) 并消耗了 gen_subsets() 和 rec_subsets() 的结果的情况下，对于 range(20)，rec_subsets() 仍然更快。可能可以通过以下来解释来自 PEP 380 (yield from syntax support) 的引用：使用专门的语法在存在长链生成器的情况下打开优化的可能性。这种链可能会出现在递归遍历树结构时。通过链上传递 __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。

- jfs

---

我认为这里的教训是在生产代码中用非递归生成器替换递归函数。 - Rabih Kodeih