5

有时我发现自己在 Python 中编写递归生成器。这是一个最近的例子：

def comb(input, lst = [], lset = set()):
   if lst:
      yield lst
   for i, el in enumerate(input):
      if lset.isdisjoint(el):
         for out in comb(input[i+1:], lst + [el], lset | set(el)):
            yield out

for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
   print c

算法的细节并不重要。我把它作为一个完整的、真实的插图来给这个问题一些背景。

我的问题是关于以下构造：

   for out in comb(...):
      yield out

这里，comb()是生成器的递归实例化。

每次我必须拼出for: yield循环，它让我畏缩。这真的是在 Python 中编写递归生成器的方法，还是有更好的（更惯用的、更高性能的等）替代方案？

4

1 回答 1

8

每次我必须拼出 for:yield 循环时，都会让我畏缩。这真的是在 Python 中编写递归生成器的方法，还是有更好的（更惯用的、更高性能的等）替代方案？

有一个更好的选择：

yield from comb(...)

这实际上与以下内容相同：

for out in comb(...):
    yield out

这需要 Python 3.3。如果您坚持使用 Python 2.x（或更早的 3.x），则必须坚持使用旧方式，因为 Python 2 的语法在 2.7 之后将永远不会再次更新（并且 3.0 到 3.2 显然同样被冻结）。

首先，查看评论中提到的 Wessie的纯 Python 产量。此版本仅适用于单一级别的“yield from”，但底部有一个链接，指向更灵活和优化（但更难理解）的版本。它似乎并没有真正起作用（我得到了一个NameErroron _stack，但它看起来应该很容易修复。如果是这样，并且如果可以@supergenerator在最外面的生成器上放置一个装饰器，并且如果性能可以接受，那么你的回答。

如果没有，您可以采取各种技巧来在一个地方而不是在每个级别处理多个级别的产量循环。然而，它们都不会让你降到 0 级——而且实际上，它们很少值得去做。例如：

一旦你考虑序列而不是生成器函数，很明显我们要做的就是展平序列。无论您是要尝试展平 N 个级别，展平直到达到不可迭代，展平直到满足其他一些可预测的级别，等等，都有一个简单的算法；你只需要选择正确的。但它会让你的代码更惯用、更易读、更高效等吗？很少。让我们举一个超级简单的案例。

def flatten(seq, levels=1):
    for level in range(levels):
        seq = itertools.chain.from_iterable(seq)
    return seq

所以：

def a():
    yield 1
    yield 2
    yield 3
def b():
    yield a()
def c():
    yield b()
def d():
    yield c()

for i in flatten(d(), 3):
    print i

好处是我只需要在调用站点的一个地方处理嵌套，而不是在沿途的每个生成器的 3 个地方。代价是读者不太清楚发生了什么，而且更容易出错。（好吧，在这种情况下不是那么多......但想象一下扁平化直到lambda x: isinstance(list)，测试它的地狱，释放它，然后有人呼吁comb...... tuple）治愈比疾病更糟糕，这就是为什么我称之为把戏。

除非展平确实是算法的自然部分，或者中间的某些步骤是您不能或不想接触的代码，或者以这种方式构造事物是有用的说明或提醒某事，或者…</p>

只是为了好玩，我写了一个全唱全跳的 flatten-any-way-you-want 函数，并将它作为一个补丁提交给 Erik Rose 漂亮的more-itertools库。即使他不接受，你也可以在我的 fork中找到它——它被称为collapse，它是文件中的最后一个函数。

于 2012-11-26T23:51:20.113 回答