Python のイテレータってなに?








記事を移転しました。今後ともどうぞ、よろしくお願いいたします。


https://python.ms/iterator/









以下、旧版




f:id:domodomodomo:20171126155731j:plain
図. イテレータのイメージ



イテレータとは、list, tuple, set などの集合を表現するオブジェクトから
iter 関数で生成された集合のコピーみたいなものだと考えてください。

イテレータから next 関数で要素を取り出すことができ
取り出す操作は for 文で自動的に繰り返す(iterate する)ことができます。
















f:id:domodomodomo:20180113154538j:plain


何を言ってるのか、さっぱりだと思います。
まず、理解するとできるようになることを、先に説明したいと思います。















1. イテレータを理解すると何ができるようになるの?

答え: 自分で定義したクラスのオブジェクトを...

1. for 文の in で使えるようになったり
2. 集合を引数に取る関数で使えるようになったりします。


◯ 出来ること1: for 文の in で使えるようになる。

例えばチームを表現するクラスがあったとします。

class Team(object):
    def __init__(self):
        self.member_list = []

member = Team(['川島 永嗣', '香川 真司', '長谷部 誠 '])



このように list を参照して for 文を回していたのが

>>> for member in samurai_brue.member_list:
...     print(member)
川島 永嗣
香川 真司
長谷部 誠 
>>>



こんな風に in の中に自分が定義したクラスのオブジェクトが書けるようになります。

>>> for member in samurai_brue:
...     print(member)
川島 永嗣
香川 真司
長谷部 誠 
>>>



上記のように for 文の in に書き込めるできるオブジェクトを イテラブル と言います。





◯ 出来ること2: 集合を引数に取る関数で使えるようになる。

set 関数を用いて差集合、和集合を取ったり , max 関数を用いて集合の最大値を取ったりすることもできるようになったりもします。

こんな風に書いていたのを

>>> set(team_a.member_list) - set(team_b.member_list) 
{'長谷部 誠'}
>>>



こんな風に書き換えたりもできたりします。

>>> set(team_a) - set(team_b) 
{'長谷部 誠'}
>>>



他にも iterable を引数に取る関数が使えるようになります。 公式マニュアルの組み込み関数のページ で ctrl+F で iterable で検索するといくつか引っかかってきます。例えば all, any, dict, enumerate, min, sorted, sum, tuple, zip 関数で使えます。





◯ どうやってやるの?

実装の仕方は、とっても簡単で、次のような iterator を返す __iter__ メソッドを追加するだけでできるようになります。

    # これを追加するだけ。
    def __iter__(self):
        return iter(self.member_list)



この __iter__ メソッドは for 文や set などの iterable を引数に取る関数で使われたときに呼び出されます。呼び出されると iter 関数がイテレータというリストのコピーのようなものを作り、for 文や set などの iterable を引数に取る関数に作ったイテレータを渡し処理を実行します。

全体のコードは、こちら。対話モード >>> にコピペして、動くか確認してみてください。

# 実装の仕方
class Team(object):
    def __init__(self):
        self.member_list = []
    
    # これを追加するだけ。
    def __iter__(self):
        return iter(self.member_list)


#
# 出来ること1: for 文の in で使えるようになる。
#
samurai_brue = Team()
samurai_brue.member_list.extend(
    ['川島 永嗣', '香川 真司', '長谷部 誠'])

for member in samurai_brue:
    print(member)
# 川島 永嗣
# 香川 真司
# 長谷部 誠


#
# 出来ること2: 集合を引数に取る関数で使えるようになる。
#
team_a = Team()
team_a.member_list.extend(
    ['川島 永嗣', '香川 真司', '長谷部 誠'])
team_b = Team()
team_b.member_list.extend(
    ['川島 永嗣', '香川 真司', '原口 元気'])

set(team_a) - set(team_b)
# {'長谷部 誠'}



◯ まとめ

イテレータを理解するとできるようになることを、ごく手短に紹介させていただきました。イテレータは for 文と、とても深く関わっているということだけ、押さえておいていただけると幸いです。

このようにして for 文はイテレータを操作しているので、もしイテレータを理解すると for 文の動作の中身を、より深く理解することができます。実はこの記事も、「for 文を理解する5講座」という全5回の連載の4回目の記事になります。

1〜3回を読んでいなくても理解できるように頑張って書いては見ましたが... 2、3回目は、ざっくり眺めていただいた方が、読みやすいかなと思います。いきなりここから読み出しても、抽象的過ぎて「だから... なに?」みたいな気分になる恐れがあります。

各回の目的は、1回目は for 文の導入、2、3回目はとりあえず実際にイテレータを触ってみること、そしてこの4回目は、イテレータという概念を理解することです。


f:id:domodomodomo:20181103193404j:plain
Python の for 文ってなに? - いっきに Python に詳しくなるサイト

















ここから先は、
もし動作の詳細に興味がわいたら、読み進めて見てください。





このあとは、次のような具合で説明を進めていきます。

2 ~ 5 章...実際にイテレータを触ってみる。
6 ~ 9 章...4つのイテレータを自作する。
10 章...イテレータとリストを区別する。
11 章...イテレータとコンテナを区別する。
12 ~ 13章...2つの疑問について考える。



2. Pythonイテレータの動作

イテレータの動作を図で見てみる。

動作を図示するとこんな感じです。
ざっくり、てきとーに眺めてください。
f:id:domodomodomo:20171126155706j:plain

イテレータは、list, tuple, set などの集合を表現するオブジェクトから
iter 関数で生成された集合のコピーみたいなものだと考えてください。
f:id:domodomodomo:20171126155710j:plain

イテレータから1つ1つ要素を取り出すには
next 関数を使います。
f:id:domodomodomo:20171126155713j:plain
f:id:domodomodomo:20171126155716j:plain
f:id:domodomodomo:20171126155719j:plain
f:id:domodomodomo:20171126155722j:plain
f:id:domodomodomo:20171126155726j:plain

使い終わると
イテレータは空っぽになりますが
リストはそのままです。
f:id:domodomodomo:20171126183233j:plain


全体像は、こんな感じになります。
f:id:domodomodomo:20171126155731j:plain


イテレータの動作をコードで見てみる。

イテレータは、list, tuple, set などの集合を表現するオブジェクトから
iter 関数で生成された集合のコピーみたいなものだと考えてください。

# list, tuple, set などの集合を表現する
# オブジェクトを一般に container 総称します。
container = [1, 2, 3, 4]

iterator = iter(container)
iterator
# <list_iterator object at 0x10db73f60>

# iterator は集合をコピーしたものなので
# container と iterator の中身は同じ
list(iterator)
# [1, 2, 3, 4]



1. next 関数は、イテレータから1つ1つ要素を取り出すことができます。
2. next 関数は、イテレータが空ならば例外 StopIteration を送出します。

container = [1, 2, 3, 4]

iterator = iter(container)
next(iterator)
# 1

next(iterator)
# 2

next(iterator)
# 3

next(iterator)
# 4

next(iterator)
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# StopIteration

◯ どのオブジェクトなら iter 関数を使って iterator を生成できるの?

for ~ in ... の in ... に入れることができるオブジェクトです。このようなオブジェクトは、for 文の中で繰り返すことができる (iterate できる) という意味で iterable なオブジェクトと呼ばれます。

3. for 文と一体何の関係があるの?

答え: for 文の中で next(iterator) が繰り返し呼び出されています。

next 関数を4回も手打ちさせるコードを見せられると、こんなの一体どこで使うんや.. とか、なんていうキチガイフレンズなのかな.. みたいな気分になってしまうかも知れません。

ここでは 4, 5 で手書きで実行した next 関数を空になるまで実行するように while 文に書き換え、それをさらに for 文に書き換えていきます。

Step1. while 文で書き換え

4, 5 では iterator が空になるまで手書きで next 関数をひたすら実行しました。あまり iterate 繰り返している感じがしないので while 文で書き換えて見ましょう。

container = [1, 2, 3, 4]

iterator = iter(container)
while True:
    next(iterator)
# 1
# 2
# 3
# 4
# Traceback (most recent call last):
#   File "<stdin>", line 2, in <module>
# StopIteration

Step2. 例外 StopIteration を捕まえる

都度、例外を投げられては実際の運用で使い物になりません。そこで、例外を捕まえます。

container = [1, 2, 3, 4]

iterator = iter(container)
while True:
    try:
        next(iterator)
    except StopIteration:
        break
# 1
# 2
# 3
# 4

Step3. next の返り値を変数 element に代入させます。

iterator の返り値を再利用しやすくなりました。

container = [1, 2, 3, 4]

iterator = iter(container)
while True:
    try:
        element = next(iterator)
    except StopIteration:
        break
    element
# 1
# 2
# 3
# 4

Step4. for 文に書き換え

しかし Step3 のコードは、非常に長く煩雑です。何とかならないでしょうか。実は Python ではこのコードを、for 文を使って次のように書き換えることができます。

container = [1, 2, 3, 4]

for element in container:
    # element = next(iterator) 
    # が繰り返されている(iterate されている)。
    element
# 1
# 2
# 3
# 4

for 文は while 文よりも、簡潔に表現できます。for 文の中で element = next(iterator) という処理が、文字通り繰り返されている(iterate されていいる)ことがわかります。

一応 for 文と while 文の速度比較をして見たのですが、だいたいの場合、for 文の方が速いかなと感じています。
4. for 文と while 文の速度の比較 - Python を高速化したい

これを見ていると、もし next 関数と iterator 関数を実装することができれば、自分で作ったクラスでも for 文の in の中で使えそうですね。


4. next 関数, iter 関数を実装したい

実は next 関数と iter 関数の動作を実装できます。何故なら iter 関数も next 関数も、iterable の __iter__ メソッド, __next__ メソッドをそれぞれ呼び出しているだけだからです。

◯ __iter__ メソッド

# list, tuple, set などの集合を表現する
# オブジェクトを一般に container 総称します。
container = [1, 2, 3, 4]

# iterator = iter(container)
iterator = container.__iter__()
iterator
# <list_iterator object at 0x10db73f60>

list(iterator)
# [1, 2, 3, 4]

◯ __next__ メソッド

container = [1, 2, 3, 4]


iterator = iter(container)

# next(iterator)
iterator.__next__()
# 1

# next(iterator)
iterator.__next__()
# 2

# next(iterator)
iterator.__next__()
# 3

# next(iterator)
iterator.__next__()
# 4

# next(iterator)
iterator.__next__()
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# StopIteration

疑問: なんでメソッドと関数があるの?

答え: 使い分けています。

ユーザが自分で iterator を定義したいときは __iter__, __next__ メソッドから定義します。実際に使うときは iter, next 関数から呼び出します。

__iter__, __next__ メソッドと iter, next 関数が取る引数の違いに注目してください。iter, next 関数は、__iter__, __next__ メソッドと異なり optional な引数を取ります。

iter, next 関数は、単純に __iter__, __next__ メソッドを実行するだけでなく optional な引数を取り、それに基づいて異なる処理をします。optional な引数に基づく iterator に共通する処理は、組み込み関数が担ってくれるというわけです。

ちなみに Python では、このように __do__ メソッドを do 関数で呼び出すような書き方を定めてるものとして、他にも len, bool があります。リンク先でもう少し詳しい解説をしています。
Python の len はなんでメソッドではなく関数なの?

この後は、__iter__, __next__ メソッドを実装して iterable な container と iterator を自作していくことになります。

5. container と iterator の関係

いままで触ってきた内容を元に、実装したいクラス、メソッドを図に落とすと次のようになります。
f:id:domodomodomo:20171126131131j:plain

container と iterator の関係

◯ 実装の方針

この図を見ると自分が作った container を for 文の in にいれたい場合は、container に __iter__ メソッドを追加して、iterator には __next__ メソッドを実装さえしてしまえば良さそうですね。

ここまでは iterator を触って大体の動作を把握しました。ここから先は空集合、リスト、木の3つのデータ構造についてそれぞれ iterator を自作して理解を深めていきたいと思います。


6 章...iterator を自作する1 空集合
7 章...iterator を自作する2 リスト(コピー)
8 章...iterator を自作する3 リスト
9 章...iterator を自作する4 木















6. iterator を自作する1 空集合

やっと自作するところまでたどり着きました。空集合とか、気取って書いて見ましたが、何も要素を持たない iterator と言うことです。

◯ 問題

このクラスを

class Container(object):
     pass



for 文の in に使えるようにします(iterable にします)。最も小さい iterable を実装していきます。

>>> # 何も起こらない。とにかくエラーが発生しないことを目標に。
>>> for element in Container():
...     print(element)
>>> 

◯ 方針

公式のマニュアルを読みながら、実装を進めて見たいと思います。
公式マニュアルと仲良くなることも、このページの目的です。

Python はコンテナでの反復処理の概念をサポートしています。この概念は 2 つの別々のメソッドを使って実装されています; これらのメソッドを使ってユーザ定義のクラスで反復を行えるようにできます。
4.5. イテレータ型

Step1. container オブジェクト

まず iterate させたい値を持つ container オブジェクトに対して iterator オブジェクトを返す __iter__ メソッドを定義する。


コンテナオブジェクトに反復処理をサポートさせるためには、
以下のメソッドを定義しなければなりません。

container.__iter__()
イテレータオブジェクトを返します。

Step2. iterator オブジェクト

次に iterator オブジェクトには、次の2つのメソッドを定義する。イテレータオブジェクト自身を返す __iter__ メソッド と、次の要素を返す __next__ メソッド。


イテレータオブジェクト自体は
以下の 2 つのメソッドをサポートする必要があります。

iterator.__iter__()
イテレータオブジェクト自体を返します。

iterator.__next__()
コンテナの次のアイテムを返します。もしそれ以上アイテムが無ければ StopIteration 例外を送出します。

Step3. 図を更新

イテレータオブジェクト自体を返す iterator.__iter__() と言うのがメソッドが新しく登場してきました。ちょっと、図を更新してみます。
f:id:domodomodomo:20171126131853j:plain

container と iterator の関係2

この iterator.__iter__() は何者かと言うと、コンテナだけではなくイテレータそのものも for 文の in の中で使えるようにするためにあります。イテレータであるかどうかを判別するために利用しています。

しかし iterator.__next__() があれば、イテレータだと判断できるのではないでしょうか?なぜ、わざわざ iterator.__iter__() を実装しなければならないのでしょうか?

それについては最後の方で紹介いたします。
なんで iterator にも自分自身を返すメソッド __iter__ を実装するの?

◯ 解答例(実装例)

class Container(object):
    pass
    
    def __iter__(self):
          return Iterator()


class Iterator(object):
    def __iter__(self):
          return self
    
    # 要素はないので呼び出された
    # 瞬間に StopIteration を投げる。
    def __next__(self):
         raise StopIteration


if __name__ == '__main__':
    for element in Container():
        print(element)

7. iterator を自作する2 リスト

◯ 問題

list を属性に持つクラスを iterable にして for 文で使えるようにしましょう。ただし、理解のために iter 関数を使わずに自分でイテレータクラス ListIterator を実装してみたいと思います。

#  このままでは for 文で使えない,  iterable でない
class Container(object):
    def __init__(self, list_):
        self.list = list_


for 文内で iterator が実行されると
文字列を繰り返す(iterate)するように実装して見ましょう。

>>> container = Container(
... ['Yaruo', 'Yaranaio', 'Yarumi'])
>>> 
>>> for element in container:
...     print(element)
... 
Yarumi
Yaranaio
Yaruo
>>>



◯ 方針

リストのコピーを使って実装して見ます。

◯ 解答例(実装例)

実装するとこんな感じになります。

class Container(object):
    def __init__(self, list_):
        self.list = list_
    
    # container.__iter__()
    def __iter__(self):
        # iter 関数を使わずに
        # return iter(self.list)
        return ListIterator(self.list)


class ListIterator(object):
    def __init__(self, list_):
        self.list = list_.copy()
    
    # iterator.__iter__()
    def __iter__(self):
        return self
    
    # iterator.__next__()
    def __next__(self):
        if self.list:
            return self.list.pop()
        # シーケンスが空であれば終了
        else:
            raise StopIteration

if __name__ == "__main__":
    container = Container(['Yaruo', 'Yaranaio', 'Yarumi'])
    for element in container:
        print(element)

8. iterator を自作する3 リスト(コピーじゃない)

◯ コピーで実装してしまうことの問題点

メモリを消費するから。copy を実行してしまうと、その分だけメモリが増加してしまいます。しかし、例えばリストのインデックスだけ保存しておくようにしておけば、そのような事態を避けることができます。

◯ list_iterator クラス

本当のことを言えば、イテレータは、コピーではありません。

>>> iter([1, 2, 3])
<list_iterator object at 0x103ec02b0>
>>> 



list のイテレータである list_iterator クラスもリストのコピーでは、ありません。そのため list を空にすると list_iterator も空になってしまいます。

lst = [1, 2, 3]
iterator = iter(lst)

# lst を空にすると
lst.pop()
lst.pop()
lst.pop()
lst.pop()

# iterator も空になる
list(iterator)
>>> lst = [1, 2, 3]
>>> iterator = iter(lst)
>>> 
>>> # lst を空にすると
>>> lst.pop()
3
>>> lst.pop()
2
>>> lst.pop()
1
>>> lst.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list
>>> 
>>> # iterator も空になる
>>> list(iterator)
[]
>>> 

◯ 問題

list を属性に持つクラスを iterable にして for 文で使えるようにしましょう。ただし、理解のためにリストのコピーを使わずに、list_iterator クラスと同じ動作をするイテレータクラス ListIterator を自分で実装してみたいと思います。

#  このままでは for 文で使えない,  iterable でない
class Container(object):
    def __init__(self, list_):
        self.list = list_

◯ 方針

リストのインデックスを使って、イテレータを実装します。

◯ 解答(実装例)

class Container(object):
    def __init__(self, list_):
        self.list = list_
    
    # container.__iter__()
    def __iter__(self):
        # return iter(self.list)
        return ListIterator(self.list)


class ListIterator(object):
    def __init__(self, list_):
        self.list = list_
        self.index = 0
    
    def __iter__(self):
        return self
    
    def __next__(self):
        if self.index < len(self.list):
            element = self.list[self.index]
            self.index += 1
            return element
        else:
            raise StopIteration

if __name__ == "__main__":
    container = Container(['Yaruo', 'Yaranaio', 'Yarumi'])
    for element in container:
        print(element)




◯ 問題 その2

リストを逆順するイテレータを実装してください。

class Reverse:
    def __init__(self, data):
        self.data = data
        self.index = len(data)

    def __iter__(self):
        return self

    def __next__(self):
        ...  # ここにコードを書き込んで見てください。

if __name__ == "__main__":
    container = Reverse(['Yaruo', 'Yaranaio', 'Yarumi'])
    for element in container:
        print(element)

# Yarumi
# Yaranaio
# Yaruo


◯ 回答 その2

実は Python の公式ドキュメントのチュートリアルから引っ張ってきました。シーケンスを逆順する組み込み型 reversed と同じ動作をする Reverse と言うイテレータを、実装、紹介しています。
9.8. イテレータ - Python チュートリアル


◯ CPython の list_iterator の実装

こんな車輪の再発明みたいなコード、どこで使うんや。と思われると思います。実は、このようにしてインデックスを参照するやり方は CPython の list_iterator クラスと同じ実装になります。

ここで、ほんの少しだけ CPython の実装をのぞいて見たいと思います。リストのインデックスを更新してるんだなってことだけを何となく眺めてもらえると嬉しいです。

もしわからなければ、キチガイが何かのたまいてるなという暖かい目で、読み流してください。 でも、もし「何だか Python を C に書き直してるだけやん」と感じて、CPython の入り口のきっかけになれば幸いです。

// class list_iterator(object):
typedef struct {
    PyObject_HEAD
    // self.index
    Py_ssize_t it_index;
    // self.list
    PyListObject *it_seq;
} listiterobject;
// def __init__(self, list_):
static PyObject *
list_iter(PyObject *seq)
{
    listiterobject *it;

    if (!PyList_Check(seq)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    it = PyObject_GC_New(listiterobject, &PyListIter_Type);
    if (it == NULL)
        return NULL;
    
    // self.index = 0
    it->it_index = 0;
    Py_INCREF(seq);
    
    // self.list = list_
    it->it_seq = (PyListObject *)seq;
    _PyObject_GC_TRACK(it);
    return (PyObject *)it;
}
// def __next__(self):
static PyObject *
listiter_next(listiterobject *it)
{
    PyListObject *seq;
    PyObject *item;

    assert(it != NULL);
    seq = it->it_seq;
    if (seq == NULL)
        return NULL;
    assert(PyList_Check(seq));

    // if self.index < len(self.list):
    if (it->it_index < PyList_GET_SIZE(seq)) {
        // element = self.list[self.index]
        item = PyList_GET_ITEM(seq, it->it_index);
        // self.index += 1
        ++it->it_index;
        Py_INCREF(item);
        return item;
    }

    it->it_seq = NULL;
    Py_DECREF(seq);
    return NULL;
}


◯ ポイント

1. container.__iter__ は、イテレータを返すためだけに設計する。
2. iterator.__next__ は、集合の要素を取り出すためだけに設計する。


__iter__, __next__ メソッドでも、様々な機能を実装できます。しかし、基本的には上記の内容に絞って実装した方が、可読性の高いコードになるかなと思います。




取り出した要素を2倍にする処理を例にして、考えてみたいと思います。

方法 1. (推奨)for 文で取り出してから。

これが一番自然ですね。

for element in container:
    element = 2 * element
方法 2. map クラス
class Container(object):
    def __iter__(self):
        return map(lambda e: 2 * e, ListIterator(self.list))
方法 3. iterator.__next__ を書き換える。
class ListIterator(object):
    def __next__(self):
        if self.index < len(self.list):
            element = self.list[self.index]
            self.index += 1
            return 2 * element  # <- ここを書き換えました。
        else:
            raise StopIteration
方法 4. list 内包表記から iter 関数で呼び出す。

この書き方は、特にオススメしません。何故なら、このやり方では、一旦リストを生成しているため、そのリストの分だけメモリを必要としてしまうからです。

class Container(object):
    def __iter__(self):
        return iter([2 * e for e in ListIterator(self.list))
◯ まとめ

このことから、何が言えると思いますか?

それはイテレータが、要素を1つずつ取り出すために設計されているということです。取り出した要素を 2 倍にするには、どんな書き方だってできます。しかし、1度取り出して、それから処理をする。それが一番、わかりやすい書き方でした。

したがって、Python を習いたての人に「for 文とは何ですか?」と聞かれたら、「要素を1つずつ取り出してくれます。」と説明すれば、基本的にはいいのかなと思ったりもします。


9. iterator を自作する4 2分探索木

もともと for 文で回せるリストを属性にくっつけただけのオブジェクトを iterable にしても「だからなんやねん?」って感じです。list, tuple, dict, str などの最初から使える組み込み型は、ある意味、オブジェクトが直線に並んでいると考えることもできます。

直線で並んでいるものを、1つずつ繰り返し取り出すこと iterate することは、頭の中で考える時はイメージしやすいです。そこで今度は、すこし難易度を上げて直線で並んでいない型について、1つずつ繰り返し取り出すこと iterate することを考えて見ました。


9.1. 問題

2分探索木, Binary Search Tree を iterable にして見ます。

9.2. 2分探索木

2分探索木とは、「「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。Wkipedia」だ、そうです。


f:id:domodomodomo:20171119172218p:plain



2分探索木は、大小関係がわかるため、少ない計算量でソートして要素を取り出すことができます。言い換えると、ある値の次に大きな値が、どれかを探しやすいということです。

>>> # 上図と同じ構造の木を作る。
>>> bst = BinarySearchTree()
>>> for value in (8, 3, 1, 6, 10, 4, 7, 14, 13):
>>>     bst.insert(value)
>>> 
>>> # 木から1つ1つ要素を取り出す。
>>> for value in bst:
        print(value)
1
3
4
6
7
8
10
13
14
>>>
9.3. 回答

二分探索木の説明と実装は、こちらにまとめました。
さわって覚える Python で二分探索木 - いっきに Python に詳しくなるサイト

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

とりあえず、いまはリストなどの線形ではないデータ構造も iterable にできるんだということだけ、なんとなく把握しておいていただければなと思います。











10. イテレータとリストを区別する。

for 文の中での表面的な動作は同じですが、イテレータとリストは全く違うものです。では、どのようにして使い分ければいいでしょうか?
答え: もし、メモリを大量に消費するならイテレータを実装する。

イテレータを使うメリット: メモリの節約

イテレータは、オブジェクトのコピーを作りません。イテレータは、メモリを少しだけしか消費しません。イテレータの大体の構成は、(1) コンテナの現在の要素と(先ほど自作した例で言ええばリストの self._index や木の self._route)、(2) 現在要素から次の要素を取りに行く __next__ メソッドを持っているだけだからです。

import sys

# 重いです。
lst = list(range(10**7))

# list
#   大量のメモリを消費する
#   -> for ループの度にコピーを作るのは非効率的
sys.getsizeof(lst)
# 90000112

# iterator
#  メモリを消費しない
sys.getsizeof(iter(lst))
# 56

イテレータを使うデメリット: 使い勝手が悪い

next 関数や for 文を使って、次の要素を取り出すことはできます。しかし、イテレータを戻ったり(1つ前の要素を取り出したり)、リストのようにいきなり 5 番目の要素を取得すると言ったことはできません。

イテレータを使うデメリット: 若干だけど遅い

実は、素直にリストに全ての要素を叩き込んでから、イテレータを実行した方が、ごくごく若干ですが速そうです。デメリットというほどではないのですが。結果と考察については、こちらにまとめて書きました。
6. リストとイテレータの速度の比較 - Python を高速化したい










11. 内部イテレータと外部イテレータを区別する。

イテレータには2種類の設計の仕方があります。内部イテレータと外部イテレータです。内部イテレータは for 文で回すと空になります。このことを知らないと、ちょっと長いこと悩むような事態に陥ります。

>>> # 空っぽになる内部イテレータの例
>>> file = open('sample.txt', 'r')
>>> for line in file: line
... 
'Hello, world!\n'
'你好,世界!\n'
'こんにちは、世界!\n'
>>>
>>> # 空っぽになっている。
>>> for line in file: line
... 
>>>

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

当たり前のことかもしれませんが,気をつけましょう.弱い筆者はこれを解決するのに2時間(夕食休憩を含む)もかかってしまいました.
イテレータでファイルを扱う時は気をつけようねというお話 | Qiita

もう2回くらい躓いているんだけど, pythoniterator をクラス変数なんかの関数をまたぐものにいれると盛大にバグる. 1回目は list と同様に舐められるけど2回目以降はなくなるという現象.
https://twitter.com/keno_ss/status/973748477808164864


◯ 外部イテレータ

f:id:domodomodomo:20171127163607j:plain
iterable と iterator を切り分けて別々のクラスで設計されている場合、その iterator外部イテレータと呼ばれます。上でせっせと、自作していたのは、全て外部イテレータです。

◯ 外部イテレータを持つ組み込み型の例
list, dic, str 型

普段よく使う list, dictionary, string などの組み込み型は、外部イテレータ list_iterator, dict_keyiterator, str_iterator を持っています。 iterator と container のクラスが、別々に別れています。

最初からユーザが定義せずとも使用できる list, dic, str などの型を組み込み型と呼びます。

>>> iter([1, 2, 3])
<list_iterator object at 0x1053d52b0>
>>>
>>> iter({'a':1, 'b':2, 'c':3})
<dict_keyiterator object at 0x1053c3a98>
>>>
>>> iter('Yaruo')
<str_iterator object at 0x1053d5208>
>>>

◯ 内部イテレータ

f:id:domodomodomo:20171127163715j:plain
反対に iterable と iterator が同じクラスで設計されている場合、その iterator内部イテレータと呼ばれます。

◯ 内部イテレータを持つ組み込み型の例
filter, map, TextIOWrapper 型

filter, map, TextIOWrapper 型は、内部イテレータを持っています。ちなみに TextIOWrapper は、ファイルを読み込む時に使う open 関数から返されるオブジェクトです。

>>> open('sample.txt', 'r')
<_io.TextIOWrapper name='sample.txt' mode='r' encoding='UTF-8'>
>>>



これらのオブジェクトは、1度 for 文で回すと空っぽになります。このことを知らないと、イテレータが空になっていることに気づけずに、長いこと悩むような事態に陥ります。

>>> lst = [0, 1, 2, 3]
>>> iterator = map(lambda x: 2*x, lst)
>>> for i in iterator: i
... 
0
2
4
6
>>>
>>> # 空っぽになっている。
>>> for i in iterator: i
... 
>>> 
>>> file = open('sample.txt', 'r')
>>> for line in file: line
... 
'Hello, world!\n'
'你好,世界!\n'
'こんにちは、世界!\n'
>>>
>>> # 空っぽになっている。
>>> for line in file: line
... 
>>>


◯ 空っぽになった内部イテレータを元に戻したい、リセットしたい。

この節は Effective Python の「項目17: 引数に対してイテレータを使うときには確実さを尊ぶ」 の劣化版です。その方法について、概略を3つ記します。

方法1 もう一度イテレータを呼び出す。

メリットは実装が簡単です。デメリットは、for loop のたびに再代入するのが面倒です。

>>> lst = [0, 1, 2, 3]
>>> iterator = map(lambda x: 2*x, lst)
>>> for i in iterator: i
... 
0
2
4
6
>>>
>>> # もう一回、再代入する。
>>> iterator = map(lambda x: 2*x, lst)
>>> for i in iterator: i
... 
0
2
4
6
>>>
>>> # file.seek メソッドを使います。
>>> file = open('sample.txt', 'r')
>>> for line in file: line
... 
'Hello, world!\n'
'你好,世界!\n'
'こんにちは、世界!\n'
>>> for line in file: line
... 
>>> # 空っぽになる。
>>>
>>> # seek メソッドを使う。
>>> file.seek(0)
0
>>> for line in file: line
... 
'Hello, world!\n'
'你好,世界!\n'
'こんにちは、世界!\n'
>>>
方法2 list にデータを保存する。

メリットは実装が簡単です。デメリットはメモリを消費します。もはやイテレータでは無くなります。もしメモリの使用量が気にならないなら、これがいいと思います。

>>> lst = [0, 1, 2, 3]
>>> lst = list(map(lambda x: 2*x, lst))
>>> for y in lst: y
... 
0
2
4
6
>>> for y in lst: y
... 
0
2
4
6
>>> 
>>> # リストに保存する。
>>> file = open('sample.txt', 'r')
>>> lst = list(file)
>>> lst
['Hello, worlf!\n', '你好,世界!\n', 'こんにちは、世界!\n']
>>>
>>> # 空っぽにならない。
>>> for line in lst: line
... 
'Hello, worlf!\n'
'你好,世界!\n'
'こんにちは、世界!\n'
>>> for line in lst: line
... 
'Hello, worlf!\n'
'你好,世界!\n'
'こんにちは、世界!\n'
>>> 
方法3 iterator クラスと container クラスを分割する。

メリットは、再代入しなくていい。デメリットは実装が面倒です。いままで見てきた通り、iterator クラスと container クラスを分割して、内部イテレータから外部イテレータに再設計します。そうすれば for 文から抜けた後も、イテレータが空っぽになったりするようなこともありません。

# wrapper クラスを作るだけ
class safe_map(object):
    def __init__(self, function, iterable):
        self.function = function
        self.iterable = iterable
    
    def __iter__(self):
        return map(self.function, self.iterable)

# 空っぽにならない
container = safe_map(lambda x: x**2, range(3))
for i in container: i

for i in container: i





◯ まとめ

内部イテレータの利点は、専用のイテレータを実装しないため、実装が簡単です。欠点は、気づきにくいバグを引き起こしやすいです。これは for 文を回すと空っぽになるためです。

外部イテレータの欠点は、専用のイテレータクラスを実装しなければならず、手間がかかります。利点は、内部イテレータのような気づきにくいバグを引き起こしにくいです。これは for 文を回しても空っぽにならないためです。

項目実装バグに
外部イテレータめんどうなりにくい
内部イテレータかんたんなりやすい











ここからは次の2つの疑問について考えてみます。


12 章...なんで StopIteration で判定するの?
13 章...なんで map や filter は、
リストではなくてイテレータを返すの?

12 疑問 1. なんで StopIteration で判定するの?

答え: 速いから


StopIteration で判定するメリット
速い
3.3. 関数ではなく、ベタ書きと例外で終了を通知 - Python を高速化したい






StopIteration で判定するデメリット
例外は、コードが読みづらい。

どのコードが、どの例外をいつ発するのか、この try 文は何を期待しているのかを考えるのが辛い。でも、それを for 文で包むことで、このデメリットを解消している。





13 疑問 2. なんで map や filter は、リストではなくてイテレータを返すようになったの?

答え: メモリの節約になるから

map は Python 2 のころは、リストを返す関数でした。

>>> # Python 2
>>> map(lambda x: 2*x, [0, 1, 2, 3])
[0, 2, 4, 6]
>>>



map は Python 3 では、イテレータを返すクラスに変更されました。map は、遅延評価するイテレータです。

>>> # Python 3
>>> map(lambda x: 2*x, [0, 1, 2, 3])
<map object at 0x1083f4470>
>>> list(map(lambda x: 2*x, [0, 1, 2, 3]))
[0, 2, 4, 6]
>>> 



Python は ABC という教育用言語に影響を受けて可読性を重視して設計されました。

Pythonの開発のスタート時から、もっとも大きい影響を与えた言語は、1980年代の初め頃にLambert Meetens氏とLeo Geurts氏などがオランダ国立情報数学研究所で言語設計を行ったABCである。ABCはBASICの代替の教育用言語を目指していた言語である。

The History of Python.jp: 初期の言語設計と開発



それにも関わらず、なぜ list(map(fun, iterable)) なんていう読みにくい、初学者にとって理解しにくい変更をわざわざしたのでしょうか?特に Python を習いたての頃は、map や filter からイテレータを返されると、わかりにくくて戸惑ってしまいます。そもそもイテレータが何であるかさえ知らないですしね。

実際 map, filter について記事を書こうと思った時に、どうやってイテレータに触れないで説明するかですごく苦慮しました。
Python の map, filter, reduce ってなに?

このような変更を施した理由は、リストのコピーを作るというのは、いままで見てきた通り、メモリを消費するからだと思っていますPythonメーリングリストを漁ったら資料が出てくるかもしれない。

繰り返しになりますが イテレータは、next 関数が呼び出されたタイミングで計算します。1度に計算をすべて行わないのでメモリを節約できます。

>>> # map クラス
>>> iterator = map(lambda x: 2*x, [1, 2, 3])
>>> # 要素を取り出して 2 * 1 を行う
>>> next(iterator)
2
>>> # 要素を取り出して 2 * 2 を行う
>>> next(iterator)
4
>>> # 要素を取り出して 2 * 3 を行う
>>> next(iterator)
6
>>> # 要素を取り出せないので raise StopIteration
>>> next(iterator)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> 




map は、公式のドキュメントでは「2. 組み込み関数 」の項目の中で説明されていますが map はクラスです。これは Python 2 の頃は、map が関数だったことの名残だと思われます。
2. 組み込み関数 map

map だけではなく Python 2 から 3 になるにかけて、filter や zip もリストを返す関数から遅延評価するイテレータになりました。
リストからビューおよびイテレータへ

map 関数が遅延評価だという根拠は Python 2 で itertools.imap として扱われていたものが、組み込み関数として map 関数になりましたという記述を見つけたからです。

Extension Modules

  • Code for itertools ifilter(), imap(), and izip() moved to bultins and renamed to filter(), map(), and zip(). Also, renamed izip_longest() to zip_longest() and ifilterfalse() to filterfalse().
What's New In Python 3.0 | Python.org

◯ range 関数から range クラスへ

Python 2 では range はリストを返す関数で xrange は、遅延評価する iterable をインスタンス化するクラスでした。Python 3 では Python 2 のリストを返す range は廃止されて、代わりに Python 2 の遅延評価する iterable をインスタンス化するクラスの xrange が range になりました(range クラスがインスタンス化したオブジェクトは iteable ではありますが、イテレータそのものはではありません)

Python 2 の頃は range ではなく xrange を使いましょうと、よく言われていました。これは例えば 10**100 回 for 文を回すために range(10**100) と書いてしまうと、for 文を回しただけで多くのメモリを一瞬で消費してしまうためです。

多くの人がすでに知っているとは思いますが、xrangeを使うのがベターです

for i in xrange(6):
    print 1**2

xrange は range と違って一気にメモリを確保しないので、メモリが節約できます。動画中では、xrange という名前は醜い!と言って笑いを取っていましたw ちなみに Python 3 では range が xrange と同様の動きをするようになりましたので、range を使用してOKです。

Pythonらしいコードの書き方 - Kesinの知見置き場



map, filter そして zip からイテレータを返されたり、range が iterable なオブジェクトになってしまうと、最初は、わかりにくくて戸惑ってしまいます。しかし、それでもリストを返す関数が廃止されてしまうくらい、繰り返す iterate するときにはリストよりもイテレータの方が優れた実装ということではないでしょうか。

項目実装メモリの使用量
リストわかりやすい多い
イテレータむずかしい少ない












それでは最後に for 文で使える、iterable とは何かについて触れてこの連載の締めくくりとさせていただきたいと思います。