読者です 読者をやめる 読者になる 読者になる

ジェネレータで遊ぶ(python)

 

pythonにはジェネレータという組み込み型が存在し、値を逐次に計算する配列として使うことができます。ジェネレータを使って遊んだので書きます。

参考文献

structure and interpretation of computer programsの3.5節を参考にしました。

無限ジェネレーターに関するユーティリティ関数

この文章では無限に値を返すジェネレーターを扱うので、最初に便利な関数を定義しておきます。

# gの最初のn項を表示する
def g_print(g, n=10):
    for i in range(n):
        print(next(g))

# gをn項飛ばす
def g_delayed(g, n):
    for _ in range(n):
        next(g)
    return g

# gの第n項を表示する
def g_ref(g, n):
    return next(g_delayed(g, n))

無限ジェネレータ

pythonではジェネレータを使って無限に値を返し続けるものを書けます。

# 自然数を0から返す
def integers():
    i = 0
    while True:
        yield i
        i += 1
>>> g_print(integers())
0
1
2
3
4
5
6
7
8
9

同様に少し凝ったものも書けます。

# 5の倍数でない自然数を小さい順に返す
def no_five():
    i = 0
    while True:
        if i % 5 != 0:
            yield i
        i += 1
>>> g_print(no_five())
1
2
3
4
6
7
8
9
11
12

このno_fiveではローカル変数iを1づつ増やすことで全ての自然数をチェックしています。

no_fiveで行っている「ローカル変数に無限に自然数を代入して何かする」ということはまさにintegersがfor文で使われたときに行うことなので、次のように書くことができます。

def no_five():
    for i in integers() # while文の代わりにfor文とintegersを使った
        if i % 5 != 0:
            yield i

integersからno_fiveが作られる関係は、高階関数を使ってまとめることができます。

# ジェネレータg(無限でも良い)からcondを満たすものだけを抜き取る
def g_filter(g, cond):
    for i in g:
        if cond(i): # "i % 5 != 0" をcondに一般化した
            yield i

no_five = g_filter(integers(), lambda x: x % 5 != 0)

なおpythonの組み込み関数にfilterがありますが、無限ジェネレータに対しては上手く動きません。要素をすべて読みに行ってしまうようです。

g_filterと同様に、ジェネレータに対する高階関数を定義できます。

# gの全要素にfを適用する
def g_map(g, f):
    for i in g:
        yield f(i)

# gの要素とhの要素を足す
def g_add(g, h):
    for a, b in zip(g, h):
        yield a + b

# gの要素とhの要素をかける
def g_mul(g, h):
    for a, b in zip(g, h):
        yield a * b

# gの要素の累積和
def g_sum(g):
    sum = 0
    for i in g:
        sum += i
        yield sum

これらを使って様々なジェネレータを定義できます。

# 偶数全部
evens = g_map(integers(), lambda x: 2*x)

# 7で割ると3余る偶数全部
Nseven_plus_three = g_filter(evens, lambda x: x % 7 == 3)

# 7で割ると3余る偶数に自然数を足したもの
Nseven_plus_three_plus_N = g_add(Nseven_plus_three, integers())

再帰ジェネレータ

ジェネレータは関数の一種なので、再帰的に定義することができます。

def ones():
    yield 1
    yield from ones() # 次の要素は自分自身から取る

定義が言っているのは「onesは最初1を返し、それ以降はonesが返すものを最初から返す」ということです。つまり、1を無限に返します。

>>> g_print(ones())
1
1
1
1
1
1
1
1
1
1

ただしこの例では、onesはyieldするたびに新しくonesを作成するので、onesはメモリーを無限に食います。そのためこのonesは実用的ではありません。

もう少し面白い例がこれです。

def fib():
    yield 1
    yield 1
    yield from g_add(g_delayed(fib(), 1), fib())

fibの定義を解釈すると、

  1. fibの最初は1
  2. その次は1
  3. その次以降は「fibと、fibを一つずらしたジェネレータの和」というジェネレータの返す値を返す

3.が言っているのは\(x_n = x_{n-1} + x_{n-2}\)ということなので、fibはフィボナッチ数列を表します。

>>> g_print(fib())
1
1
2
3
5
8
13
21
34
55

メモ化していないので低速ですが、ifを使わないフィボナッチ数列の定義というのは珍しいと思います。

再帰的に定義されたジェネレータの例をいくつかあげます。他では見ないような形で再帰が使われているので面白いです。

# 1, 2, 3, 4, 5, ...
def integers():
    yield 1
    yield from g_add(ones(), integers())

# 1, 2, 4, 8, 16, ...
def two_powered():
    yield 1
    yield from g_add(s(), s())

# 1, 2, 6, 24, 120, 720, ...
def fact():
    yield 1
    yield from g_mul(g_delayed(integers(), 2), fact())

感想

本当はこのあと再帰ジェネレータをメモ化して速くして終わる予定だったんだけどメモ化ができなかったのでここで終わる。こういう細かいところはpythonじゃ無理だ。