Python

Pythonのジェネレーターってなんのためにあるのかをなるべく分かりやすく説明しようと試みた

はじめに

Pythonのジェネレーターについて説明してあるページは他にもありますが、英語だったり、あまり自分としてしっくりこないものが多かったので、自分の中で考えを整理することも兼ねて、ジェネレーターについて自分なりに説明しようと思います。
断っておくと、筆者は基本的ににわかなので、誤ったことを口走るかもしれません。間違い等がありましたらコメントしていただけると自分の勉強にもなるので大変助かります。
あと、ここで紹介するジェネレーターの利用法はあくまでも利用法の数例で、決して他に利用法がないというわけではありません。

ジェネレーターとは?

詳しい、正確な説明は他にも素晴らしい記事があるので、そちらをご参照ください:
Pythonのイテレータとジェネレータ

簡潔に説明すると、「通常の関数の、return文をyieldに置き換えたもの」ととりあえずは思ってください。(色々と違いますが、とりあえず見逃してください)。
returnの代わりにyieldと書くと、呼び出しただけでは値を返さなくなります
その代わり、for文などで呼び出して、順々に値を返すようになります。多分例を示したほうがわかりやすいと思います。

example.py
def count_up():
    x = 0
    while True:
        yield x
        x += 1

確かに、returnではなく、yieldになっていますね。そしてyieldの後に何か処理がきています。return文の後に処理がくることはないので、通常の関数のreturnを単純に置き換えたものとは何か違うことが早速わかります。それはおいおい説明します。とりあえず、このgeneratorは例えば以下のように呼び出します:

>>> countup()
<generator object countup at 0x101fa0468>
>>> for i in countup():
...     print(i)
...     if i == 5:
...             break
0
1
2
3
4
5

確かに、呼び出しただけでは何も値が帰ってきていないようです。代わりに、for文の中で呼び出すと、順々に値を返してきています。この時何が行われているかというと、count_upは呼ばれるたびにxの値を返しているのですが、呼び出されるたびにxの値をincrementしています。これがyieldの後に来ている処理の正体です。
なんとなくジェネレーターが何かはこれでわかったと思います(よくわからなくてもこれからもいくつか例を紹介するので心配しないでください)。
しかし、ここで皆さんがおそらく思っているのは、
    これってどこで使うの?
ということだと思います。
というわけで、今回はジェネレーターの用途を自分なりに説明していこうと思います。

ジェネレーターと関数の違い

先ほどの例でなんとなくわかったと思いますが、ジェネレーターと関数は全く違います
ジェネレーターは関数よりも、圧倒的にクラスに近いものです。例えば、先ほどの例の

>>> countup()

は、クラスのインスタンスを生成していたと解釈するとスッキリ理解できます。なので、以下のようなコードも通用します:

>>> y = countup()
>>> for i in y:
...     print(i)
...     if i == 5:
...             break
0
1
2
3
4
5

試しに、この後に以下のような処理を走らせると、

>>> for i in y:
...     print(i)
...     if i == 10:
...             break
6
7
8
9
10

0から5が消えました!その理由は、ジェネレーターは呼び出されるたびに、行われた処理を記憶するからです。つまり、ステートをもつということです。これが関数との最大の違いです。上の例では、最初のfor文が終わった時点でyの中ではx=6となっていて、それがそのまま次のfor文まで続いているというわけです。

で、じゃあこれってなんで重要なの?ってところですが、例えば、みんな大好きフィボナッチ数列を計算する場面を考えて見ましょう。よく紹介される、再帰を用いる計算方法は以下の通りです:

fibonacci_recursive.py
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

nが小さければいいのですが、nが大きくなると、スタックが一杯になってエラーが吐かれます。それに対して、ジェネレーターを用いる場合、

fibonacci_generator.py
def fibonacci():
    a, b = 0, 1
    while 1:
        yield b
        a, b = b, a+b

このように、直前2つの数列の値をステートとして保持することで、スタックを無駄に消費せずにフィボナッチ数列が計算できるようになります。

ジェネレーターとListの違い

ここまでの例を見ただけでは、おそらく読者が思うのは、
Listでよくないか?
ということだと思います。確かに、0からプリントするだけなら、別にリストでもいいです。
じゃあいつならリストではダメなのがいつか、といえば、リスト全体をメモリ内に保持するのが難しい、かつ不要なときです。
例えば、同じくフィボナッチ数列のN番目の要素をリストを用いて計算する例を考えて見ます:

fibonacci_list.py
f = [0, 1]
n = 2
while n < N:
    f.append(f[n-1] + f[n-2])
    n += 1

もしN番目の値を得たいだけなら、N-3番目以前のフィボナッチ数列の値はメモリの無駄です。
つまり、ジェネレーターが活躍する場面は、順々に値を返し、ステートを持つ必要があるが、リスト全体を保持する必要がない場面です。出力シンボル付き有限状態オートマトンをイメージしてもらえばいいと思います。
逆に、別にステートを持たなくてもいい場合や、リストを保持しないといけない場面には向きません。前者の例は、入力された数に対してハッシュ関数を計算する場面、後者の例は、素数のリストを作成する場面なんかがあります。
以下では、もう少し実践的な例を見ていきます。

ジェネレーターの実践的な利用法

字句解析

ジェネレーターが実際に使われている場面として、pythonの字句解析用の標準ライブラリがあります:
http://docs.python.jp/2/library/tokenize.html
字句解析とは、プログラムをコンパイルするときによく行われる処理で、プログラムを1文字ずつ見ていき、プログラムの文字列を、重要なパーツ(トークンと言う)ごとに分割していく処理です。例えば、
def f(hoge, foo):
というのは、
def, f, (, hoge, foo, ), :
というトークン列におそらく分割されます。
defという文字列から関数定義だということがわかり、fが関数名、そのあとの「 ( 」から「 ) 」の間にある、コンマで区切られた変数が引数だとわかります。字句解析では、この情報もトークンに付け加えて、次の処理にトークン列を渡します(少し不正確かもしれませんが、詳しくはコンパイラについての資料かなんかを参照してください)。

ここで重要なのは、文字を1文字つず見て解析していくとき、例えば「 ( 」を見たか見ていないかによって、「 ) 」という文字を見たときの処理が変わってくるということです。つまり、ある程度のステートを持たないといけません。
でも、この関数定義が終わったら、この関数の情報なんてどうでもよくなるわけです。プログラム全体の情報を一々保存していたらメモリの無駄です。
したがって、字句解析は、ジェネレーターの活躍する格好の場面というわけです。

パイプライン

詳しくは以下のサイトで解説されています。
https://brett.is/writing/about/generator-pipelines-in-python/

簡単に説明すると、ジェネレーターによるパイプラインというのは、いくつかのジェネレーターを接続して処理を行っていくことです。工場でベルトコンベアー式に横から処理を行っていくことをイメージしてもらえればいいと思います。紹介されている例は、与えられた整数のリストの偶数要素を3倍にして、文字列に変換して返すパイプラインです。

pipeline.py
def even_filter(nums):
    for num in nums:
        if num % 2 == 0:
            yield num
def multiply_by_three(nums):
    for num in nums:
        yield num * 3
def convert_to_string(nums):
    for num in nums:
        yield 'The Number: %s' % num

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
pipeline = convert_to_string(multiply_by_three(even_filter(nums)))
for num in pipeline:
    print num

この例は、個々のジェネレーターは状態を持ちませんが、それでもジェネレーターを有効につかている例と言えます。リスト全体を保存する必要がないが、逐次的に処理を施していくことが必要がある場面だと言えます。
関数処理でいいじゃん、と思うかもしれませんが、例えば奇数の値を処理するのは、上の例ではただの無駄な計算になってしまうわけです。だからこそ、1つ1つの要素に順々に処理を適用できるジェネレーターが便利なのです。

再帰

以下のサイトに詳しい説明、例があります:
http://www.unixuser.org/~euske/doc/python/recursion-j.html

先ほどから説明している通り、ジェネレーターというのはリスト全体を保持せずに、順次処理ができることが大きな強みです。つまり、細分化し、繰り返し処理を通して解決できる問題と相性が良いわけです。
これは、再帰によって問題を解決する際の考え方と非常に近いことがわかると思います。フィボナッチ数列の例は、再帰をジェネレーターで置き換えた例でしたが、ジェネレータ自体を再帰的に使うことももちろんできます。関数でなくジェネレーターを使うメリットは、値を生成したらその場で値を破棄できる点です。
例えば、ジェネレーターを再帰的に使って木構造を走査するコードは以下のようになります:

tree.py
class Node:
    def __init__(self, data):
        self.data = data
    self.left = None
    self.right = None


def traverse(node):
    if node is not None:
        for x in traverse(node.left):
            yield x
        yield t.dat
        for x in traverse(node.right):
            yield x

ちなみに、python3.3系から新たに追加された、yield from文を使用すると、traverse関数はさらにスッキリかけて、

def traverse(node):
    if node is not None:
        yield from traverse(node.left):
        yield t.dat
        yield from traverse(node.right)

となります。

コルーチンの実現

以下のソースに詳しい説明があります:
http://masnun.com/2015/11/13/python-generators-coroutines-native-coroutines-and-async-await.html

コルーチンというのは、処理を一旦中断した後、途中から処理を再開できるサブルーチンです。
コルーチンでは、値を取り出すだけでなく、値を送りつけることもできます。例えば、以下の例を見てみます:

coroutine.py
def coro():
    hello = yield "Hello"
    yield hello


c = coro()
print(next(c))
print(c.send("World"))

ここでは、yieldが代入式の右辺に来ていわかります。そして、sendメソッドで"World"という文字列を送りつけています。ステートを持つジェネレーターの特徴を活かしていることがわかります。
コルーチンについて詳しく説明していると、これはこれでまた1つの記事になりそうなので、ここでは紹介にとどめておきます。気が向けばコルーチンについての記事も投稿するかもしれません。
なお、python3.5からはnativeのコルーチンが実装されましたので、ジェネレーターを使わなくても一応同様の処理が実現できます。

まとめ

ジェネレーターはなんとも掴みづらい概念ですが、ステートを持ち、リスト全体を保持せずに、部分的な処置だけで順番に値を返していくツールと考えれば意外とシンプルに理解できるものだと思います。皆さんも是非ジェネレーターを使いこなしてかっこいいプログラムを書きましょう!(私は未だに使いこなせていませんが)。