0

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

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在释放内存方面并不积极。但计算时间较长。这是否意味着，每次调用它实际上都必须计算递归树的整个一个分支？如果是这种情况，运行时间的时间复杂度将增加 N*log(N)，对吗？

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

4

1 回答 1

1

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

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

另外，itertools.permutations.

于 2013-05-29T06:20:37.410 回答