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




簡単に言えば...

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






メリットは...

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






デメリットは...

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








リストを返してくれる関数について考えたいと思います。 標準ライブラリ 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 章...どっちを使うべき?
4 章...ジェネレータイテレータを使うときの注意事項
5 章...ジェネレータ関数ジェネレータイテレータ
6 章...ジェネレータ関数定義普通の関数定義
7 章...まとめ




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. ジェネレータイテレータとリストどっちを使うべき?

答え: 基本的にはジェネレータかな...

3.1. なんで?

答え: Python 2 では list を返す関数だった zip, range, map, filter が Python 3 ではイテレータクラスに変更されたから
リストを使わずにイテラブルなオブジェクトを返す - Python 2.7.x と 3.x の決定的な違いを例とともに

Python の開発者の人たちの意図としては、基本的にはリストよりもイテレータを使いましょうね。という雰囲気なのかなと思っています。 メモリの消費というのがクリティカルだったのかなと思います。

また、書籍 Effective Python の項目 16 でも「リストを返さずにジェネレータを返すことを考える」と書かれています。

3.2. ジェネレータとリストのメリットデメリット

もう1度、メリットデメリットを再確認してみます。

項目 ジェネレータ リスト
速度 ごく若干遅い ごく若干速い
メモリ O X
扱いやすさ X O
書きやすさ list の初期化不要 list の初期が必要
3.2.1. 速度

実は速度は、ほんの、ほんのすこしだけリストが速そうです。
6. リストとイテレータの速度の比較 - Python を高速化したい

3.2.2. 書きやすさ

ほんの、ほんのちょっとだけ短くなります。

# リストを返す関数
def accumulate_list(iterable):
    current = 0
    lst = []  # <- 余分な1行
    for element in iterable:
        current += element 
        lst.append(current)  # <- append って書かないといけない
    return lst

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

4. ジェネレータイテレータを使うときの注意事項

実は、ジェネレータイテレータは、1度 for 文で回すと空になります。 このことに引っかかって、時間を費やしてしまった方を Twitter や 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回目は、何も表示されない

驚いたことに、ジェネレータの戻り値に ... 何も結果が得られません。... この振る舞いの原因は、イテレータが結果を一度だけしか生成しないことです。... 紛らわしいのは、すでに尽きてしまったイテレータに対して反復処理をしても、何のエラーも生じないことです。
項目17: 引数に対してイテレータを使うときには... - Effective Python


なぜ、このようなことが起こるのでしょうか? それはジェネレータイテレータイテレータだからです。 この原因の詳細は、このあと「イテレータってなに?」の中で説明させていただきます。

とりあえず対応策だけ知りたい方は、こちらからどうぞ。3つの対応策を示しています。
Python のイテレータってなに? - いっきに Python に詳しくなるサイト

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

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

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

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

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

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

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 みたいな感じがしてカッコいい...

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

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

単純に 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.generator()))
    # [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 generator(self):
        if self.root:
            return self.root.generator()
        else:
            # empty generator
            return (_ for _ in range(0))


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 generator(self):
        if self.left:
            yield from self.left.generator()
        yield self.value
        if self.right:
            yield from self.right.generator()


if __name__ == '__main__':
    sample_code()


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

頑張ってはいますが、実はまだまだ書きかけです。説明とソースコードは一段落していて、 ざっと眺めていただく分には問題ないかなとは思うのですが、説明だけになっていて、 「え?だからなに?」みたいな、まだ取っ掛かりにくい記事になっています。 とりあえずいまは yield from という言葉があるんだくらいに捉えておいていただけると幸いです。

8. まとめ

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

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

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

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



実は、この記事は「for 文を理解する5講座」の2回目になります。 f:id:domodomodomo:20181103193404j:plain

次はジェネレータ式と全く同じ機能を持つ map, filter について、触れていきます。 1回目は簡単な導入なので、このまま3回目に進んでいただいても大丈夫です。

なぜ、同じ機能を持ったものが2つも存在するのでしょうか?