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）都将根据之前找到的所有素数（so2、3、5和7）进行测试，直到找到下一个素数，即11。然后将11添加到过滤器的“列表”中，依此类推

这部分{}是一个{a3}

我的问题涉及Python用来“嵌套”这些生成器表达式的机制。例如，让我们在表达式中使用两个可能的过程：

第一次检查时，我们使用nats（对于自然数）并向其添加2过滤器

第二次，我们将已经“通过”nats和2过滤器的生成器添加到3过滤器中。我们从[3,2,nats]中产生，从[2,nats]中产生，从[nats]中产生。要点是，显然，每个层过程都需要保留一些变量上下文，例如，每个层“看到”不同的n

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

1. 是否为每个嵌套的生成器调用添加堆栈帧
2. 它是否只需要创建一个闭包对象
3. 也许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)调用使用了

…因此它继续存在

实际限制

正如你所能想象的，这是非常消耗内存的。在每次递归调用时，调用堆栈的使用率都会增加，迭代器的嵌套构造中的每个迭代器都是s的一个执行上下文中的变量sieve，并且必须执行其任务

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

Answer 2

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

Answer 3

如你所见in this visual demonstration of your code

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

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