Python のジェネレータってなに?




簡単に言えば...

リストを返す関数みたいなもの






メリットは...

メモリの消費量を抑えられる






デメリットは...

リストに比べると使い勝手が悪い








リストを返してくれる関数について考えたいと思います。 組み込みモジュール itertools の中に accumulate 関数 という、累積和を返してくれる関数があります。

import itertools

lst = itertools.accumulate((1, 2, 3, 4, 5))

for e in lst:
    print(e)

# 1
# 3
# 6
# 10
# 15



リストを使ったものとジェネレータを使ったものを、 それぞれ実装して比較してみたいと思います。

1. list を返す関数で実装する。

# リストを返す関数
def accumulate_list(iterable):
    current = 0
    lst = []
    for element in iterable:
        current += element 
        lst.append(current)
    return lst

# リスト
lst = accumulate_list((1, 2, 3, 4, 5))

for e in lst:
    print(e)

# 1
# 3
# 6
# 10
# 15

2. ジェネレータ関数で実装する。

yiled 文を使った関数定義文を ジェネレータ関数 と言います。 ジェネレータ関数が返すオブジェクトを ジェネレータイテレータ と言います。

# ジェネレータ関数
def accumulate_generator(iterable):
    current = 0
    for element in iterable:
        current += element 
        yield current

# ジェネレータイテレータ
gen = accumulate_generator((1, 2, 3, 4, 5))

for e in gen:
    print(e)

# 1
# 3
# 6
# 10
# 15





リスト lst と ジェネレータイテレータ gen は、 まったく同じ動作をしているように見えます。違いは何でしょうか?


1 章...リストジェネレータイテレータ
2 章...リスト内包表記ジェネレータ式
3 章...ジェネレータ式高階関数 map, filter
4 章...ジェネレータ関数ジェネレータイテレータ
5 章...ジェネレータ関数定義普通の関数定義
6 章...ジェネレータ関数を再帰呼び出ししたい。
7 章...for 文で使うと空っぽになるので注意してください。
8 章...まとめ

1. リスト と ジェネレータイテレータ の違いってなに?

答え: 要素を生成するタイミングが違います。

for 文は要素を1つずつ取り出してくれます。

リストは、for loop が実行される前に、全ての要素を生成します。 それに対してジェネレータイテレータは、for loop が回るたびに、処理を起動をして要素を生成し、要素を渡したら処理を中断しています。

◯ ジェネレータのデメリット

このようにして、必要になるまで処理を実行しないことを遅延評価と言います。 遅延評価のため、ジェネレータは for 文や next 関数 を使って1つ1つ要素を取り出すことはできますが。

gen = accumulate_generator(range(10))
next(gen)  #  0
next(gen)  #  1
next(gen)  #  3
next(gen)  #  6
next(gen)  # 10
next(gen)  # 15
next(gen)  # 21
next(gen)  # 28
next(gen)  # 36
next(gen)  # 45
next(gen)  # StopIteration


反対に、いきなり途中の要素、例えばいきなり 5 番目の要素を取り出すというようなことはできません。

lst = accumulate_list(range(10))
lst[5]

gen = accumulate_generator(range(10))
gen[5]  # TypeError


また next 関数によって次の要素を取り出すことはできますが、1つ前の要素を取り出すと言ったこともできません。

◯ ジェネレータのメリット

リストは全ての要素を生成してしまうので、大量のメモリを消費してしまいます。 ジェネレータイテレータは、必要なものしか作らないので、そうでもありません。

int 型くらいならいいかもしれませんが、ファイルなど大量の str 型を扱う場合には、 意識しないといけないことになります。

import sys

# メモリを大量消費(実行に時間がかかります。)
sys.getsizeof(accumulate_list(range(10**8)))
# 859724472

# メモリをあまり消費しない
sys.getsizeof(accumulate_generator(range(10**8)))
# 88

◯ まとめ

ジェネレータイテレータは、リストではありません。 デメリットは、リストのように途中の値を参照することはできず、すこし使い勝手が悪いです。 メリットはメモリの消費量を抑えることができます。 大量のオブジェクトを取り扱う時に威力を発揮します。

2. リスト内包表記 と ジェネレータ式

リストを返す簡易的な表記がリスト内包表記なら、ジェネレータイテレータを返す簡易的な表記がジェネレータ式です。

# リスト
lst = [i for i in range(10)]

def f():
    lst = []
    for i in range(10):
        lst.append(i)
    return lst

assert lst == f()
# ジェネレータ
gen = (i for i in range(10))

def g():
    for i in range(10):
        yield i

assert list(gen) == list(g())


iterable な引数を1つしか取らない関数には、ジェネレータ式をそのまま書き込むことができます。

sum(i for i in range(10))

# 二重の括弧はいらない
# sum((i for i in range(10)))

3. ジェネレータ式 と 高階関数

関数を引数に取る関数を高階関数と呼びます。例えば map, filter は、高階関数です。ジェネレータ式と同じ役割を果たします。

lst = [0, 1, 2, 3]

# 高階関数, map
list(map(lst, lambda x: x * x))

# ジェネレータ式
list(x * x for x in lst)

◯ 使い分けは?

果たしてどちらを使うべきでしょうか?基本的には読みやすい方を。 どちらでも良い場合は、ジェネレータ式を使った方が良いかなと思ったりもします。

例えば、既に関数が定義されているようなシーンでは map を使うといいかなと。 簡単に言えば lambda 式を使うくらいならジェネレータ式やリスト内包表記で書いた方が良いかなと思ったりもします。

# 0. 元のやり方
#     関数 f を 2 回呼び出しててちょっと嫌だな...
[f(x) for x in lst if f(x) % 2 == 0]

# 1. map を使った改善例
[y for y in map(f, lst) if y % 2 ==0]

# 2. ジェネレータ式を使った改善例
[y for y in (f(x) for x in lst) if y % 2 == 0]

# 3. かと行って lambda を使ってまで高階関数を使うと、なんだか汚くなる
list(filter(lambda y: y % 2 == 0, map(f, lst)))

◯ Guido が嫌いな高階関数 map, filter, reduce

ただし Guido はジェネレータ式の方が綺麗な書き方だと考えているようです。 以下の資料で map, filter の比較対象が list comprehensions, リスト内包表記となっているのは Python 2 の頃の話で map, filter がリストを返す関数だったため。

  • I've never liked lambda

    • crippled (only one expression)
    • confusing (no argument list parentheses)
    • can use a local function instead
  • map(), filter()

    • using a Python function here is slow
    • list comprehensions do the same thing better
  • reduce()

    • nobody uses it, few understand it
    • a for loop is clearer & (usually) faster

Python Regrets - Guido van Rossum


リスト内包表記は、組み込み関数のmap()とfilter()の代替手段となっている。 map(f, S)は、[f(x) for x in S]と同じ意味となるし、filter(P, S)は[x for x in S if P(x)]と同じ意味となる。 map()やfilter()を使った表現の方がコンパクトであるため、 リスト内包表記の方が推奨されていないのでは?と思う人もいるだろう。

しかし、より現実的なサンプルを見ると見解が変わるだろう。 与えられたリストの全ての要素に数字の1が足された、新しいリストを作りたいとする。 リスト内包表記を使った場合には、[x+1 for x in S]と表現できる。 map()を使うと、map(lambda x: x+1, S)となる。 "lambda x: x+1"はインラインで無名関数を作るPythonの書き方である。

ここでの本当の問題はPythonのラムダ記法が冗長すぎることで、 この表記がもっと簡潔になればmap()を使った記法がより魅力的になるはずだ、ということがずっと主張されてきた。 私個人の見解としてはこれには反対である。 リスト内包表記の方が、 特にマップされる式の複雑さが増加するとmap()を使った関数表記よりも見やすくなることが分かったからである。

リスト内包表記〜ジェネレータ式 -The History of Python.jp

◯ 実は関数じゃなくてクラスです

map, filter は高階 関数 と書きましたが、Python 3 では map, filter はクラスになっています。組込型はクラス名が大文字でないので誤解しやすい。

assert isinstance(map, type)
assert isinstance(filter, type)

4. ジェネレータ関数 と ジェネレータイテレータ

ジェネレータという言葉には、実は2つの意味があります。区別しましょう。

generator(ジェネレータ)
通常は ジェネレータ関数 を指しますが、文脈によっては ジェネレータイテレータ を指す場合があります。 意図された意味が明らかでない場合、 明瞭化のために完全な単語を使用します。

ジェネレータ関数 (generator function)
yield 文 (yield 文 の節を参照) を使う関数もしくはメソッドを ジェネレータ関数 と呼びます。 そのような関数が呼び出されたときは常に、関数の本体を実行するのに使えるイテレータオブジェクトを返します: イテレータiterator.__next__() メソッドを呼び出すと、 yield 文を使って値が提供されるまで関数を実行します。 関数の return 文を実行するか終端に達したときは、 StopIteration 例外が送出され、イテレータが返すべき値の最後まで到達しています。

generator iterator(ジェネレータイテレータ)
generator 関数で生成されるオブジェクトです。 yield のたびに局所実行状態 (局所変数や未処理の try 文などを含む) を記憶して、処理は一時的に中断されます。 ジェネレータイテレータ が再開されると、中断した箇所を取得します (通常の関数が実行の度に新たな状態から開始するのと対照的です) 。

5. ジェネレータ関数 と 普通の関数

Guido van Rossum はジェネレータ関数について、普通の関数を定義する def とは別の用語を、例えば gen のような語を定義しようか迷ったそうです。

何故なら、ジェネレータ関数と普通の関数は、異なるものだからです。それは次の2点で異なります。

1つ目は、関数は return で1度に全ての返り値を評価して返すのに対して、ジェネレータ関数は yeild で返り値を個々に遅延評価して返します。

2つ目は、関数は return で指定されたオブジェクトそのものを返すのに対して、 ジェネレータ関数は yield で指定されたオブジェクトを返すジェネレータイテレータを返します。

最終的には Guido は、自分の直感に従ったそうです。PEP 255 の文章を引用します。 ここで慈悲深き終身独裁官とは Guido を指しています。

慈悲深き終身独裁官による判決 - PEP 255 Simple Generators
BDFL Pronouncements - PEP 255 Simple Generators

議論
issue
ジェネレータ関数をジェネレータでない関数と区別するために def の代わりに gen や generator のような別の新しいキーワードを導入するか、 あるいは構文を変えるべきかどうか
Introduce another new keyword (say, gen or generator) in place of def, or otherwise alter the syntax, to distinguish generator-functions from non-generator functions.

欠点
con
実際には(あなたがジェネレータをどのように考えているかという観点から言えば)、 ジェネレータは関数である。再開可能であるという差異はあるが。ジェネレータがどのように始動するかという動作原理は、比較的些細な技術的問題である。 新しいキーワードの導入は、ジェネレータがどのように起動するかという動作原理を過度に強調してしまう (起動に関する動作原理は、重要ではあるがジェネレータ全体の動作から見れば小さい)。
In practice (how you think about them), generators are functions, but with the twist that they're resumable. The mechanics of how they're set up is a comparatively minor technical issue, and introducing a new keyword would unhelpfully overemphasize the mechanics of how generators get started (a vital but tiny part of a generator's life).

利点
pro
現実には(あなたがジェネレータをどう考えてるかという観点から言えば)、 ジェネレー関数は、実際、ファクトリー関数である。この関数は、関数の動作から考えれば あたかも魔法を使ったように、ジェネレータ関数はジェネレータイテレータを生成している。この観点から言えば、 ジェネレータでない関数とは根本的に違う。関数というよりもむしろ、コンストラクタのように振舞っている。 本文に埋め込まれた yield 文だけでは、意味的に全く違うことを示すには不十分である。
In reality (how you think about them), generator-functions are actually factory functions that produce generator-iterators as if by magic. In this respect they're radically different from non-generator functions, acting more like a constructor than a function, so reusing def is at best confusing. A yield statement buried in the body is not enough warning that the semantics are so different.

慈悲深き終身独裁官
BDFL
私の直感は def と言った。どちらの主張についても完全に納得がいくようなものがない。 そのため、私は自分の言語設計者としての直感に相談することにした。
def it stays. No argument on either side is totally convincing, so I have consulted my language designer's intuition.

私の直感は、「PEP で提案されている構文は、まさに的確である - 暑すぎず寒すぎず、ちょうど良い」と教えてくれた。しかしギリシャ神話のデルポイのご神託のように、なぜそうなのか理由は説明はしてくれない。なので、私は PEP で提案された構文にについての議論に対して、反証するものを持っていない。
It tells me that the syntax proposed in the PEP is exactly right - not too hot, not too cold. But, like the Oracle at Delphi in Greek mythology, it doesn't tell me why, so I don't have a rebuttal for the arguments against the PEP syntax.

最も思いついたものは "恐怖と不安と疑念" である(既に反証がないということに関して同意したことは、さておき)。もし、ある日から、これが言語の一部になったら、私は Andrew Kuchling の "Python の嫌なところ" に掲載されのではないかと、ひどく疑問に感じる。
The best I can come up with (apart from agreeing with the rebuttals ... already made) is "FUD". If this had been part of the language from day one, I very much doubt it would have made Andrew Kuchling's "Python Warts" page.

何故ジェネレータ関数定義は「def」を関数定義と共有して... - Qiita
PythonWarts - Python Wiki

全然どうでもいいのですが BDFL Pronouncements って Senatus consultum ultimum みたいな感じがしてカッコいい...

6. 再帰呼び出しでリストを生成する関数を
ジェネレータ関数に書きかえたい。

◯ ジェネレータ関数から別のジェネレータ関数を呼び出したい

単純に yield を使って呼び出してみます。

def f():
    yield g1()
    yield g2()

def g1():
    yield 0
    yield 1

def g2():
    yield 2
    yield 3

[i for i in f()]
# [<generator object g1 at 0x100e9db48>, <generator object g2 at 0x100e9dba0>]


yield from を使うと上手くいきます。

def f():
    yield from g1()
    yield from g2()

def g1():
    yield 0
    yield 1

def g2():
    yield 2
    yield 3

[i for i in f()]
# [0, 1, 2, 3]


yield from は、処理を subgenerator 子ジェネレータに処理を deligate 移譲しています。 yield from は PEP 380 で Python 3.3 から採用されました。
PEP 380 - 子ジェネレータに処理を移譲する書き方について

再帰呼び出しでリストを生成する関数を
ジェネレータ関数に書きかえたい。

リストを生成する関数は、ジェネレータ関数で簡単に表現できました。 しかし、再帰呼び出しでリストを生成する関数の場合、単純に yiled を使うとうまく動作しません。

例えば、下図のような二分探索木は、再帰呼び出しを使えば、簡単にソートされたリストを生成することができます。 しかし、再帰呼び出しを使うため、yiled は、そのままでは使えません。

f:id:domodomodomo:20171119172218p:plain


その原因は上でみたとおりです。 そのまま yiled を使うとジェネレータイテレータ、そのものが返されてしまいます。

再帰呼び出しでリストを生成する関数を、ジェネレータ関数で表現するときは yield from を使います。


def sample_code():
    # 上の図と同じ木を作る。
    binary_search_tree = BinarySearchTree()
    for value in (8, 3, 1, 6, 10, 4, 7, 14, 13):
        binary_search_tree.insert(value)
    
    print(binary_search_tree.list())
    # [1, 3, 4, 6, 7, 8, 10, 13, 14]
    
    print(list(binary_search_tree))
    # [1, 3, 4, 6, 7, 8, 10, 13, 14]


class BinarySearchTree(object):
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root:
            self.root.insert(value)
        else:
            self.root = BinarySearchNode(value)
    
    def list(self):
        if self.root:
            return self.root.list()
        else:
            return []
    
    def __iter__(self):
        if self.root:
            return iter(self.root)
        else:
            return iter([])


class BinarySearchNode(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
    def insert(self, value):
        if value <= self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinarySearchNode(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinarySearchNode(value)
    
    
    #
    # 1. 再帰呼び出しでリストを生成する関数を
    #
    def list(self):
        sorted_list = []
        if self.left:
            sorted_list.extend(self.left.list())
        sorted_list.append(self.value)
        if self.right:
            sorted_list.extend(self.right.list())
        return sorted_list
    
    #
    # 2. ジェネレータで書き換え
    #    再起の部分には yeild ではなく yiled from を使う。
    #
    def __iter__(self):
        if self.left:
            yield from self.left
        yield self.value
        if self.right:
            yield from self.right


if __name__ == '__main__':
    sample_code()


上記のコードは、簡易版です。二分探索木そのものについては、ここで書きました。 ジェネレータ関数を使わずに Path というイテレータを実装しています。 ジェネレータを使うと簡潔にイテレータを表現できていることがわかります。

7. 請注意 for 文で使うと空っぽになります

実は、ジェネレータイテレータは、1度 for 文で回すと空になります。 このことに引っかかって、時間を費やしてしまった方を Twitter や Qiita でたまに見かけます。

map/zip/filter オブジェクトに対して、list を2回やると空っぽになります。 最初何が起こったのかわからずバグじゃないかとか、破壊的メソッドか!?などと思ったりしたわけですが、仕様らしいです。
python の map オブジェクトを list にした後は何も残らない - Qiita


実際に見てましょう。

def accumulate_generator(iterable):
    current = 0
    for element in iterable:
        current += element
        yield current


gen = accumulate_generator(range(10))



for e in gen: e

# 0, 1, 3, 6, 10, 15, 21, 28, 36, 45

for e in gen: e

# 2回目は、何も表示されない


なぜ、このようなことが起こるのでしょうか? それはジェネレータイテレータイテレータだからです。

原因と対策、イテレータとは何かについては、こちらで書きました。 実はこの記事は、以下の記事からの続きになります。

8. まとめ

ジェネレータイテレータは、リストを表現してくれています。 しかも実際にリストを生成することなく。 これによってメモリの使用料を削減することができます。 つぎの2つを区別しましょう。

1.リストを返す関数ジェネレータ関数
2.リスト内包表記ジェネレータ式


ジェネレータ関数を使えば、イテレータを簡潔に実装できます。 例えば、データの集合を表すクラスの __iter__ メソッドで直接、ジェネレータ関数を定義したら、 イテレータクラスを実装しなくても、クラスを iterable にできました。

ジェネレータという言葉は、ときと場合によって、ジェネレータイテレータであったり、 ジェネレータ関数であったりします。つぎのことを区別しましょう。

3.ジェネレータイテレータジェネレータ関数





最後の仕上げに iterable とは何かについて、考えて見ます。より正確に Python の型, プロトコルについて考えて見たいと思います。