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がインターリーブによって返されたメソッドを即座に呼び出し、次にRZであるbを呼び出すので（最初のyieldの呼び出しの前に）、これは無限再帰である必要があります。しかし、これは実際には機能しているようです。誰かが理由を説明できますか？

4

3 に答える 3

4

yieldジェネレーター（ステートメントを持つ関数）は怠惰です。これはresult()、最初の値を要求するまで処理を開始しないことを意味しますが、これは実行しません。

ここでの根本的な原因は、x最初から値を要求することです。これは、少なくとも2番目の値が要求されるまで、ジェネレーターが子ジェネレーターを要求することは決してないことを意味します。より簡単な例を考えてみましょう。

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

100回の反復後、1000回後に20回、10000回後に28回、100000回後に34回、14回の反復子オブジェクトを生成したため、非常に遅い...

于 2012-06-17T01:57:16.070 に答える