Python 生成器表达式递归

Question

这是一个关于 Python 内部结构的问题。以下代码摘自this video about laziness in python:

def nats(n):
    yield n
    yield from nats(n + 1)


def sieve(s):
    n = next(s)
    yield n
    yield from sieve(i for i in s if i % n != 0)

s = sieve(nats(2))
print(next(s), next(s), next(s), next(s), next(s)) # Primes: 2, 3, 5, 7, 11...

sieve 函数延迟生成素数（原始概念请阅读 this）。从概念上讲，我们将过滤器添加到“筛子”中，因此每个数字（比如 10）都会针对所有先前找到的素数（因此 2、3、5 和 7）进行测试，直到找到下一个素数，即 11。11 是然后添加到过滤器的“列表”中，依此类推。

这部分 (i for i in s if i % n != 0) 是一个 generator expression (or "comprehension")。

我的问题与 Python 用于“嵌套”这些生成器表达式的机制有关。例如，让我们使用两个可能的表达式：

我们第一次通过它时，我们采用 nats（对于自然数）并向其添加 2 过滤器。

第二次，我们使用已经“通过”nats 和 2 过滤器 的生成器，并添加 3 过滤器 到它。我们从 [3,2,nats] 产生，从 [2,nats] 产生，从 [nats] 产生。关键是，很明显，每一层传递都需要保存一些变量的上下文，因为每一层都“看到”不同的 n 例如。

但是 Python 到底在做什么？以下是我认为可行的几个选项：

是否为每个嵌套生成器调用添加堆栈帧？
是否只需要创建一个闭包对象？
也许 python 将生成器“压缩”为一个类似于此表达式的生成器： i % 2 != 0 and i % 3 != 0 and i % 4 !=0?

或者我可能遗漏了一些关于这里发生的事情的基本信息？

Answer 1

clearly some preservation of a context of variables is necessary for each layer pass, as each layer "sees" a different n for example.

是的，这不是特定于生成器，而是特定于任何函数调用：如果该函数调用一个函数（可能是它自己），那么它的局部变量将保存在堆栈帧中，并且新的函数执行上下文获取它的自己的一组局部变量。

Is it adding a stack frame for each nested generator call?

是的。所以在sieve的情况下，sieve的每个执行上下文都有自己的n和s变量。

在 sieve 传递给递归调用的表达式中，它正在从它作为参数获得的现有迭代器创建一个新的、更具限制性的迭代器。我们可以倒推看看完整的迭代器是什么样子的。

第一次递归调用，可以展开为：

yield from sieve(i for i in 
                   (i for i in nat(3))   # this is roughly `s`
                 if i % 2 != 0)

我写 nat(3) 而不是 nat(2) 因为值 2 已经从那个迭代器中消耗了。

该递归调用将产生 3，并进行下一个递归调用：

yield from sieve(i for i in 
                   i for i in                 # }
                     (i for i in nat(3))      # } this is roughly `s` 
                   if i % 2 != 0 and i != 3)  # }
                 if i % 3 != 0)

我再次添加 and i != 3 因为 3 已经被单独的 next(s) 调用消耗掉了。

...如此继续。

实际限制

如您所想，这非常耗费内存。在每次递归调用时，调用堆栈的使用量都会增加，迭代器嵌套构造中的每个迭代器都是 sieve 执行上下文之一中的变量 s，并且必须完成其工作。

虽然从理论上看这看起来很优雅，但在实际实现中并不实用：在遇到“超出最大递归深度”类错误之前可以生成的素数数量会少得令人失望。当运行它在 repl.it 上时，在错误之前生成的最后一个素数是 3559.

Answer 2

如你所见in this visual demonstration of your code,

每 yield from 创建一个新的堆栈框架和一个新的生成器对象。

我认为 nats 可以很容易地重写为使用循环而不是递归。然而，sieve 可能更难优雅地重写保持这个想法。

Answer 3

FWIW，您可以通过删除递归并在生成器中使用循环来避免堆栈溢出。这将允许您生成更大的质数，但这不是免费的午餐。您仍然通过捕获所有生成器对象来消耗内存，您只是没有通过递归来完成它。它会逐渐变慢，最终运行资源不足：

def nats(n): 
    while True:
        yield n
        n += 1


def sieve(s):
    while True:
        n = next(s)
        yield n
        s = filter(lambda i, n=n: i % n != 0, s)


s = sieve(nats(2))

# generate the 3000th prime
for x in range(3000):
    n = next(s)

print(n)
# 27449

Python 生成器表达式递归

Python generator expression recursion

python

closures

generator-expression

sieve-of-eratosthenes

python-internals

实际限制