python - 在递归中使用 yield 平衡内存和性能

Question

我有一个产生排列的函数:

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]

据我所知，yield 会即时计算结果，而不是将中间计算存储在堆上。这很好，因为 python 是 not aggressive at freeing up memory .但是it takes longer to calculate .这是否意味着每次调用它实际上都必须计算递归树的整个分支？如果是这样，运行时间的时间复杂度将增加 N*log(N)，对吗？

如果确实yield每次都需要计算整个一个分支，在每一层上，计算都需要按照 child 的数量按比例重复，每一层加起来都是N。由于深度为 log(N)，因此总数为 N*log(N)。这似乎是一笔太大的交易。何时使用 yield 或更好的替代方法是否有好的经验法则？

Answer 1

如果您检查 documentation ，您会看到 yield 卡住了生成器的状态。当控制流返回时，就好像它是一个外部调用，所以所有的状态都被保留。

因此，由于运行时复杂度没有差异，我不会太担心列表和生成器之间的性能差异。生成器的内存节省方面值得考虑，如果你经历大集合，以及创建“无限”集合的能力。

此外，itertools.permutations。