Generator

はじめに

ここでは、Python におけるジェネレータについて述べます。 まず、ジェネレータという概念について簡単に説明し、ジェネレータを導入する利点について触れます。 続いて、ジェネレータの定義方法とその実装例を紹介しながら、ジェネレータの挙動について詳細に述べます。 また、ジェネレータ式や yield from 式、ジェネレータのパフォーマンス面における注意点などについても説明します。

ジェネレータとは何か

ジェネレータ (generator) という言葉を単独で使うとき、それが指す対象は実は二つあります: ジェネレータ関数とジェネレータイテレータです (後者はジェネレータオブジェクトとも呼ばれます)。

ジェネレータ関数は、ジェネレータイテレータを返す関数です。 ジェネレータイテレータ (generator iterator) は、その名の通りイテレータであるため、for 文による繰り返し処理などに使用することが可能です。 ジェネレータイテレータから得られる値は遅延評価されます、すなわち、その値を取得する際に計算されます。 その結果、値をすべてメモリ内に保持しておくよりも、メモリ効率が優れたプログラムを書くことが可能となります。

ジェネレータ関数は、関数内で return の代わりに yield を使用することで作成できます。 たとえば、

def f():
    i = 0
    while True:
        yield i
        i += 1

は、0 以上の整数列を計算するイテレータを返すジェネレータ関数です。 このジェネレータ関数を用いて for 文を実行すると、

>>> for i in f():
...     print(i)
...
0
1
2
<略>
770334
770335
770336
770337
^CTraceback (most recent call last):
  File "<stdin>", line 2, in <module>
KeyboardInterrupt

のように、無限に整数を取得することができます。 しかも、必要な値はその都度計算しているため、メモリを無限に必要とすることはありません。

モチベーション

ここではジェネレータが必要となる具体的な場面について考えましょう。

たとえば、1 から n 番目までのフィボナッチ数列の値を得たいとします。 ここで、素朴に次のような関数を定義するとどのような問題があるでしょうか:

def fibonacci(n):
    result = []
    a, b = 0, 1
    for i in range(n):
        result.append(a)
        a, b = b, a + b
    return result

関数 fibonacci は n 個の整数のリストを返します。 ここで、もし n がとても大きな数であれば、

という二つの問題が生じます。 これに対し、すべての値をあらかじめ生成するのではなく、ジェネレータにより各値を利用する都度計算することにすれば、サイズの制限を気にすることなくいくらでも大きな数列を得ることができます。 また、すべての値が生成されるまで待つ必要もありません。

あるいは、Python の標準ライブラリにある os.walk 関数のクローンを自分で実装することを想像してみましょう。 os.walk は、引数として与えられたパスを起点としたディレクトリツリーを生成します。 ここで、与えられたパス以下のファイル名をすべて列挙したリストを返すような関数として実装したとします。 論理的にはそれでも問題ないはずですが、このように実装すると、生成されるツリーの階層が深いような場合 (たとえば、ルートディレクトリへのパスを引数として与えた場合)、上の関数 fibonacci とまったく同じ問題が生じます。 こうした問題を回避するためには、ジェネレータを定義し、ディレクトリツリーの各ノードごとに情報を取得できるようにする必要があります (実際、標準ライブラリの os.walk はジェネレータを返します)。

以上、ジェネレータが有用、あるいは必要であるような場合について確認してきました。 以下では、ジェネレータを実際に定義する方法について述べていきます。

ジェネレータ関数の定義と挙動

ジェネレータ関数 (generator function) は、冒頭でも述べた通り、ジェネレータイテレータを返す関数です。 したがって、ジェネレータ関数を定義するためには、通常の関数と同様に def キーワードを用います。 通常の関数と異なるのは、yield 式を利用する点です。 もっとも単純なジェネレータ関数を定義すると、次のようになります:

def f():
    yield

f は実用上は無益ですが、立派にジェネレータとして振る舞います:

>>> f
<function f at 0x7f5710572af0>
>>> f()
<generator object f at 0x7f5710576890>
>>> for x in f():
...     print(x)
...
None

上の結果から、f は通常の関数であること、f() は generator object を返していることがわかります。 また、for ループにおいて f() を利用できることから、ジェネレータイテレータである f() は、文字通りイテレータとして振る舞うということも確認できます。

yield 式は、呼び出しもとに値を返すという機能に加え、実行時の情報を記憶する役割をもちます。 これを for ループにおけるジェネレータイテレータの挙動とともに説明すると、次のようになります。

まず、for ループによりジェネレータイテレータの __next__ メソッドが呼び出されると、対応するジェネレータ関数の実行が開始されます。 処理が yield 式まで到達すると、呼び出しもとに yield に与えられた値が返されます。 これが return 式と異なるのは、上で述べたように、ローカル変数の状態や実行箇所へのポインタなど、yield 実行時の情報が保存された上で、いわば関数の実行を「停止」するという点です。 これにより、このあと再度 __next__ メソッドが呼び出されると、停止前の情報を復元した上で、関数の実行が再開されます。 なお、yield 式に到達せずに関数を抜けると、StopIteration 例外が送出され、for ループは終了します。

ジェネレータの例

もう少し実用的な例で、上で述べたジェネレータの挙動を確認してみましょう。 次のコードは 0 から n - 1 までの整数を返すジェネレータ関数です:

def firstn(n):
    num = 0
    while num < n:
        yield num
        num += 1

ここで、

for i in firstn(10):
    print(i)

を実行したときの処理の流れは次のようになります。

まず、for 文に対して firstn(10) というジェネレータイテレータが与えられることで、その __next__ メソッドが呼ばれます。 その結果、関数 firstn の実行が開始されますが、n の値は 10 であり num より大きいため、yield num が実行されます。 これにより、関数は n や num などの変数の値、yield を実行した行の情報などを記録した上で処理を停止し、num の値を返します。 こうして返された値は、i へと代入され、その値は print 関数へと渡されます。

次の for ループの繰り返しの開始時において、再度 __next__ メソッドが呼びだされ、関数 firstn の実行が再開されます。 この際、以前に記憶した情報が再利用されるため、num += 1 の行がまず実行され、num の値は 1 となります。 続いて while 文の条件式が評価されますが、n はまだ num より大きいため、また yield 式が評価されます。 ここでも評価時の情報が記録された上で num が返されますが、それが i へと代入され print 関数へと渡ります。

こうした処理が複数回繰り返され、num += 1 により num の値が 10 となると、while 文の条件式が偽と評価され、関数を抜けます。 その結果、StopIteration が送出され、これを検知した for ループは、繰り返し処理を終了します。

以上が処理の流れの詳解となります。

なお、これと同じ内容をジェネレータを用いずにイテレータとして実装すると、次のようになります:

class firstn:
    def __init__(self, n):
        self.n = n
        self.num = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.num < self.n:
            cur, self.num = self.num, self.num + 1
            return cur
        else:
            raise StopIteration

ジェネレータ関数を定義するよりもはるかに複雑さが増しています。 ジェネレータ関数がイテレータをシンプルに生成するための強力なツールであるということが理解できたはずです。

ジェネレータ式

ジェネレータはジェネレータ式 (generator expression) によって生成することも可能です。 ジェネレータ式は、外形上はリスト内包表記を丸括弧で包んだものになります:

>>> [x**2 for x in range(4)] # リスト内包表記
[0, 1, 4, 9]
>>> (x**2 for x in range(4)) # ジェネレータ式
<generator object <genexpr> at 0x7f5710576970>

ジェネレータ式は、通常のリストなどと同じように使うことができます:

>>> gen_exp = (x**2 for x in range(4))
>>> for i, x in enumerate(gen_exp):
...     print(f'{i}**2 = {x}')
...
0**2 = 0
1**2 = 1
2**2 = 4
3**2 = 9

なお、上のジェネレータ式をジェネレータ関数により定義すると次のようになります:

def f():
    for x in range(4):
        yield x**2

ジェネレータ式により、さらに簡潔にジェネレータを定義できることがわかります。

ジェネレータ式は、リスト内包表記とは異なり、generator object を返します。 これにより、要素が事前にメモリ上へと生成されることがないため、メモリ効率を高めています。 このことを実際の数値により確認してみましょう:

>>> import sys
>>> sys.getsizeof([x**2 for x in range(4)]) # リスト内包表記
88
>>> sys.getsizeof((x**2 for x in range(4))) # ジェネレータ式
112
>>> sys.getsizeof([x**2 for x in range(1024)]) # リスト内包表記
9016
>>> sys.getsizeof((x**2 for x in range(1024))) # ジェネレータ式
112

sys.getsizeof は、引数のオブジェクトのサイズをバイト単位で返します。 上の結果から、ジェネレータ式のサイズは、range に与えた数とは関係なく一定となっていることがわかります。 一方、リストのサイズは要素の個数に応じて増加していきます。 つまり、リストの要素が極端に少ない場合を除いて、ジェネレータのほうがメモリ上のサイズが小さくなるのです。 このようにして、ジェネレータのメモリ効率の良さを数値の上からも確認することができます。

パフォーマンス

ジェネレータの利点としてメモリ効率について触れましたが、注意点もあります。 あらかじめ要素をメモリ上に展開する場合と比較して、ジェネレータは要素の取得の際に関数呼び出しがあるため、そのオーバーヘッドにより実行時間が長くなるのです。 このこともコードにより確認してみましょう:

>>> import cProfile
>>> cProfile.run('sum([i * 2 for i in range(10000)])')
         5 function calls in 0.002 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    0.002    0.002 <string>:1(<listcomp>)
        1    0.000    0.000    0.002    0.002 <string>:1(<module>)
        1    0.000    0.000    0.002    0.002 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.sum}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


>>> cProfile.run('sum((i * 2 for i in range(10000)))')
         10005 function calls in 0.033 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    10001    0.016    0.000    0.016    0.000 <string>:1(<genexpr>)
        1    0.000    0.000    0.033    0.033 <string>:1(<module>)
        1    0.000    0.000    0.033    0.033 {built-in method builtins.exec}
        1    0.016    0.016    0.033    0.033 {built-in method builtins.sum}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

cProfile.run は、引数として与えられた文の実行に関する統計情報を表示する関数です。 これに基づけば、筆者の環境では、リスト内包表記を合計する計算に比べて、ジェネレータを合計する計算は関数の呼び出し回数が 1 万回多く、また 16.5 倍の時間が実行に掛かっています。

実行速度という観点から見たとき、ジェネレータは関数呼び出しのオーバーヘッドが余計に掛かる、という点は留意しておくべきでしょう。

yield from 式

Python 3.3 から導入された文法に、yield from 式があります。 これを使うと、ジェネレータから yield する値を別のイテラブルから取得している際に、記述を簡略化することができます。

たとえば次のコードは、0 から n までの値と、各値の二乗を返すジェネレータです:

>>> def both(n):
...     for i in range(n):
...         yield i
...     for i in (x**2 for x in range(n)):
...         yield i
...
>>> list(both(5))
[0, 1, 2, 3, 4, 0, 1, 4, 9, 16]

ジェネレータ関数 both は、内部で他のイテラブル (range(n) と (x**2 for x in range(n)) から値を取得し、それを yield しています。 この関数は、yield from 式により次のように書き換えることが可能です:

>>> def both(n):
...     yield from range(n)
...     yield from (x**2 for x in range(n))
...
>>> list(both(5))
[0, 1, 2, 3, 4, 0, 1, 4, 9, 16]

また、次の例は、複数のイテラブルを引数として取り、各イテラブルから取り出した値を yield していくジェネレータです (itertools.chain と同等の挙動となります):

>>> def chain(*iterables):
...     for it in iterables:
...         for i in it:
...             yield i
...
>>> list(chain('ABC', range(4)))
['A', 'B', 'C', 0, 1, 2, 3]

この関数は、次のように書き換えられます:

>>> def chain(*iterables):
...     for it in iterables:
...         yield from it
...
>>> list(chain('ABC', range(4)))
['A', 'B', 'C', 0, 1, 2, 3]

いずれの例も、イテラブルから各値を取得する処理を、yield from 式により簡略化しています。 このように、別のイテラブルから値を取得しそれを yield する場合においては、yield from 式を使用することでより簡潔に表現することができます。

まとめ

参考