Python のジェネレータ (4) - 無限リスト

Python のジェネレータ (3) - 数字にコンマを振る のつづき

1. 有限リストに対して有限の繰り返し

「有限のリストを走査する」ためのジェネレータは、次のように書く。関数 g は、引数としてリスト L を受け取るとする。

def g(L):
    for e in L:
        yield e

関数の中で yield が使われているので、ジェネレータが返される。これをジェネレータ関数と呼ぶ。

 

2. 無限リストに対して無限の繰り返し

関数 g の中では、与えられたリストを走査するために、for ループを利用した。 for ループの代わりに

while True

を用いて、延々と回る無限ループに置き換えると、「無限リストを対象としたイテレータを生成する」ジェネレータとなる。

例えば、

「 3 の倍数の無限リスト」

が欲しい場合、次のように書くことができる。

def m3():
    i = 0
    while True:
        i += 3
        yield i

Python では、無限リストを表現する特別な記述方法はない。その代わり、「３の倍数」を延々と計算するループを利用する。関数の中で return ではなく、yield を用いることにより、１回のループごとに呼び出し元に制御が戻る。これにより、ループが最後まで終了するのを待たずに済む。

上記のジェネレータを for 文に渡した場合、ループが止まらない。ジェネレータに対する next() の呼出し回数を指定することにより、無限ループに陥らないようにする必要がある。

例えば、「 3 の倍数の無限リスト」の先頭から 10 個要素が欲しい場合は、

g = m3()
for i in range(0,10):
    print g.next()

結果は、

3
6
9
12
15
18
21
24
27
30

 

無限リストを有限のリストと重ね合わせる

リスト内包表記を用いると、

g = m3()
print [g.next() for x in range(0,10)]

リスト内包表記で生成するのは有限のリストで、これを無限のリストと重ね合わせる。

結果は、上記と同じ要素がリストとして返ってくる。

[3, 6, 9, 12, 15, 18, 21, 24, 27, 30]

zip 関数を使うなら、

print [b for (a,b) in zip(range(0,10), m3())]

• cf. Python の zip と map の違い

 

3. ジェネレータをクラスから類推する

ジェネレータは、動作のイメージがつかみにくい。(+_+) しかし、クロージャを理解したときと同じ要領で、関数をクラスに見立てると理解しやすい。

例えば、上記の関数 m3 の場合で考える。

1. 関数名 m3 をクラス名と見立てる。
2. 変数 i は、インスタンス変数に相当する。
3. while ループは、next() によって呼出されるメソッド。呼出される度に、インスタンス変数を更新する

と見なすことができる。

 

n の倍数に一般化

上記の関数 m3 を、

「n の倍数を返すジェネレータ」

に変更する。

def m(n):
    i = 0
    while True:
        i += n
        yield i

先ほどと同じく、ジェネレータ関数 m をクラスと見なすと、引数 n を読み取り専用のインスタンス変数と見ることがでできる。

 

4. 指定した要素数を取得する関数

次に、無限リストを生成するジェネレータから、

指定した要素を取得する関数

を作ってみる。 Haskell であれば take 関数に相当する。

 

有限リストを対象にする場合

まずは、対象を有限リストで考えてみる。指定した要素の数だけリストから取得するには、

def takeL(n,L):
    result = []
    for i in range(0,n):
        result.append(L[i])
    return result

print takeL(3, [1,2,3,4,5])

リスト内包表記を使うなら、

def takeL2(n,L):
    return [L[x] for x in range(0,n)]

print takeL2(3, [1,2,3,4,5])

リスト内包表記は、必要とする分だけ要素を重ね合わせて取得するための手段として用いた。

 

ジェネレータを渡して無限リストを対象にする

有限リストの代わりに、「無限リストを生成するジェネレータ」を渡すなら、

def take(n,g):
    result = []
    for i in range(0,n):
        result.append(g.next())
    return result

print take(10, m(3))

ただし、関数 m は先に定義した「n の倍数を返すジェネレータ」を指す。

 

ジェネレータを渡し、ジェネレータが返される場合

次に、「無限リストを生成するジェネレータ」を渡したら、「有限リストを走査するためのジェネレータ」が生成される関数を定義してみる。

def gtake(n,g):
    for i in xrange(0,n):
        yield g.next()

print list(gtake(10, m(3)))
print [x for x in gtake(10, m(3))]

この関数の動作イメージは、次のように理解すれば良い。 例えば、

gtake(5, m(3))

の場合で考える。関数の呼び出しを見ると、無限リストから 5 つ要素を取得する形をとっている。しかし、実際には無限リストを生成するジェネレータから、要素を順に計算した結果を得ている。

比喩的に言えば、gtake のジェネレータにより生成されたイテレータが動くと、それに伴なって m のジェネレータが生成したイテレータも呼応するように動く。

take 関数は、実行すると、要素がリストとして返された。もし、take するリストが巨大であれば、要素数に応じたメモリが必要となる。それに対して、gtake 関数は、ジェネレータが返されるので、走査するためのメモリがあればよい。

極端な例で言えば、

「3 の倍数を 1000万個」 take 関数によって取得し、その後、10 で割り切れる数を 1 つだけ必要である

とする。 take 関数の場合、

for e in take(10000000, m(3)):
    if e % 10 == 0:
        print e
        break

「1000 万個の 3 の倍数のリスト」が生成されてから、その要素に対して 10 で割りきれるか確認することになる。

これに対して gtake 関数では、

for e in gtake(10000000, m(3)):
    if e % 10 == 0:
        print e
        break

実際には、「1000 万個の 3 の倍数のリスト」は生成されず、「 3 ~ 30 までの 3 の倍数」だけを確認して終了する。上記のコードにおいて break がなければ 1000 万個の 3 の倍数の要素を走査することになる。要素の末尾に到達せずに処理が終了するほど、gtake 関数の動作は有利となる。もし、末尾まで走査したとしても、メモリの使用量は take 関数よりも少ない。

 

5. Haskell の場合

Python で書いたコードを、Haskell で置き換えてみる。

m3 n = n : (m3 $ n+3)
-- 3 の倍数の無限リスト
m3' = m3 3

m x n = n : (m x $ n+x)
-- n の倍数の無限リスト
m' n = m n n

main = putStrLn $ show $ take 10 $ m' 3

遅延評価により、必要なときに必要なだけ処理されるので、無限リストを自然に扱える。

Python のジェネレータ (5) 再帰とジェネレータと Composite につづく…