Python のイテレータとは




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 = []



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

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



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

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



iterable ... 上記のように for 文の in に直接代入できるオブジェクトを、 iterable なオブジェクトと言います。



◯ 出来ること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 関数でイテレータ、リストのコピーのようなものを作って処理を実行します。

全体のコードは、こちら。

# 実装の仕方
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)
# {'長谷部 誠'}



◯ まとめ

イテレータの利点と使い方を説明しました。イテレータの利点と使い方を知っておけば、細かい動作なんて知らなくても全然良いと思います。



















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





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

2 ~ 5 章...実際にイテレータを触ってみる。
6 ~ 10 章...5つのイテレータを自作する。
11 章...イテレータのメリットとデメリットを再確認する。
12 章...2種類あるイテレータの構造を把握する。
13 章...3つの疑問について考える。
14, 15 章...用語からイテレータを復習する。
16 ~ 19 章...もう少し正確にイテレータを把握する。



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 文の方が速いかなと感じています。
3. for 文と while 文の速度の比較

これを見ていると、もし 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 を触って大体の動作を把握しました。ここから先は次の5つの iterator を自作することを通して、最終的にジェネレータまで理解していきたいと思います。


6 章...iterator を自作する1 空集合
7 章...iterator を自作する2 リスト
8 章...iterator を自作する3 リスト(コピーじゃない)
9 章...iterator を自作する4 2分探索木
10 章...iterator を自作する5 2分探索木(ジェネレータ)















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

◯ 解答例(実装例)

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)

◯ 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;
}

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

もともと for 文で回せる list を属性にくっつけただけのオブジェクトを iterable にしても「だからなんやねん?」って感じなので、次は木を iterable にして見ます。

◯ 問題

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

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


f:id:domodomodomo:20171119172218p:plain


こんな操作がしたい。

>>> # 上図と同じ構造の木を作る。
>>> binary_search_tree = BinarySearchTree()
>>> binary_search_tree.insert_list([8, 3, 1, 6, 10, 4, 7, 14, 13])
>>> 
>>> # 木から1つ1つ要素を取り出す。
>>> for element in binary_search_tree:
        print(element)
1
3
4
6
7
8
10
13
14
>>>



まだ iterable でない2分探索木。ワイのキチガイコードを見ると面食らいますが、やってることは結構単純です。

insert メソッドは、木に要素を追加します。要素と等しいか、要素よりも小さければ左の木に追加, 要素よりも大きければ右の木に追加しているだけです。

class BinarySearchTree(object):
    def __init__(self):
        self.element = None
        self.left_tree = None
        self.right_tree = None
    
    def insert(self, new_element):
        if not self.element:
            self.element = new_element
        # 小さければ左の木に追加
        elif new_element <= self.element:
            if not self.left_tree:
                self.left_tree = BinarySearchTree()
            self.left_tree.insert(new_element)
        # 大きければ右の木に追加
        elif new_element > self.element:
            if not self.right_tree:
                self.right_tree = BinarySearchTree()
            self.right_tree.insert(new_element)
    
    def insert_list(self, lst):
        for new_element in lst:
            self.insert(new_element)

◯ 方針

次の2つのメソッドを実装する。

1. __iter__ メソッド

イテレータを返すメソッド。イテレータクラスは自作せず、 リストのイテレータを再利用しましょう。

    def __iter__(self):
        # 2分探索木からリストを生成して、
        lst = self.generate_sorted_list()
        # そのリストのイテレータを返すようにします。
        return iter(lst)
2. generate_sorted_list メソッド

2分探索木からリストを生成するメソッド。このメソッドは、"左下にある要素から順に1つ1つ取っていきます"。

二分木は「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つので、左下の値が一番小さい値になります。なので "左下にあるものから順に要素を取って"いく と、自動的に小さい順にソートされた要素のリストが取れることになります。

木の全てのノードを辿る方法として、深さ優先探索と幅優先探索があります。今回は、深さ優先探索を利用して、"左下にあるものから順に要素を取っていきま" した。

    def generate_sorted_list(self):
        """Get all data by depth-first search."""
        sorted_list = []
        if self.left_tree:
            sorted_list.extend(self.left_tree.generate_sorted_list())
        sorted_list.append(self.element)
        if self.right_tree:
            sorted_list.extend(self.right_tree.generate_sorted_list())
        return sorted_list

◯ 解答例(実装例)

generate_sorted_list と __iter__ を追加して iterable にした2分探索木。ポイントは __iter__ メソッドが list の iterator をそのまま返しているところです。要素を取り出すだけなら iterator クラスの実装はせずに済みます。

class BinarySearchTree(object):
    def __init__(self):
        self.element = None
        self.left_tree = None
        self.right_tree = None
    
    def insert(self, new_element):
        if not self.element:
            self.element = new_element
        # 小さければ左の木に追加
        elif new_element <= self.element:
            if not self.left_tree:
                self.left_tree = BinarySearchTree()
            self.left_tree.insert(new_element)
        # 大きければ右の木に追加
        elif new_element > self.element:
            if not self.right_tree:
                self.right_tree = BinarySearchTree()
            self.right_tree.insert(new_element)
    
    def insert_list(self, lst):
        for new_element in lst:
            self.insert(new_element)
    
    def generate_sorted_list(self):
        """Get all data by depth-first search."""
        sorted_list = []
        if self.left_tree:
            sorted_list.extend(self.left_tree.generate_sorted_list())
        sorted_list.append(self.element)
        if self.right_tree:
            sorted_list.extend(self.right_tree.generate_sorted_list())
        return sorted_list
    
    def __iter__(self):
        # 2分探索木からリストを生成して、
        lst = self.generate_sorted_list()
        # そのリストのイテレータを返すようにします。
        return iter(lst)


if __name__ == "__main__":
    # for 文で使える。
    binary_search_tree = BinarySearchTree()
    binary_search_tree.insert_list([8, 3, 1, 6, 10, 4, 7, 14, 13])
    for element in binary_search_tree:
        print(element)
    
    # iterable を引数に取る関数も使える。例 set 関数。
    tree_a = BinarySearchTree()
    tree_b = BinarySearchTree()
    tree_a.insert_list([1, 2, 3, 4, 5, 6])
    tree_b.insert_list([3, 4, 5, 6, 2, 1])
    print(set(tree_a) == set(tree_b))



◯ 簡単な処理を付け加えたい。

たんに取り出すだけではなく、取り出した要素を2倍にする処理について、比較、検討してみたいと思います。

方法 1. for 文で取り出してから。

これが一番自然ですね。正直、このくらいなら、わざわざ専用のイテレータクラスを実装する必要はなさそうではありますが、このまま他の方法を見てみたいと思います。

for element in binary_search_tree:
    element = 2 * element
方法 2. ジェネレータ

リスト内包表記だと [ ] を使います。( ) を使うと遅延評価するイテレータを返してくれます。ここで返してくれる遅延評価するイテレータというのは、実はジェネレータです。あとで後述します。

class BinarySearchTree(object):
    def __iter__(self):
        return (2 * e for e in self.generate_sorted_list())
方法 3. map クラス

方法 2, 3 は、基本的に同じ意味合いです。このケースでは、記述がシンプルになるので、方法 2 の方が自然かなという気もします。もし、処理させる内容が、式ではおさまらず関数になってしまうケースなら、方法 3 の方が自然だと思います。あるいは、方法 4 のようにイテレータクラスを実装してしまっても、いいかもしれません。

class BinarySearchTree(object):
    def __iter__(self):
        return map(lambda e: 2 * e, self.generate_sorted_list())
方法 4. iterator クラスを実装

iterator のラッパークラス doubling_iter を作成しました。大変冗長ではありますが iterator クラスを新たに実装する分、list だけではなく iterable なオブジェクトに対応した汎用的な設計になります。

class BinarySearchTree(object):
    def __iter__(self):
        return doubling_iter(self.generate_sorted_list())

class doubling_iter(object):
    def __init__(self, iterable):
        self.iterator = iter(iterable)

    def __iter__(self):
        return self

    def __next__(self):
        return 2 * next(self.iterator)
非推奨. list 内包表記から iter 関数で呼び出す。

方法 2 と似た様な書き方ですが、この書き方はオススメしません。何故なら、この非推奨のやり方では 方法 2, 3 の2倍のメモリを必要とするからです。方法 2, 3 では、リストを1回、生成しているのに対して、非推奨のやり方では、リストを2回も生成しています。方法 2, 3 では generate_sorted_list で1回、非推奨のやり方では generate_sorted_list とリスト内包表記で2回です。

class BinarySearchTree(object):
    def __iter__(self):
        return iter([2 * e for e in self.generate_sorted_list()])


10. iterator を自作する4 2分探索木(ジェネレータ)

ジェネレータを使うことにより、メモリの使用量を抑えて、より簡潔にイテレータを表現できます。

◯ ジェネレータとは

ジェネレータも集合みたいなものです。この集合に要素を追加したい時は yiled 文を使います。

def generator_function():
    yield 1  # 要素を追加
    yield 2  # 要素を追加
    yield 3  # 要素を追加
    yield 4  # 要素を追加
    
    # 末端に到達するか return が実行されると
    # SropIteration が自動的に raise される。
    # raise StopIteration


# yiled が使われた関数は
# generator クラスのオブジェクトを返します。
generator_iterator = generator_function()

generator_iterator
# <generator object create_generator at 0x10eecda98>

type(generator_iterator)
# <class 'generator'>

# ジェネレータの要素を表示
for element in generator_iterator: element
# 1
# 2
# 3
# 4

◯ 問題

一つ前の節で自作した 2分探索木 をジェネレータを使って、書き換えます。

◯ 方針

再帰でジェネレータを使う場合は yield from を使用します。

◯ 解答例(実装例)

実装例は次の通りです。list を使った場合に比べて、短く書けています。

class BinarySearchTree(object):

    # 短い
    def __iter__(self):
        if self.left_tree:
            yield from iter(self.left_tree)
        yield self.element
        if self.right_tree:
            yield from iter(self.right_tree)

    """
    # 長い
    def __iter__(self):
        lst = self.generate_sorted_list()
        return iter(lst)

    def generate_sorted_list(self):
        sorted_list = []
        if self.left_tree:
            sorted_list.extend(self.left_tree.generate_sorted_list())
        sorted_list.append(self.element)
        if self.right_tree:
            sorted_list.extend(self.right_tree.generate_sorted_list())
        return sorted_list
    """

◯ ジェネレータのメリット: 表現が簡潔になる。

上で見たとおりです。

◯ ジェネレータのメリット: メモリの節約

実は、ジェネレータはジェネレータが呼び出されるたびに、再起動して、次の要素を取りに行きます。そのため、使用するメモリの総量自体は変りませんが、メモリの瞬間最大使用量は下がります。

反対に、普通のイテレータは、for 文を実行する前に要素を全て保存しなければなりません。例えば「8. iterator を自作する3 2分探索木」を見てください。list に全ての要素を保存してから iter 関数で iterator を返しています。

この2分木の例だと、「メモリの使用量が増える」と言われてもピンと来ませんが、例えばファイルを読み込むような処理をする場合は、ファイル全体を読み込んでしまうとメモリの使用量が一気に上がってしまいます。yiled を使い1行読み込み捨てて、また1行見込み1行捨てるようにすれば、そのような事態は避けられます。

◯ ジェネレータのデメリット

リストに比べて、for 文の実行が 2, 3 割ほど実行速度が遅くなります。実際の比較はリンク先で行なっています。
3. イテレータとジェネレータの for 文の速度の比較

しかし、何事にもさじ加減や状況によるものはあると思いますが、たとえ 2, 3 割実行速度が遅くなったとしてもコード数を簡潔に半分以下に書けるなら、半分以下に書ける方を取るのが望ましいと思います。

Python で書くなら、実行速度よりも可読性を優先するべきです。もし、この塩梅で可読性を犠牲にしてまでも実行速度を求めるようとしたなら、それは違う言語の使用を検討する時です。

◯ list を生成するときは、メソッドを実装しない。

ジェネレータを用いて iterable にした場合、 list を取得するときは、generate_sorted_list のような list を生成するメソッドを実装するのではなく、list のコンストラクタを用いるのが良いと思います。

>>> tree = BinarySearchTree()
>>> tree.insert_list([1, 2, 3, 4, 5, 6])
>>>
>>> # OK
>>> list(tree)
[1, 2, 3, 4, 5, 6]
>>>
>>> # NG 実装しない。
>>> # tree.generate_sorted_list()
>>>

◯ 用語の整理

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

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

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

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

◯ ジェネレータ関数について

Guido van Rossum はジェネレータ関数について、普通の関数を定義する def とは別の用語を、例えば gen のような語を定義しようか迷ったそうです。何故なら、ジェネレータ関数と普通の関数は、異なるものだからです。それは次の2点で異なります。

1つ目は、関数は return で1度に全ての返り値を評価して返すのに対して、ジェネレータ関数は yeild で返り値を個々に遅延評価して返します。

2つ目は、関数は return で指定されたオブジェクトそのものを返すのに対して、ジェネレータ関数は yield で指定されたオブジェクトを返すジェネレータイテレータを返します。

最終的には Guido は、自分の直感に従ったそうです。PEP 255 の文章を引用します。ここで慈悲深き終身独裁官とは Guido を指しています。

慈悲深き終身独裁官による判決
BDFL Pronouncements

議論
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.

PEP 255 -- Simple Generators | Python.org

何故ジェネレータ関数定義は「def」を関数定義と共有して...
PythonWarts - Python Wiki

全然どうでもいいのですが BDFL Pronouncements って Senatus consultum ultimum みたいな感じがしてカッコいい...














11. どういう時にイテレータを使うべき?どういう時に使ったらいけないの?

答え: コードの可読性があがるとき

Python の機能を使って抽象化、簡潔化することが言外にあるのかな、と。感じたりします。抽象化し過ぎてしまうとコードの詳細な動作がわからなくなるというリスクを取りつつも、Python の機能を積極的に用いて簡潔に記述して可読性の向上を図るのが、1つの指針なのかもしれない。

この理由は、第1にPEP 8 では 1 行の文字数を 79 文字に限定しているから。長くても 99 文字と短い。第2に Python が抽象化を支援する機能を提供しているから。第3に仮に /( ) を使うにしても、改行すると可読性は下がるから。

これら3つを組み合わせると適切に抽象化できるならば、抽象化して1行の文字数を減らすことの方が望ましいと言うことが推論できる。
Python PEP 8 の最大 79 文字について

イテレータを使うメリット: 記述がシンプルになります。

iterator を使って、ほんの少しですが記述を簡潔にすることができます。例えば、一番最初の例で見た通り member_list のような属性を参照することなく、直接 for 文や itereable なオブジェクトを引数に取る関数に代入しています。特に木など集合を表現するクラスに応用しやすいと感じています。

# iterable にする
for element in binary_search_tree:
    pass
# iterable にしない, list を使う
for element in binary_search_tree.generate_sorted_list():
    pass

イテレータを使うデメリット: 動作の詳細がわからない。

このコードでは、どのような順序で要素を出力してくれるか、わかりません。

# iterable にする
for element in binary_search_tree:
    pass



過度な抽象化は逆にコードの可読性を下げてしまうそうです。

コードが理解しづらい
 4. コメントなしに低レベルの最適化が施されている
 5. コードが賢すぎる
コードが追いかけづらい
 4. 全てが抽象化されすぎている
まずコードの可読性を最適化しよう | POSTD



ちょっと本題からはづれてしまいますが、Python 2 では reduce 関数が組み込み関数として使えました。 Python 3 では reduce 関数は、組み込み関数から除外されて functools から import することになりました。過度な抽象化を避けると言う意味ではひとつの例かなと思ったりもします。

# 
import functools
lst = [1, 2, 3, 4, 5]

# 1. 明示的に累積ループで書く
def product(s):
    p = 1
    for e in s:
        p = p * e
    return p
product(lst)  # 120

# 2. reduce で書く
functools.reduce(lambda x,y: x*y, lst)  # 120

# 3. Python2 では import しなくても書けた
# reduce(lambda x,y: x*y, lst)  # 120



なぜかと言うと読み辛いからだそうです。以下のブログは Guido のブログからの引用です。

今度は reduce 関数について考えよう。これは実際私がいつも最も憎むものだ。+ もしくは * を含む2、3の例を除けば reduce 関数はいつもパッと見ではわからないような関数を引数にとって呼び出されている。
So now reduce(). This is actually the one I've always hated most, because, apart from a few examples involving + or *, almost every time I see a reduce() call with a non-trivial function argument,

私は reduce 関数が何をしているかを理解する前に、引数として与えられた関数に、実際に何が与えられているのかを図示するために紙とペンを取らないといけない。
I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do.

したがって私の中では reduce 関数が適用できるのは、結合演算子にごく限定される(訳注: 結合演算子 ... 例えば +, -, *, / などの四則演算子)。それ以外の事例では明示的に累積ループを書いた方がよい。
So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly.
The fate of reduce() in Python 3000 by Guido van van Rossum

Python と Go 言語

Python は iterable にすることによって、書き方をシンプルにできる。ただ iterable にしない書きかもできて、その分だけ書き方に幅ができてしまいます。

Python って誰が書いても同じようなコードになりますみたいな言葉を誰かから聞いた気がして、個人的にもそう言うのが好きなので、ちょっと気持ち悪い気もします。

反対に Go 言語というものがあります。Go 言語は、機能を削って設計された言語のようです。その分だけ記述には、どうしても煩雑さを要してしまうところもあります。ただ、書き方は、より統一されるみたいな感じになるようです。

ここで機能を削ってできたと言われる Go 言語ならどんな扱いになってるんやろうか..と気になったのですが、まだよくわかりませんが..、なんとなく Pythonイテレータと同等の機能を提供するものは無さそうです。

それならサービスが固まってない段階は Python が提供する様々な機能を積極的に使ってシンプルに書いて、そこからサービスが固まったら Go でリファクタリングして処理速度を求めて低レベルな記述に書き写して書くというのは、ある意味正しい流れなのかもしれない..。Rust の位置付けはどうなのだろうか...。
なぜ私達は Python から Go に移行したのか - Frasco
















12. 内部イテレータと外部イテレータ

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

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

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

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

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



◯ 外部イテレータ

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 = [y for y in 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 = [line for line in 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 文を回しても空っぽにならないためです。

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

13. 3つの疑問

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

答え: 速いから



Java みたいに hasNext メソッドを実装して書くようなやり方でもよかったのじゃないのかと。

// Java 条件で判定
Iterator it = sequence.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}
# Python 例外で判定
it = iter(sequence)
while True:
    try:
        print(next(it))
    except StopIteration:
        break


例外のメリット
1. 稀にしか False が生じないようなケースでは、繰り返しの処理を条件分岐で処理させるよりも例外で処理した方が速いから。

解決した問題 - PEP 234 Iterators
Resolved Issues - PEP 234 Iterators

イテレーションの終端であることを示すシグナルに対して、例外を使うことがあまりにも処理が重すぎないか、疑問であった。
It has been questioned whether an exception to signal the end of the iteration isn't too expensive.

end 関数を呼び出すことは、1度のイテレーションで2度の呼び出しをしないといけない。2つの呼び出しは、例外の検査を含めた1度の呼び出しよりも重い処理である。特に実行速度が重要な for ループに対して、例外のための検査をとても軽い処理で行える。
Calling an end() function would require two calls per iteration. Two calls is much more expensive than one call plus a test for an exception. Especially the time-critical for loop can test very cheaply for an exception.

Java の hasNext と同じようなことをしたいために end 関数で判定しようとすると、next 関数を呼び出す前に、end 関数も呼び出さないといけなくなります。2回関数を呼び出実装は、1回関数を呼び出して例外で判定する実装よりも、速度が遅くなってしまいます。

他にも list を比較するような処理を行うときにも同じようなことが言えました。例としては、こちらの方がわかりやすいかなと思ったりもします。
7. if 文と 例外の速度の比較 - Python を高速化したい




2. わざわざ hasNext メソッドを実装するよりも __next__ メソッドが例外を出しすようにして1つにまとめた方が綺麗に書けるから。特にジェネレータを書くときに hasNext メソッドのようなものを実装するのは煩雑。





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


疑問 2. なんで iterator には自分自身を返すメソッド __iter__ を実装するの?(読み飛ばしてください)

答え: next メソッドを実装しているだけでは、イテレータであるかどうかを判定するのに不十分だから。

実はこれ Python 2 の話に戻ります。昔は __next__ メソッドではなく、直接 next メソッドを実装していました。呼び出すときも iter.next() として呼び出していました。Python 2.6 から next(iter) という書き方が登場します。Python 3 になってから __next__ メソッドが、登場します。

next() (.next()) はよく使われる関数ですが、以下は言及する価値のある構文の変化(そして実装の変化)です。Python 2.7.5 で関数とメソッドの構文を使えるところでは、Python 3 では next() 関数しか残っていません。(.next() メソッドを呼ぶと AttributeError になります)

next() 関数 と .next() メソッド



一体何が価値ある構文の変化なのかというと、もし、next メソッドが実装されているかどうかだけでの判定では、プログラマが next を別の用途で実装していた場合と区別がつきません。普通のユーザが定義したメソッドと区別つかないやろって話は len 関数の時にも同じような話をしていました。
Python の len はなんでメソッドではなく関数なの? -

ただ、正直、理解できていません。以下の文章は Guido のメールからの抜粋です。気になる方は、リンク先の英文を読んで見てください。

なぜイテレータは __iter__ メソッドを持たないといけないのか
Why must an iterator have an __iter__ method? (fwd)

いま、質問の本題に戻りましょう。なぜ iterator オブジェクトは <iter> を実装しなければならないのでしょうか?私のこれに対する理由は、"for item in iterator" と書いたときに、for-loop の実装が、私が会議の BOF で "type sniffing" と呼んだものを実行しなくて良いようにするためです。for-loop は単純に <iter> を実行して、iterator 自身を返します、そしたら for-loop はハッピーですよね。もし、オブジェクトが <iter> を実装していなければ、for-loop は、そのオブジェクトを受けつけません。
Now let's go back to the question in the subject: why must iterator objects implement <iter>? My reason for this was so that when we write "for item in iterator", the for-loop implementation doesn't have to do what I called "type sniffing" in the BOF at the conference. It simply invokes on the iterator, which returns the iterator itself, and the for-loop is happy. If the object doesn't implement <iter>, it's not acceptable input for a for-loop.

上記別の提案では、異なる方法を提案しています。
The alternative proposal above suggests a different approach:

1. look for <next>
2. look for <iter>
3. look for <getitem>

私は、このやり方は特定の場合においてのみ理にかなっていると思っています。もし確実に <next> を判定できる場合、言い換えるなら、もし確実にあるオブジェクトをイテレータであるかどうか区別できる場合ような場合です。
I think this could only done reasonably, if we can reliably check for , in other words, if we can reliably tell if something is an iterator.

しかし、これは Python においては一般的な問題です。例えば、どうやって CPython のコードから、あるオブジェクトがシーケンスであるかどうかを判定しますか?オブジェクトがクラスインスタンスでない場合、tp_getitem が定義されているかどうかを調べるでしょう。しかし、もし、クラスインスタンスなら、最善の方法は __getitem__ を定義しているかどうかを確認し、オブジェクトが辞書でないことを望むしかありません!(注釈: わからない.. __getitem__ メソッドを実装しているオブジェクトが辞書かシーケンスかを判定できない.. ということかな。ここで言っているクラスインスタンスって何のことだろう?)
But this is a general problem in Python! How do you check (from Ccode) if something is a sequence? If it's not a class instance, you check whether it defines tp_getitem; but if it is a class instance, the best you can do is check whether it defines __getitem__ and hope it isn't a dictionary!

言い換えるなら、オブジェクトが特定のプロトコルを実装しているかどうかをテストするのは、難しいし曖昧です。プロトコルを使うことは簡単です。
In other words, testing whether an object implements a particular protocol is hard, or ill-defined. *Using* a protocol is easy.

type sniffing
おそらく型判定, ここでは iterable であるかどうかの判定だと思われます。<next> か <iter> のどちらかひとつだけを実装していれば、 iterable だって判定させる実装よりは、<iter> が実装されていればイテレータだと判断する方が、簡単、みたいなそんな文章が続いています。

BOF(bird of feather)
同じ興味を持つ人たちの集まり、特定のテーマの自由討論会◆特にIT関連のフォーラムなどで、特定のテーマに関連や関心のある人が集まり、自由に議論したり情報交換したりする場を指す。会議のプログラムとして予定されているものもあれば、非公式のものもある。




Python 3 では __next__ メソッドで定義するようになったので、必要ないんじゃないかなと思ったのですが、組み込み型である list の iterator の list_iterator, dict の iterator の dict_keyiterator, str の iterator の str_iterator は、ちゃんと __iter__ メソッドを実装しています。

#
# 1) list_iterator
#
type(iter([]))
# <class 'list_iterator'>
hasattr(iter([]), '__iter__')
# True

#
# 2) dict_keyiterator
#
type(iter({}))
# <class 'dict_keyiterator'>
hasattr(iter({}), '__iter__')
# True

#
# 3) str_iterator
#
type(iter(''))
# <class 'str_iterator'>
hasattr(iter(''), '__iter__')
# True



ちなみに iterator に __iter__ メソッドがなくても for 文自体は全く問題なく動作します。何で残したのか疑問ではあります。型判定のために残りしているのでしょうか。

例えば Effective Python の「項目17: 引数に対してイテレータを使うときには確実さを尊ぶ」で内部イテレータと外部イテレータを区別する際に、この __iter__ を活用するような書き方を指示しています。



疑問 3. なんで map や filter は、リストではなくてイテレータを返すの?

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

Python を習いたての頃は、map や filter からイテレータを返されると、わかりにくくて戸惑ってしまいます。そもそもイテレータが何であるかさえ知らないですしね。

map は、遅延評価するイテレータです。遅延評価するイテレータというのは、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
>>> 
>>> # list 内包表記
>>> #   リストに格納するために
>>> #   1度に 2*1, 2*2, 2*3 を全て実行してしまう。
>>> lst = [2 * x for x in [1, 2, 3]]
>>>



そして list_iterator クラスと同じように map クラスもコピーでは、ありません。ところが、昔 Python 2 では map はクラスではなく関数でした。Python 2 では map 関数を使うとリストが返されました。このような変更を施した理由は、リストのコピーを作るというのはメモリを消費するからだと思っています。

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


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

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

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

Python 2 の頃は range ではなく xrange を使いましょうと、よく言われていました。これは例えば range(10*100) みたいなことをしたらとてつもないメモリを一瞬で消費してしまうためです。

多くの人がすでに知っているとは思いますが、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 することを実装ときには、リストよりもイテレータの方が、優れているということではないでしょうか。

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














14. 用語

復習を兼ねて、上記の動作例で使用した組み込み関数、オブジェクトメソッド、発生した例外を一度、整理して見たいと思います。

以下は、マニュアルからの抜粋になります。

container
他のオブジェクトに対する参照をもつオブジェクトもあります; これらは コンテナ (container) と呼ばれます。コンテナオブジェクトの例として、タプル、リスト、および辞書が挙げられます。オブジェクトへの参照自体がコンテナの値の一部です。
— ワイの注記 container について記述されている箇所の抜粋しました。タプル、リスト、および辞書など集合を表現するオブジェクトを container だと言いたい様子。ただ、この定義だと全てのオブジェクトが container に該当してしまうんじゃまいか..

iter(object[, sentinel])
イテレータ (iterator) オブジェクトを返します。 第二引数があるかどうかで、第一引数の解釈は大きく異なります。

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

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

next(iterator[, default])
iterator の __next__() メソッドを呼び出すことにより、次の要素を取得します。イテレータが尽きている場合、 default が与えられていればそれが返され、そうでなければ StopIteration が送出されます。

iterator.__next__()
コンテナの次のアイテムを返します。

StopIteration
組込み関数 next() と iterator の __next__() メソッドによって、そのイテレータが生成するアイテムがこれ以上ないことを伝えるために送出されます。

generator(ジェネレータ)
generator iterator を返す関数です。 通常の関数に似ていますが、 yield 式を持つ点で異なります。 yield 式は、 for ループで使用できたり、next() 関数で値を 1 つずつ取り出したりできる、値の並びを生成するのに使用されます。
通常はジェネレータ関数を指しますが、文脈によっては ジェネレータイテレータを指す場合があります。 意図された意味が明らかでない場合、 明瞭化のために完全な単語を使用します。

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

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

15. イテレータとは

復習を兼ねて、言葉から一般論を追いかけてみます。

◯ 辞書では

辞書では、どのように説明されているのでしょうか?

iterate
 (Vi) 繰り返し適用される
 (Vt) ~を繰り返して言う, ~を反復する
~tor
 ~する人
英辞郎 on the WEB:アルク

「繰り返すもの」ってことですかね?

Wikipedia では

イテレータ(英語: iterator)とは、プログラミング言語において配列やそれに類似する集合的データ構造(コレクションあるいはコンテナ)の各要素に対する繰り返し処理の抽象化である。
イテレータ - Wikipedia

いまいちよくわかりません??

Python の公式ドキュメントでは

Python では、どのように説明されているのでしょうか?

iterator
 データの流れを表現するオブジェクトです。
用語集 — Python 3.6.5 ドキュメント









f:id:domodomodomo:20171106122644j:plain


もっとよくわからなくなりました???笑
















ここから下はもう少し

 「iterable って、正確にはなんだろう?」
 「container って、集合じゃなくても良くない?」

って疑問に思った方だけ読んでいただければと思います。



container は集合で iterator はそのコピーみたいなものと考えると理解しやすいです。しかし、実際の実装では別に container や iteraotr が集合である必要も __next__ メソッドがその要素を取り出す必要もありません。

どう言うことかと言えば、マニュアルで指定された __next__ メソッドや __iter__ メソッドが定義さえされていれば for 文で問題なく使うことができます。だから Python の公式ドキュメントは、イテレータを「データの流れを表現するオブジェクトです。」というなんともわからない表現をしています。

ここから先では文章ではなく、iterable であるかどうかを判定するコードを書いて、イテレータの理解を深めていきたいと思います。



16 章...iterable の定義
17 章...① isiterable 関数
18 章...② isiterable 関数(詳細版)
19 章...③ assertIsIterableContainer 関数

16. iterable の定義

for 文の in にいれることができれば iterable だと言えそうです。

iterable
構成要素を一度に一つずつ返すことができるオブジェクトです。構成要素を一度に一つずつ返すことができるオブジェクトです。

イテラブルの例には、(list 、 str 、 tuple のような) 全てのシーケンス型 、 dict ... などがあります。

イテラブルは for ループやその他シーケンスが必要な多くの場所 (zip() 、 map() 、 ...) で使えます。

用語集 — Python 3.6.5 ドキュメント

What exactly are Python's iterator, iterable, and iteration protocols?


17. ① isiterable 関数

簡単に言えば for ~ in ... の ... に入れても動作できるかどうかを判定します。

def isiterable(container):
    return hasattr(container, '__iter__') 



これで十分です。あれだけ盛り上げておいてこれかよ、って感じですが..。

(追記)__getitem__ メソッドでも iterable にできます。このことを見過ごしていました。後日加筆訂正するつもりですが、現在は __iter__ メソッドについてのみ考えます。
__getitem__の挙動についてメモ - 素数好きの最高技術責任者のブログ

◯ でも、別の用途で __iter__ メソッドが定義されているかもしれないけどいいの?

答え: 問題ありません。

Python では __iter__ は全てのオブジェクトが iterator を返す様にマニュアルで定められているからです。

前後左右に2つのアンダースコアで挟まれた変数、または属性は __*__ 、マニュアルで記載された以外の用途で使ってはならないことになっています。

例えば __init__ メソッドを初期化以外の別の用途で使ったら、大変なことになってしまいますよね。

このドキュメントで明記されている用法に従わない、 あらゆる __*__ の名前は、いかなる文脈における利用でも、警告無く損害を引き起こすことがあります。
2. 字句解析 — Python 3.6.5 ドキュメント

◯ duck typing (Java を知らない人は読み飛ばしてください。)

__iter__ メソッドさえ定義されていれば iterable だと言えます。

Java とは違い Python では、例えば iterable という interface が継承されていなくても、同じ名前の method さえ定義されていれば、iterable という interface を実装している様に振舞うことができます。この様な型付の性質は duck typing と呼ばれたりします。

iterable という interface が宣言されていなくても(duck というinterface がされていなくとも)、iter メソッドを実装していて、そいつが iterator のように振る舞うなら(duck のように鳴き、よちよち歩くなら)、そいつは iterator だ!(duck だ!)という意味合いだそうです。

static typing が静的型付け, dynamic typing が動的型付けと訳されるなら、duck typing は鴨的型付けって訳になるんですかね..。
デザインパターン「Iterator」-Qiita (Java での iterator の例)

また mypy を使う場合は duck typing を許してくれなさそうな気配があります。例えば mypy を使うと __iter__ を実装しているだけでは iterable とみなしてくれず、ちゃんとクラス定義時に iterable であることを明示するオブジェクト Iterable を継承しないとエラーを返されます。

from typing import Iterator, Iterable

# NG -> error: Iterable expected
# class Foo(object):
class Foo(Iterable):
    def __iter__(self) -> Iterator[int]:
        yield 1
        yield 2

for x in Foo():
    print(x)

Mypy doesn't recognize objects implementing __iter__ as being Iterable · Issue #2598 · python/mypy · GitHub

18. ② isiterable 関数(詳細版)

iterable container, iterator が __iter__, __next__ メソッドを実装しているかどうかの判定しています。

def isiterable(container):
    # container
    if not hasmethod(container, '__iter__'):
        return False
    # iterator
    iterator = container.__iter__()
    if not hasmethod(iterator, '__iter__'):
        return False
    if iterator.__iter__() is not iterator:
        return False
    if not hasmethod(iterator, '__next__'):
        return False
    return True


def hasmethod(obj, method_name):
    return hasattr(obj, method_name) \
        and callable(getattr(obj, method_name))


要素を全て出力したら StopIteration を吐くかどうかの判定は行いません。

iterator を生成して、StopIteration を吐くかどうかを確認するためには、要素数の数だけ next 関数を呼び出すしかありません。この実装は次の2つの理由から却下しました。

第1に iterator オブジェクトが副作用を持っている可能性があるから。第2に要素数の数だけ next 関数を呼び出すのは時間がかかるから。


19. ③ assertIsIterableContainer 関数

isiterable 関数より詳しく StopIteration を正しく吐くかどうかまで判定するコードです。 あるいは、イテレータプロトコルが正しく実装されているか判定するコードです。Python ではオブジェクト間の定められたやり取りをプロトコルと表現しているようです。

ここまで来ると isiterable と言う判定よりも、test に近くなるので assert を吐くようにしました。使い所はびっくりするほど全くないと思いますが、unittest の練習がてらに書いてみました。てきとうに暖かい目で流して、眺めていていただけると嬉しいです。

◯ 使い方

import unittest
class TestIterableContainer(unittest.TestCase):
    def test_iterable_container(self):
        iterable_container = Container(
            'Trump', 'Obama', 'Clinton')
        # success
        assertIsIterableContainer(iterable_container, 3)
        # error
        assertIsIterableContainer(iterable_container, 4)





unittest を実行するも num_of_elements 4 より小さい繰り返し回数 3 回で StopIteration が raise されたのでエラーで返されている。

$ # python -m unittest テストファイルスクリプト
$ python -m unittest test_iterable_container
F
======================================================================
FAIL: test_iterable_container (test_iterable_container.TestIterableContainer)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "test_iterable_container.py", line 28, in assertIsIterableContainer
    next(iterator)
  File "test_iterable_container.py", line 77, in __next__
    raise StopIteration('No name is stocked...')
StopIteration: No name is stocked...

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "test_iterable_container.py", line 88, in test_iterable_container
    assertIsIterableContainer(iterable_container, 4)
  File "test_iterable_container.py", line 38, in assertIsIterableContainer
    'but less than num_of_elements.')
AssertionError: StopIteration arised, but less than num_of_elements.

----------------------------------------------------------------------
Ran 1 test in 0.000s

FAILED (failures=1)
$


◯ test_iterable_container.py

シェルにコピペするだけでも動作を確認できる様になってます。

import unittest


class TestIterableContainer(unittest.TestCase):
    def test_iterable_container(self):
        iterable_container = Container(
            'Trump', 'Obama', 'Clinton')
        # success
        assertIsIterableContainer(iterable_container, 3)
        # error
        assertIsIterableContainer(iterable_container, 4)


def assertIsIterableContainer(container, num_of_elements):
    if not(type(num_of_elements) is int and num_of_elements >= 0):
        raise ValueError('num_of_element sholud be zero or a natural number.')
    
    # 1) container.__iter__()
    assert hasmethod(container, '__iter__'), \
        'container does not have __iter__ method.'
    iterator = container.__iter__()
    
    # 2) iterator.__iter__()
    # Does this function return self?
    assert hasmethod(iterator, '__iter__'), \
        'iterator does not have __iter__ method.'
    assert iterator is iterator.__iter__(), \
        'iteraotr.__iter()__ does not return himself.'
    
    # 3) iterator.__next__()
    assert hasmethod(iterator, '__next__'), \
        'iterator does not have __next__ method.'
    
    # 4)
    # After popping all elements,
    # does this function raise StopIteration?
    k = -1
    while True:
        try:
            k = k + 1
            next(iterator)
            
        except StopIteration:
            # 4-0) success
            if k == num_of_elements:
                break
            # 4-1) less than num_of_elements
            elif k < num_of_elements:
                raise AssertionError(
                    'StopIteration arised, ' +
                    'but less than num_of_elements.')
                    
        else:
            # 4-2) more than num_of_elements
            if k == num_of_elements:
                raise AssertionError(
                    'iterator\'s method __next__ called, ' +
                    'but more than num_of_elements.')

def hasmethod(obj, method_name):
    return hasattr(obj, method_name) \
        and callable(getattr(obj, method_name))


#
# sample iteraotr
#
class Container(object):
    def __init__(self, *args):
        # type(args) is tuple
        self.tuple = args
    
    # container.__iter__()
    def __iter__(self):
        return Iterator(*self.tuple)


class Iterator(object):
    def __init__(self, *args):
        self.list = list(args)
    
    # iterator.__iter__()
    def __iter__(self):
        return self
    
    # iterator.__next__()
    def __next__(self):
        if self.list:
            return "Hello, " + self.list.pop() + "."
        else:
            raise StopIteration('No name is stocked...')


#
# main
#   インタラクティブシェルにコピペするだけでも動くために
#
if __name__ == '__main__':
    test_iterable_container = TestIterableContainer()
    test_iterable_container.test_iterable_container()



20. おわりに

最後まで、お読みいただき、ありがとうございました。

Remove all ads