エキスパートPythonプログラミング(1) イテレータ、ジェネレータ、ジェネレータ式

python

「エキスパートPythonプログラミング」の中からピックアップした話題をベースに、python user3人で勉強会(2012/08/31)しました。
その際の資料を元に、勉強会で話した内容を公開しておきます。

テーマ/キーワード

iterator、generator、generator式

以下は、話の流れで少し触れた程度
関数オブジェクト
- 有名
- 無名
closure

本日の概要

今日は、ジェネレータの話をします。

ジェネレータとは、「一旦何らかの値を戻して、しばらく後にその時点から処理を再開する」ことが出来る関数です。時間を置いて値をいくつも生成(generate)するところからそう呼ばれています。
ジェネレータは反復処理に使われるため、必ず「イテレータプロトコル」に対応します。

まず、イテレータのおさらいからします。

イテレータ

イテレータとは、単に"イテレータプロトコル"を実装したコンテナオブジェクトです。
イテレータプロトコル*1とは、次の2つのメソッドです。

  • コンテナの次の要素を返すnextメソッド(Python3系では、__next__に変更された)
  • イテレータ自身を返す__iter__メソッド

(実演) イテレータの基礎
イテレータを作ってループを回してみます。

$ python
>>> i = iter('12345')
>>> i # <iterator object at 0xXXXX>のようなイテレータオブジェクトが出来ているのが見えるはず
>>> i.next() # '1'
>>> i.next() # '2'
>>> i.next() # '3'
>>> i.next() # '4'
>>> i.next() # '5'
>>> i.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>
  • シーケンスの要素を取り出し終わるとStopIterationが発生します。
  • forループは、StopIterationの例外を捕まえるとループを終了するようになっています。

"オレオレイテレータ"を作成するには、next()メソッド、__iter__を提供するようにします。

(実演) オレオレイテレータ
初期値を与え、1ずつカウントダウンするイテレータを作ってみます。

class CountDownIter(object):
	def __init__(self, num):
		self.num = num
	def __iter__(self):   # ★ in演算子などで利用可能にする
		return self
	def next(self):       # ★ loopなどでコンテナの次の値を取り出す
		self.num -= 1
		if self.num == 0:
			raise StopIteration
		return self.num


i1 = CountDownIter(5)
i1.next() # 4
i1.next() # 3
...

i2 = CountDownIter(5)
for i in i2:
 print i

ジェネレータ

最初に話した通り、ジェネレータとは、「一旦何らかの値を戻して、しばらく後にその時点から処理を再開する」ことが出来る関数です。
"yieldステートメント"を含む関数が呼び出されたときには、イテレータプロトコルをサポートするジェネレータオブジェクトを戻します。
文字でみるより動きをみた方が早いと思うので実演でみてみます。

(実演) ジェネレータ
カウントダウンするジェネレータを作って、先のイテレータと比較してみます。

>>> def count_down_gen(num):
>>> 	while True:
>>> 		if num==0:
>>> 			raise StopIteration
>>> 		yield num
>>> 		num -= 1
>>>
>>> g1 = count_down_gen(5)
>>> g1 # <generator object <genexpr> at 0xXXXX>のようにジェネレータオブジェクトが作られているのが見えるはず
>>> g1.next() # 5
>>> g1.next() # 4
...
>>> g2 = count_down_gen(5)
>>> for g in g2:
>>>  print g

ジェネレータはイテレータの一種です。先のイテレータと同じようなことが出来ました。
さらにジェネレータでは、タダのイテレータではできない、無限数列なども実装できます。

def num_sequence(num):
	while True:
		yield num*2
		num += 1		


g3 = num_sequence(5)
print g3
g3.next()

〜本の解説より〜
開発者は長年、普通にリストを返す関数を利用することになれてきました。
ループ処理やシーケンスを返す関数を実装するときには、まずジェネレータの利用を検討すべきです。
一つずつ要素を返すことで、その要素を使用する他の関数へ渡す場合に全体のパフォーマンスを向上させます。

==>上記の例だと、無限に続く数列をリストで表現しようとすると、無限大なメモリサイズが必要になりますが、ジェネレータを使えば、解説のように"1要素と要素を生成する式"しか返さないのでメモリ効率が上がります。
(有限でも大きなリストを扱う場合には同じ話ですね)

標準ライブラリのtokenizeモジュールは、テキストストリームから1行ずつ取り出し、トークンを生成するイテレータを返します。
何らかの処理を行うコードに対して、トークンを一つずつ渡すことができます。

このように、ジェネレータでは処理を一時停止した時のステート情報を保持し、後で再開できるようにします。

ジェネレータ式

yieldを使う代わりに、丸括弧"()"を使ってもジェネレータ作ることができ、新たなジェネレータオブジェクトを生み出せます。
これをジェネレータ式といいます。
ジェネレータ式は単一の式の後ろに少なくとも一つの for 節と、場合によりさらに複数のfor または if 節を 続けたものです。
ジェネレータ式の使う変数の評価は、ジェネレータオブジェクトに対して next() メソッドを呼び出すまで遅延されます。
実演をみてもらうと、リストと比べると効率が良いことが分かるとおもいます。

(実演) ジェネレータ式

g4 = (x**2 for x in range(10) if x%2 == 0) # 0〜10の数字のうち偶数のものの2乗を返すgenerator objectを作る。
print g4
g4.next()

#リスト
l1 = [x**2 for x in range(10) if x%2 == 0]  # あらかじめ全部メモリ展開してしまう
print l1  # [0, 4, 16, 36, 64]

ジェネレータ式の目的は、主にメモリ使用量の最適化です。
実効速度はリスト内包表記より遅い場合があるので、実行結果の要素数が膨大になる場合のみにしたほうが良いそうです。

◆余談1 〜ジェネレータとジェネレータ式について〜

自分の理解では、有名のオブジェクトに対する無名のオブジェクトの関係みたいなものかなと思っています。
例えば、
「関数」に対する「λ式」と同様に、
「ジェネレータ」に対する、「ジェネレータ式」
のように理解しています。
言葉で説明してもよく分からないと思うので、実例をみてみます。

(実例)
□関数(有名関数)

def hoge(x):
 return x*10

ret = hoge(5)

□λ式(無名関数)

ret = (lambda x: x*10)(5)
#      ^^^^^^^^^^^^^^^^
#      --> "def hoge(x)" に相当

#※lambdaを有名な関数にするには以下のようにしてもOK
func1 = (lambda x: x*10)
ret = func1(5)

#※有名関数の関数オブジェクトも同様
func2 = hoge
ret = func2(5)

□ジェネレータ(有名ジェネレータ)

def fuga(max):    
 for e in range(max):
  yield e**2

g=fuga(10)
g.next()

□ジェネレータ式(無名ジェネレータ(?))

max=10
g=(e**2 for e in range(max))
g.next()

◆余談2 〜状態を持つ〜

クロージャは関数が状態を持ったようなものですが、
ジェネレータもクロージャの一種です(多分)。

クラスインスタンスは状態を持てるので、ジェネレータもクロージャもクラスで表現できます。
ただ、クラスですべてすると冗長になるので、クロージャやジェネレータで省力化するのかなと思います。
(理解が間違ってるかもしれないので、乞うご意見)

◆余談3 〜便利なツールの紹介：itertools〜

itertoolsという、イテレータ(+ジェネレータ)の扱いを便利にするモジュールがpythonにはあります。
これを使うとイテレータ同士の演算や、結合(chain)、分割(tee)、uniqしたり(groupby)など、いろいろできて実用上も便利です。
http://www.python.jp/doc/2.6/library/itertools.html

参考

  • 「エキスパート Python プログラミング」, Tarek Ziade 著, 稲田直哉,渋川よしき,清水川貴之,森本哲也 訳,ASCII
  • 「初めてのPython 第3版」,Mark Lutz 著,夏目 大 訳,O'REILLY


◆◆◆勉強会中のツッコミを反映しておきました◆◆◆
・イテレータ、ジェネレータはリストとの比較をしないほうが良いかもしれない。
==>"状態を持つリストのようなもの"という表現を削除しました。
・ジェネレータもクロージャでは？
==>多分そうなので、追記して置きました。

◆◆◆勉強会中に出た話題◆◆◆
・for文でリスト使えればイテレータいらなくね?というツッコミ
==>イテレータを使うメリットに2つありそう
- イテレータは抽象的な概念なのでnext()の実装を動的に変えることが出来るなど拡張性を高められる
- リストのように事前にすべて計算されていない場合にも対応できる(前述のオレオレイテレータの例を参照)

初めてのPython 第3版

初めてのPython 第3版

エキスパートPythonプログラミング

エキスパートPythonプログラミング

*1:ここで言うプロトコルは、通信などの"プロトコル"のイメージとは異なり"規約"くらいの意味です。語源は同じだけど。