イテレータとジェネレータ
Contents
15. イテレータとジェネレータ#
import sys
15.1. イテレータ#
自然数\(n\)が与えられたとき、\({}_n C_k\) (\(k = 0, 1, \dots, n\))、および\(\sum_{k=0}^{n} {}_n C_k\)を計算するプログラムの例を示す。
n = 6
v = 1
s = 0
for k in range(n+1):
print(v)
s += v
v *= (n-k)
v //= (k+1)
s
1
6
15
20
15
6
1
64
このプログラムは期待した通りの結果を返すが、for文の反復内容に\({}_n C_k\)を計算する部分が入るため、見通しが悪い。また、\(\sum_{k=0}^{n} (-1)^k{}_n C_k\)を計算するようにプログラムを改変するには、\({}_n C_k\)を計算する部分も含めて、実装を修正する必要が生じる。見通しのよいプログラムを書くために、range関数が\(0, 1, \dots, n\)を返すように、\({}_n C_0, {}_n C_1, \dots, {}_n C_n\)を返す関数combinationsを定義し、以下のようなプログラムを書きたい。
s = 0
for v in combinations(n):
print(v)
s += v
s
おそらく、真っ先に思い浮かぶのはcombinations関数を\({}_n C_k\) (\(k = 0, 1, \dots, n\))のリストを返す関数として実装することであろう（後ほど異なる実装を示すことになるので、ここではcombinationではなくlist_combinationsという名前の関数として実装する）。
def list_combinations(n):
v = 1
C = []
for k in range(n+1):
C.append(v)
v *= (n-k)
v //= (k+1)
return C
list_combinations関数の動作を確認する。
list_combinations(n)
[1, 6, 15, 20, 15, 6, 1]
このlist_combinations関数を使うと、先ほどの処理を行うプログラムは次のように書ける（呼び出し元のプログラムの見通しは良くなった）。
s = 0
for v in list_combinations(n):
print(v)
s += v
s
1
6
15
20
15
6
1
64
また、\(\sum_{k=0}^{n} (-1)^k{}_n C_k\)を計算するには、その計算の箇所だけ変更すればよい（動作を分かりやすくするため、print(k, v)を入れてある）。
t = 0
for k, v in enumerate(list_combinations(n)):
print(k, v)
t += ((-1) ** k * v)
t
0 1
1 6
2 15
3 20
4 15
5 6
6 1
0
なお、和の計算結果のみが必要であれば、sum関数を用いるだけでよい。
sum(list_combinations(n))
64
これにより、見通しのよいプログラムを分かりやすく書くことができたが、一つだけ心残りがある。それは、\({}_n C_0, {}_n C_1, \dots, {}_n C_n\)のすべての値を要素とするリストを一時的に作成・保持してしまう点である。今回の目的が\(\sum_{k=0}^{n} {}_n C_k\)の値を計算することだけであったら、\({}_n C_k\)のすべての値をメモリに保持するのは無駄である。なぜなら、\({}_n C_k\)のすべての値に同時またはランダムにアクセスする必要は無いからである。
\({}_n C_0, {}_n C_1, \dots, {}_n C_n\)のように、要素の値を順に返すような動作を実現してくれる仕組みがイテレータである。オブジェクトにイテレータの機能を実装することで、for文の反復対象として用いることができるようになる。オブジェクトにイテレータを実装するには、__iter__メソッドと__next__メソッドを実装すればよい。__iter__メソッドはイテレータオブジェクト自身を返すもので、通常はselfを返せばよい。__next__メソッドには次の要素を返す処理を実装する。これ以上返す要素が無い場合は、StopIteration例外を送出させる。
class iter_combinations:
def __init__(self, n):
self.v = 1
self.k = 0
self.n = n
def __iter__(self):
return self
def __next__(self):
if self.n < self.k:
raise StopIteration
v = self.v
self.v *= (self.n - self.k)
self.v //= (self.k+1)
self.k += 1
return v
このiter_combinations関数（実際にはクラス）を呼び出すプログラムは、list_combinations関数でリストを予め生成した場合と完全に同じである。
s = 0
for v in iter_combinations(n):
print(v)
s += v
s
1
6
15
20
15
6
1
64
なお、和の計算結果のみが必要であれば、list_combinations関数でリストを予め生成した場合と同様に、sum関数を用いるだけでよい。
sum(iter_combinations(n))
64
\(\sum_{k=0}^{n} (-1)^k{}_n C_k\)の計算も同様である。
t = 0
for k, v in enumerate(iter_combinations(n)):
print(k, v)
t += ((-1) ** k * v)
t
0 1
1 6
2 15
3 20
4 15
5 6
6 1
0
当たり前ではあるが、iter_combinationsクラスのオブジェクトはリストではない。
iter_combinations(n)
<__main__.iter_combinations at 0x7fe9f02f6e20>
type(iter_combinations(n))
__main__.iter_combinations
isinstance(iter_combinations(n), list)
False
iter_combinationsクラスのイテレータ・オブジェクトから順に要素を取り出すにはnext関数を用いる。すべての要素を取り出した後、StopIteration例外が送出されていることが分かる。
i = iter_combinations(4)
next(i)
1
next(i)
4
next(i)
6
next(i)
4
next(i)
1
next(i)
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
/tmp/ipykernel_2812/1939748483.py in <module>
----> 1 next(i)
/tmp/ipykernel_2812/1028479797.py in __next__(self)
10 def __next__(self):
11 if self.n < self.k:
---> 12 raise StopIteration
13 v = self.v
14 self.v *= (self.n - self.k)
StopIteration:
実際にイテレータ・オブジェクトが消費しているメモリ量を見積もるため、sys.getsizeofを用いる。\(n=5\)のとき、list_combinations関数が生成するオブジェクトよりもiter_combinationsクラスが生成するオブジェクトの方がメモリ消費量が少ない。
sys.getsizeof(iter_combinations(5))
48
sys.getsizeof(list_combinations(5))
120
続いて、\(n=100000\)とすると、メモリ消費量の差は顕著になる。list_combinations関数が生成するオブジェクトのメモリ消費量は増えていくが、iter_combinationsクラスが生成するオブジェクトのメモリ消費量は\(n\)によらず一定である。これは、イテレータがすべての要素を持つリストを生成せずに、要素を順番に返す仕様になっているからである。
sys.getsizeof(list_combinations(100000))
824456
sys.getsizeof(iter_combinations(100000))
48
15.2. ジェネレータ#
先ほどの\({}_n C_k\) (\(k = 0, 1, \dots, n\))を計算する例において、list_combinations関数とiter_combinations関数の実装を再掲する。。
def list_combinations(n):
v = 1
C = []
for k in range(n+1):
C.append(v)
v *= (n-k)
v //= (k+1)
return C
class iter_combinations:
def __init__(self, n):
self.v = 1
self.k = 0
self.n = n
def __iter__(self):
return self
def __next__(self):
if self.n < self.k:
raise StopIteration
v = self.v
self.v *= (self.n - self.k)
self.v //= (self.k+1)
self.k += 1
return v
s = 0
#for v in list_combinations(6):
for v in iter_combinations(6):
print(v)
s += v
s
1
6
15
20
15
6
1
64
list_combinations関数とiter_combinationsクラスの実装を比較すると、list_combinations関数の方が見通しがよい。これは、反復処理をfor文で書くことができるため、反復の開始から終了まで、繰り返しの処理内容をまとめて記述できるからである。一方、iter_combinationsクラスにおける__next__メソッドでは、現在の状態から次の要素を返す処理を記述することになるため、反復処理全体の流れが分かりにくい。
この両者の良いところ取りはできないものか？ すなわち、list_combinations関数のように反復処理を書くことができ、かつiter_combinationsクラスのようにイテレータとして振る舞う方法は無いだろうか？ これを実現するのが、yield文によるジェネレータ関数である。関数の中でyield文を記述すると、その関数はジェネレータ関数となる。yield文はreturn文に似ているが、関数の振る舞いをイテレータに変更し、要素を順番に返せるようにするものである。yield文が実行されると、関数の実行は中断し、yield文で指定された値が要素として呼び出し元に返される。言い換えれば、yield文の実行と、イテレータの__next__メソッドの返り値が対応する。
以下のgen_combinations関数は、ジェネレータ関数によるイテレータの実装である。list_combinations関数でリストにappendする代わりに、yield文を実行するプログラムとなる。
def gen_combinations(n):
v = 1
for k in range(n+1):
yield v
v *= (n-k)
v //= (k+1)
s = 0
for v in gen_combinations(6):
print(v)
s += v
s
1
6
15
20
15
6
1
64
sum(gen_combinations(6))
64
yield文を含む関数はジェネレータ関数となる。関数の戻り値はジェネレータ型であり、これはイテレータ・オブジェクトとして用いることができる。
gen_combinations(4)
<generator object gen_combinations at 0x7fe9f0232dd0>
type(gen_combinations(4))
generator
ジェネレータ関数の返り値はイテレータとして振る舞うので、next関数を用いて順に要素を取り出すことができる。すべての要素を取り出した後、StopIteration例外が送出される。
i = gen_combinations(4)
next(i)
1
next(i)
4
next(i)
6
next(i)
4
next(i)
1
next(i)
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
/tmp/ipykernel_2812/1939748483.py in <module>
----> 1 next(i)
StopIteration:
15.3. ジェネレータ式#
リストの内包表記で\(\{n^2 | n \in \{0, 1, 2, 3, 4, 5\}\}\)をリストとして得る例である。
[n**2 for n in range(6)]
[0, 1, 4, 9, 16, 25]
得られたリストに対して、sum関数で和を取ることで、\(\sum_{n=0}^5 n^2\)を計算する。
sum([n**2 for n in range(6)])
55
[]を()に変更すると、ジェネレータを内包表記で作成できる（ジェネレータ式）。以下のように関数の唯一の引数として用いる場合は、括弧を二重（((や))）にしなくてもよい。
sum(i**2 for i in range(6))
55
ジェネレータ式で\(\sum_{k=0}^{6} (-1)^k{}_6 C_k\)を計算する。
sum((-1) ** k * v for k, v in enumerate(iter_combinations(6)))
0