itertools.ifilter

Python

itertools.ifilterはジェネレータを受け取ってジェネレータを返すことが可能。


以下は上記のサイトでの素数を生成するサンプル。

>>> from itertools import ifilter, count
>>> def sieve():
...     g = count(2)
...     while True:
...         prime = g.next()
...         yield prime
...         g = ifilter(lambda x, prime=prime: x%prime, g)

上記のg = ifilter(lambda x, prime=prime: x%prime, g)の部分はすばらしいと思った。以下はwhile Trueのブロック部分が1ステップずつ実行されるイメージを実装したもの。

>>> from itertools import *
>>> from functools import *
>>>
>>> def foo(x, prime):
...     return x % prime
...
>>> def next_step(g):
...     prime = g.next()                  # 次の素数を取り出す
...     print 'prime =', prime
...     foo2 = partial(foo, prime=prime)
...     g1, g2 = tee(g)                   # オリジナルのジェネレータをg1に保存しておく
...     g2 = ifilter(foo2, g2)            # g2をifilterで絞ってg2に保存
...     g2, g3 = tee(g2)                  # g2をg3に保存しておく
...     for i in range(10):               # g1を10個分表示
...         print g1.next(),
...     print
...     for i in range(10):               # g2を10個分表示
...         print g2.next(),
...     return g3                         # 現在のジェネレータを返す
...
>>> g = count(2)
>>> g = next_step(g)
prime = 2
3 4 5 6 7 8 9 10 11 12        # オリジナル
3 5 7 9 11 13 15 17 19 21     # 2で割り切れるものが取り除かれている
>>> g = next_step(g)
prime = 3
5 7 9 11 13 15 17 19 21 23    # オリジナル
5 7 11 13 17 19 23 25 29 31   # 3で割り切れるものが取り除かれている
>>> g = next_step(g)
prime = 5
7 11 13 17 19 23 25 29 31 35  # オリジナル
7 11 13 17 19 23 29 31 37 41  # 5で割り切れるものが取り除かれている

ステップを重ねるごとにジェネレータから「素数で割り切れる数値」が取り除かれていることを確認できる。ifilterは無限のジェネレータを受け取り無限のジェネレータを返すことが可能というのが分かった。


上記のサイトで、この実装ではスタックオーバーフローしないと書いてあった。ifilterオブジェクトをステップごとにラップしているのに不思議である。理由としては、単にインスタンス変数として再帰的にifilterオブジェクトを持っているだけで関数呼び出しが再帰している訳ではないからだろうか？