Python 生成器表达式递归

Question

这是一个关于Python内部的问题。 以下代码摘自这个关于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...

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

这部分

(i for i in s if i % n != 0)

是一个生成器表达式（或“理解”）。

我的问题与 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

显然，每个层都需要保存一些变量上下文，例如，每个层“看到”不同的

n

。

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

是否为每个嵌套生成器调用添加堆栈帧？

是的。因此，在

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

，并且必须完成其工作。

虽然从理论角度来看这看起来很优雅，但在实际实现中并不实用：在遇到“超出最大递归深度”类型的错误之前可以生成的素数数量将少得令人失望。

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

正如您所见在代码的可视化演示中，

每个

yield from

都会创建一个新的堆栈帧和一个新的生成器对象。

我认为

nats

可以很容易地重写为使用循环而不是递归。然而，

sieve

可能更难优雅地重写并保留这个想法。