Pythonのiterable

iterable

イテラブルオブジェクト

イテラブルオブジェクトとはfor文で反復可能なオブジェクトのことです.

# range(5) - range()関数の返すオブジェクトはイテラブル
 for i in range(5) :
    print(i)
    
# [1,2,3]　- リストはイテラブル
for i in [1,2,3] :
    print(i)

# "apple" - 文字列も イテラブル
for i in "apple" :
    print(i)

# 他にも, 辞書, セット,　タプルなどもイテラブル

イテレーター

イテレーターはオブジェクトが無限に連なっている鎖のようなイメージの構造をもつオブジェクトです.　イテレーターはリストに似ていますが少し違います. イテレーターとリストの違いをこの記事では少しずつ明確にします. イテレーターもfor文で反復可能なのでイテラブルオブジェクトの一種です.

オブジェクト1 - オブジェクト2 - オブジェクト3　- ... - オブジェクトn - ...

数学の言葉でいうとイテレーターは点列 $\lbrace a_n \rbrace_{ n=1,2,...}$
です. 　点列の点が数のとき,それを数列といいます. 数列には無限数列と有限数列があります. 数列は以下のような自然数の集合を定義域にもつ写像(関数)のことです.
無限数列:　$a:N→\mathbb R; n\mapsto a_n$　
有限数列:　$a:{\lbrace 1,2,...,n \rbrace}\rightarrow \mathbb R $
文字列を表す点列:${\lbrace 1,2,...,n \rbrace}\rightarrow \mathcal S$ （$\mathcal S$は文字の集合）
型のある言語だとイテレーターと点列の概念は対応します.

イテレーターにも鎖の構造が無限のものと有限のものがあります.
無限 : オブジェクト1 - オブジェクト2 - オブジェクト3　- ... - オブジェクトn - ...
有限 : オブジェクト1 - オブジェクト2 - オブジェクト3　- ... - オブジェクトn

# 無限のイテレーターの例
import itertools

cycler = itertools.cycle("ABCD")
for i, val in enumerate(cycler):
    print(i, val)

# 0 A
# 1 B
# 2 C
# 3 D
# 4 A
# 5 B
# 6 C
# 7 D
# 8 A
# ... と永遠に続く

リストと有限のイテレーターの違い ~その1~

有限のイテレーターはリストと全く同じように感じます.

• もっともわかりやすい違いはリストが要素に何度でもアクセスできるのに対し, イテレータは消費され,1度のみしか呼び出されない点です. 詳しくは「for文
  イテレーターでできている」の項で説明します.
• 重要な違いはリストが具体的なデータ構造で全要素をメモリに保持するのに対し, イテレータは必要に応じて要素を生成し,呼び出されたら要素を捨てる点です. 詳しくは遅延評価の項で説明します.

iter関数

イテレーターを作る最も簡単な方法がiter()関数を用いることです.　iter()関数はイテラブルなオブジェクト,たとえばリストやrange()オブジェクトなどに対してイテレーター(鎖の構造)を返す関数です.
iter()関数　｜【入力】 イテラブルなオブジェクト　【出力】 イテレーター

r=iter(range(4)) 
l=iter(["Alice","Bob","Camelon"])
s=iter("aiueo")

# イテレーターはイテラブルオブジェクトなのでfor文がつかえる
for i in r :
    print(i)

for i in range(4) : 
    print(i)
# 上の2つのコードは出力は等しい
    

この時点だと,イテレーターにする意味もわからないし,リストとの違いもわかりません.

next関数

next()関数は連なっている鎖を先頭の鎖(オブジェクト)を外して吐き出す関数です. 吐き出されたオブジェクトはイテレーターから破棄されて同じイテレーターからは二度とnext()関数では呼び出せません.

イテレーターA : オブジェクト1 - オブジェクト2 - オブジェクト3　- ... - オブジェクトn - ...

というイテレーターに対してnext(イテレーターA)とすると,先頭の鎖オブジェクト1を返して, イテレーターAの先頭の鎖オブジェクト1は切り離され,

イテレーターA :オブジェクト2 - オブジェクト3　- ... - オブジェクトn - ...

という構造になります.

l=iter(["Alice","Bob","Camelon"])   

print(next(l)) # 鎖l: "Alice"-"Bob"-"Camelon"
# Alice
print(next(l)) # 鎖l: "Bob"-"Camelon"
# Bob
print(next(l)) # 鎖l: "Camelon"
# Camelon 
print(next(l)) # 鎖l: 空
# Stop Iteration Errorとなる. 

有限のイテレーターの場合, 鎖がすべて吐き出されると空になります. 空っぽになったイテレーターにnext()関数を使うと, Stop Iteration Errorとなります.

イテレーターとイテラブルオブジェクトの違い ~その$2$~

range(5), リスト, 文字列はイテラブルオブジェクトであるが,イテレーターではないので,next()関数を使うことができない.

たとえば,リストに対してnext()関数を適用しようとすると,「リストはイテレーターでない」と怒られてしまいます.

l=["Alice","Bob","Camelon"]
next(l) 
# TypeError: 'list' object is not an iterator

ここまでの解説だとまだ全然イテレーターのありがたみがわかりません.リストをpopするのとイテレーターをnextするのと動作的には同じであると思ってしまうかもしれません. イテレーターはクラスと組み合わせたり,ジェネレーターを使ったときに威力を発揮します. あとでその例を出します.

for文はイテレーターでできている

Pythonのfor文は

1. イテラブルからiter()関数でイテレーターを作成する
2. 作成したイテレーターに対して無限ループでnext()関数を繰り返し呼び出す
3. Stop Iteration Errorを受け取ったらループを抜ける
   という仕組みで動いています

次のコードがどのように動いているかというと

for i in ["Alice","Bob","Camelon"] :
    print(i) # iに関する処理部分

イテラブルオブジェクト["Alice","Bob","Camelon"]を受け取ったらそれをiter関数でイテレーターに変えて, i=next()をループでくり返し行なう. イテレーターの中身がなくなり, Stop Iteration Errorを受け取ったらループを抜けるということです. 次のコードと等価です.

iterable=iter(["Alice","Bob","Camelon"]) 
while True :
    try :
        i=next(iterable)
        print(i) # iに関する処理部分
    except StopIteration:
        break # iterableが空になったらループからぬける

よって,次のようにイテレーターに使うとStopIterationエラーとなります. しかし, リストの場合はエラーになりません.

l=["Alice","Bob","Camelon"] # リスト
il=iter(l) # イテレーター

# リストをイテレーターに変えてそのイテレーターに対して反復するからもとのリストは影響うけない
for i in l : 
    print(i)
for i in l :
    print(i)
# エラーならない

for i in il : 
    print(i)
# この時点ilは空のイテレーターとなる
for i in il :
    print(i)
# 空のイテレーターに対してnext()関数を適用しようとしているからStop Iteration Errorになる. 

イテレーターとイテラブルオブジェクトの違い ~その $3$ ~

イテラブルであるには for文の定義をみればわかる通り 　iter()関数でイテレーターが作成可能でないといけません. しかし, イテレーターはiter()関数によりイテラブルオブジェクトから作成しています.

現状だとイテラブルオブジェクトとイテレーターの関係は「にわとりと卵の関係」です. 次の項でクラスによって,独自のイテラブルオブジェクトを定義する方法を紹介します.

クラスでイテラブルなオブジェクトを定義する

クラスの特殊メソッド__iter__,__next__を用いて独自のイテレーターを作成することができます. これらの機能を用いてフィボナッチ数列のクラスとアルファベットのクラスを実装する例を挙げます.

あるクラスから生成されたオブジェクトoに対して

• iter(o)はoの特殊メソッド__iter__を実行する.
• next(o)はoの特殊メソッド__next__を実行する.

要はiter(o)はo.__iter__()と等価でnext(o)はo.__next__()ということです.

Fibonacci()イテレーターのクラスの作成

フィボナッチ数列${\lbrace a_n \rbrace}_{n=1,2,...}$のイテレーターを生成するクラスをつくります. フィボナッチ数列とは

$a_{n+2}=a_{n+1}+a_{n}, \ n=0,1,2,...$

を満たす3項間漸化式で定義される無限数列です. これを無限のイテレーターで表すことができます. 漸化式の初期条件$a_0,a_1$を与えたときに, フィボナッチ数列に対応する無限のイテレーターを返してくれるクラスを実装します.

$a_0=1,a_1=1$
を渡したとき生成されるイテレーターの鎖のイメージは
$1-1-2-3-5-8-13-21-34-...$
という無限の鎖のイメージです.

class Fibonacci:
    def __init__(self, first=1, second=1):
        self.a, self.b = first, second  # 初期条件の2つの数を引数から設定

    def __iter__(self):
        return self

    def __next__(self):
        current = self.a
        self.a, self.b = self.b, self.a + self.b
        return current

fib=Fibonacchi(1,1)
next(fib)
# 1
next(fib)
# 1
next(fib)
# 2
next(fib)
# 3

# 50以下のフィボナッチ数をプリント
for i in Fibonacchi(1,1) :
    print(i)  
    if i<50 : break

print(list(fib)) #永遠にプリントできない
        

イテレーターの一度, 消費された値が破棄されるという構造上,

fib=Fibonacchi(1,1)
next(fib)
# 1
next(fib)
# 1
next(fib)
# 2
next(fib)
# 3

# とした後に
for i in fib :
    print(i) 
# 5,8,13, ...となる

となってしまったり

fib=Fibonacchi(1,1)

for i in fib :
    print(i) 
    if i<50 : break

for i in fib :
    print(i) 
    if i<10 : break
# 1 1 2 3 5 8とプリントされてほしいが,
# 既にこの値をイテレーターが吐き出してしまっているためプリントされない

となってしまうという問題点があります.この問題を解決したいです.

Fibonacci()クラスの作成

先の項での問題を解決するには, Fibonacci()クラスとは別のFibonacciIterator()イテレータのクラスを別に定義して、そのクラスから作成されるオブジェクトFibonacci()クラスの__iter__メソッドから返すようにすればよいです. さっぱり, わからない方は実装を見た方がよいかもしれません.

Fibonacci()クラスは単にイテラブルなオブジェクトを返すクラスとして機能して, イテレーションのロジックはFibonacciIterator()クラスに委ねるということです.

class Fibonacci:
    def __init__(self, first=0, second=1):
        self.first = first
        self.second = second

    def __iter__(self):
        return FibonacciIterator(self.first, self.second)

class FibonacciIterator:
    def __init__(self, first, second):
        self.a, self.b = first, second

    def __iter__(self):
        return self

    def __next__(self):
        current = self.a
        self.a, self.b = self.b, self.a + self.b
        return current        

fib=Fibonacchi(1,1)

for i in fib :
    print(i) 
    if i<10 : break

for i in fib :
    print(i) 
    if i<10 : break

next(fib)
# TypeError: 'Fibonacci' object is not an iterator

このように実装するとfor文を回すたびにfibというイテラブルオブジェクトからiter()関数でイテレーターを作成されて作成されたイテレーターを使ってfor文を回すから, このような書き方ができます. このプログラムをみてはじめて, イテレーターとイテラブルオブジェクトと違いがわかります.

イテレーターとイテラブルオブジェクトの違い　~その$4$~

イテレーターとイテラブルオブジェクトの本当の定義は

• イテラブルオブジェクトとは__iter__関数が実装されているクラスから生まれたオブジェクト
• イテレーターとは__iter__関数と__next__関数が実装されているクラスから生まれたオブジェクト

この定義によるとFibonachi()クラスから生成されるオブジェクトはイテラブルオブジェクトですがイテレーターではありません. FibonachiIterator()クラスから生成されるオブジェクトはイテレーターです.

Alphabet()イテレーターのクラスの作成

class Alphabet:
    def __init__(self, start, end):
        self.start = ord(start)  # 開始文字のUnicodeコードポイント
        self.end = ord(end)  # 終了文字のUnicodeコードポイント
        self.current = self.start - 1  # 現在位置を開始文字のひとつ前に設定

    def __iter__(self):
        return self

    def __next__(self):
        if self.current < self.end:
            self.current += 1  # 現在位置を次の文字に更新
            return chr(self.current)  # 現在位置の文字を返す
        else:
            raise StopIteration  # 終了文字を超えたらイテレーションを終了

# 使用例
for char in Alphabet('a', 'e'):
    print(char,end+"")
# abcde

フィボナッチ数列と違い, 有限の長さをもつイテレーターです.

組み込み関数range(),zip(),enumrate()を書いてみる

イテラブルオブジェクトについて理解するため,Pythonに組み込まれいるrange()クラスとzip()クラス,enumrate()クラスを理解するために, これらと同じような挙動をもつクラスを実装しましょう.

range()クラス

range()クラスから作成されるrange()オブジェクトはイテラブルオブジェクトです. range()クラスと似たふるまいをするMyRange()クラスを実装します.

class MyRange:
    def __init__(self, start, stop=None, step=1):
        if stop is None:
            self.start = 0
            self.stop = start
        else:
            self.start = start
            self.stop = stop
        self.step = step

    def __iter__(self):
        return MyRangeIterator(self.start, self.stop, self.step)

class MyRangeIterator:
    def __init__(self, start, stop, step):
        self.current = start
        self.stop = stop
        self.step = step

    def __iter__(self):
        return self

    def __next__(self):
        if (self.step > 0 and self.current >= self.stop) or (self.step < 0 and self.current <= self.stop):
            raise StopIteration
        else:
            current = self.current
            self.current += self.step
            return current

# MyRangeの使用例
next(MyRange(3)) 
# TypeError MyRange()クラスの生成するオブジェクトそのものはイテレーターではない

for num in MyRange(5, 1, -1):
    print(num, end=" ")
# 5 4 3 2

list(MyRange(3))
# [0,1,2]

enumrate()クラス

enumerate()はイテラブルなオブジェクトを受け取って, 受け取ったイテラブルオブジェクトの中身と番号をペアにしたタプルを(番号, オブジェクト)返すようなイテレーターを返すクラスです.

class MyEnumerate:
    def __init__(self, iterable, start=0):
        self.iterator = iter(iterable)  # イテラブルオブジェクトのイテレータを取得
        self.index = start

    def __iter__(self):
        return self

    def __next__(self):
        # イテラブルオブジェクトの次の要素を取得
        # StopIteration例外が発生した場合は、そのまま例外を呼び出し元に伝播させる
        element = next(self.iterator)
        result = (self.index, element)
        self.index += 1
        return result

st="apple"
for i,s in MyEnumerate(st) :
    print(str(i)+s)

# 0 a
# 1 p
# 2 p
# 3 l
# 4 e

タプル(a,b)とは集合論的には順序対$(a,b)$です. 順序対とは
$(a,b)=(c,d)\Leftrightarrow a=b\mbox{かつ}c=d$
を満たすものです

Pythonでは a,b=c,dやa,b=(c,d)とタプルを代入できる. for文の意味を考えるとMyEnumerate(st)から受け取ったイテレーターのnext()関数が呼び出されてそれがi,sに代入されている.

zip()クラス

zip()はイテラブルなオブジェクトを複数受け取って,それぞれ受け取ったイテラブルオブジェクトの中身をペアにしたタプルを返すようなイテレーターを返すクラスだ.

class MyZip:
    def __init__(self, *iterables):　# 可変のイテレーターを受け取れるようにする
        # 引数で受け取ったイテラブルオブジェクトのイテレータをリストに格納
        self.iterators = [iter(it) for it in iterables]

    def __iter__(self):
        return self

    def __next__(self):
        # 各イテレータから次の要素を取得してタプルにまとめる
        # いずれかのイテレータが要素を返さない場合（StopIteration例外を発生させる場合）、
        # MyZipのイテレーションも終了する
        zipped = tuple(next(it) for it in self.iterators)
        if not zipped:
            raise StopIteration
        return zipped

# 使用例
iterable1 = [1, 2, 3]
iterable2 = ['a', 'b', 'c']
iterable3 = [0.1, 0.2, 0.3]

for item in MyZip(iterable1, iterable2, iterable3):
    print(item)

ジェネレーター

ジェネレーターはイテレーターを楽に生成するための仕組みです. 独自のイテレーターを作成する際に毎回, クラスを作っていては大変です.　ジェネレーターを使うと楽にイテレーターを非常に簡単にイテレーターをつくることができます.

• iter()関数で作成　... イテラブルオブジェクトからイテレーターをつくる　　　
• クラスで直接的に定義 ... 特殊メソッドで__iter__(), __next__(0を定義する.
• ジェネレーター関数で定義 ... defとyield文で定義
• ジェネレーター式で定義　 ... ジェネレーターの内包表記で定義

4つのうち2つは学びました. このセクションではジェネレーター関数とジェネレーター式を学びましょう.

ジェネレーター関数

yield文を使ったジェネレーター関数

ジェネレータ関数は呼び出されても中身の関数のコードは呼び出された時点では実行されません. ジェネレーター関数が呼びだれたときに返すものはイテレーター（ジェネレータオブジェクト）です. 　ジェネレーター関数の中のコードが実行されるのは返された,イテレータオブジェクトについてnext()関数を呼び出されたときで, ジェネレータ関数は次のyieldまで実行されて,その値を返します.

この説明だとよくわからないとおもいますので,ジェネレーターによるフィボナッチイテレーターの実装をクラスによる実装と見比べてください.

先の例で定義したフィボナッチ数列のイテレーターのクラスとほぼ挙動が同じものがジェネレーターを使うと次のように簡単に定義できます.

def fibonacciIterator(first=1, second=1):
    a, b = first, second
    while True:
        yield a
        a, b = b, a + b

fib=fibonacciIterator(1,1)
next(fib)
# 1
next(fib)
# 1
        

ジェネレーター関数の中身の処理はnext()関数が呼び出されると実行されて, yieldで中断され, 再びnext()関数が呼び出されると途中から実行されます. また, Alphabet()イテレーターのクラスと同等の機能をジェネレーターで実装できる.

def alphabet(start, end):
    current = ord(start)  # 開始文字のUnicodeコードポイント
    end = ord(end)  # 終了文字のUnicodeコードポイント
    while current <= end:
        yield chr(current)  # 現在の文字を返す
        current += 1  # 次の文字へ

# 使用例
for char in alphabet('a','e'):
    print(char)

Alphabet()イテレーターのクラスとの重要な違いはStopIterationを明示的に書いていない点ですが, next()関数が呼び出されて処理が進んだ際にブロックから抜けるときがくると思います. その際にStopIterationが起こります.

ジェネレーター関数内のreturn文

return文とyield文を混在させても問題ありません.returnとはブロックから抜けることを意味します. ジェネレーター関数のブロックから抜けるとStopIterationが起こるので, return文をかくことでただちにStopIterationを起こすことができます.

returnに返す値はStopIterationという例外クラスのvalue属性に値が渡される.

def gene():
    yield "Hello"
    return "World"

gen = gene()

try:
    next(gen)  # "Hello" を返す
    next(gen)  # ここで StopIteration が発生する
except StopIteration as e:
    print("Return value:", e.value)  # "World" を出力

ジェネレーターをくっつけるyield from文

yield from　[Iterable Object]はイテラブルオブジェクトをジェネレーターの中に組み込むことができる機能です. 2つ以上のイテタブルオブジェクトをつなげてたり, 分岐させてりできる機能だと考えるとわかりやすいかもしれません.

第$n$項までフィボナッチ数列のイテレーターを返すジェネレーターを次のように再帰的な書き方ができます.

def fibonacci(n, first=1, second=1):
    if n == 0:
        return
    yield first
    yield from fibonacci(n-1, second, first+second)

# 使用例
N = 10  # 生成したいフィボナッチ数列の項数
for num in fibonacci(N):
    print(num)

ジェネレーター式

内包表記でイテレーターを作成することもできます.最も簡易的なイテレーターの作成方法です.基本的にはイテラブルオブジェクトをいじって別のイテラブルオブジェクトをつくります.. ジェネレーター関数よりさらに簡単に定義できます.

# n以上の自然数を返すジェネレーター
def natural(n) :
    while True :
        yield n
        n+=1
          
sq=(n**2 for n in natural(0))
# 0 1 4 9 16 25 ...

li=(n*3+1 for n in natural(0))
li=(n for n in natural(0) if x%3==1)
# 1 4 7 10 13 ...

lo=(n if x%3==1 else 0 for n in natural(0))
# 0 1 0 0 4 0 0 7 0 0 10 0 0 13 ...

n=10
combinations=((x,y,n-x-y) for x in range(n+1) for y in range(n-x+1))
# (0,0,10),(0,1,9),(0,2,8)...,(0,10,0),(1,0,9),(1,1,8),(1,2,7),...,(10,0,0)

内包表記は数学の集合の内包表記に近い.
平方数の集合$S=\lbrace n^2 |n\in \mathbb N \rbrace$
$L=\lbrace n |n\in \mathbb N, n≡1({\rm mod \ 3}) \rbrace=\lbrace 3n+1 |n\in \mathbb N \rbrace$

遅延評価

最後に遅延評価の観点から, リストとイテレーターの違いを説明します. 遅延評価は,値が必要になるまでその計算を遅らせる戦略です.

$10000$円札, $5000$円札,$1000$円札が合わせて$N$枚あるとき, 金額が$Y$円となる組み合わせを1つ見つけて, 存在しない場合はそれを判定するプログラム問題出典を作成します.それを,リストとジェネレーター式を使った実装を見比べてみましょう.

# リストを使った実装
N,Y=2000,20000000

combinations = [(i,j-i-1,n+1-j) for j in range(n+2) for i in range(j)]
condition = lambda tup: 10000 * tup[0] + 5000 * tup[1] + 1000 * tup[2] == y #yは定数
solutions = list(filter(condition, combibations))

print(solutions[0] if solutions else (-1, -1, -1))

# 実行時間: 420 ms
# メモリ	297 MB

# ジェネレーター式を使った実装
N,Y=2000,20000000

combinations = ((i,j-i-1,n+1-j) for j in range(n+2) for i in range(j))
condition = lambda tup: 10000 * tup[0] + 5000 * tup[1] + 1000 * tup[2] == y #yは定数
solutions =filter(condition, combibations)

print(next(solutions,(-1,-1,-1)))

# 実行時間: 367 ms
# メモリ	12 MB

リストの内包表記を使った実装では

• combinations リスト内包表記：全ての可能な組み合わせを一度に生成し, メモリに保持しています.
• list(filter(...)): 全ての要素に対して条件をチェックし,条件を満たす全ての要素を新しいリストに格納します.

ジェネレーター式を使った実装では

• combinations ジェネレータ式：全ての可能な組み合わせを一度に生成するのではなく、必要に応じて1つずつ生成します.
• filter() 関数：ジェネレータに対して適用されるため、全ての要素を処理する前に条件を満たす要素が見つかれば処理を停止します.
• next() 関数：最初に条件を満たす要素のみを取得し,それ以上の処理は行いません.

このような「式の評価を値が必要になるまで遅らせる戦略」, 遅延評価を使うと,不要な計算を回避し, メモリー使用効率を改善できる可能性があります. 今回の例だとメモリー使用量が25倍程度差が出ました.