5

我正在玩一些聪明的方法来为序列A003602创建一个 python 生成器

这似乎有效，但我不知道为什么。在我看来，它应该达到无限递归。python 是否在我不认识的地方进行了一些惰性评估？

def N():
    i=1
    while True:
        yield i
        i+=1

def interleave(a,b):
    def result():
        x=a()
        y=b()
        while True:
            yield next(x)
            yield next(y)
    return result

def RZ():
    return interleave(N,RZ)()

gen=RZ()

对我来说，似乎因为 RZ 立即调用 interleave 返回的方法，而后者又调用了 RZ 的 b（在第一次调用 yield 之前），这应该是无限递归。但这实际上似乎有效。谁能解释为什么？

4

3 回答 3

4

生成器（任何带有yield语句的函数）都是惰性的。这意味着result()在您向它请求第一个值之前不会开始处理，而您不会这样做。

这里的根本原因是您从x一开始就要求一个值。这意味着生成器永远不会询问它的子生成器，直到至少要求第二个值。考虑一个更简单的例子：

def test():
    yield 1
    a = test()
    while True:
        yield next(a)

a = test()
for i in range(10):
    print(next(a))

这和你的一样有效。它有无限递归的潜力，但如果你要求那么多值，它只会走得那么远。您所要做的就是删除yield 1以获得预期的行为。在您的情况下，只需切换N并RZ询问下一个值 - 您将获得预期的递归。

于 2012-06-17T01:32:36.283 回答
4

其他答案已经解释了为什么没有立即无限递归问题（因为生成器被懒惰地解释）。但是，我认为考虑何时可能达到 Python 解释器中存在的递归有限限制也很有趣。

首先，我注意到您的代码可以简化一点（您的功能比实际需要的要多，并且您的N生成器与 相同itertools.count(1)）。所以这里有一个更简单的生成器版本：

from itertools import count

def RZ():
    x=count(1)
    y=RZ()
    while True:
        yield next(x)
        yield next(y)

样本输出：

>>> gen = RZ()
>>> for i in range(1, 21):
    print i, next(gen)


1 1
2 1
3 2
4 1
5 3
6 2
7 4
8 1
9 5
10 3
11 6
12 2
13 7
14 4
15 8
16 1
17 9
18 5
19 10
20 3

接下来，我编写了一个函数，用于内省嵌套生成器并计算它们被评估的深度。我不确定这段代码是否可以在 python 版本之间移植（我使用的是 2.7）：

def getDepth(gen):
    depth = 0
    while gen:
        depth += 1
        gen = gen.gi_frame.f_locals.get("y")
    return depth

输出（索引，深度，值）：

>>> for i in range(1, 21):
    print i, getDepth(gen), next(gen)

1 1 1
2 2 1
3 3 2
4 3 1
5 4 3
6 4 2
7 4 4
8 4 1
9 5 5
10 5 3
11 5 6
12 5 2
13 5 7
14 5 4
15 5 8
16 5 1
17 6 9
18 6 5
19 6 10
20 6 3

这些深度值呈对数增长。具体来说，产生序列的第 N 个值所需的嵌套生成器的深度是ceil(log(N, 2)) + 1。

在我的 Python 副本中，允许递归（默认情况下）达到 100 级深度。只有在生产了 2^99 + 1 (=633,825,300,114,114,700,748,351,602,689) 个项目后，生成器才会达到该限制。我不会屏住呼吸等待的。

于 2012-06-17T04:26:32.570 回答
1

To me it seems like since RZ instantly calls the method returned by interleave which in turn calls b which is RZ (before the first call to yield),调用包含的函数yield返回一个迭代器对象，直到你开始迭代它才会被评估，因为 RZ 也返回一个迭代器，因为它调用具有 yield 的结果，因此它最初返回一个迭代器，即 RZ 返回一个迭代器.

yield next(x)将调用yield i并停止，再次调用迭代器yield next(y)将调用x = a(); y = b(); while True: yield next(x)并停止，依此类推，它似乎在不断地创建生成器，虽然不是很快，这可能好也可能不好......

count = 0
def N():
    i=1
    global count
    count += 1
    while True:
        yield i
        i+=1

def interleave(a,b):
    def result():
        global count
        count += 1
        x=a()
        y=b()
        while True:
            yield next(x)
            yield next(y)
    return result

def RZ():
    return interleave(N,RZ)()

gen = RZ() # 1) call RZ

gen = RZ()
r = [next(gen) for index in xrange(100)]
print count

它生成了 14 个迭代器对象，经过 100 次迭代，1000 次后 20 个，10000 次后 28 个，100000 次后 34 个，所以很慢......

于 2012-06-17T01:57:16.070 回答