読者です 読者をやめる 読者になる 読者になる

あれもPython,これもPython

Pythonで世界を包みたい

今週のPython(2016年4月2日週)とイテレータ

Python勉強記(基本編) 今週のPython

f:id:esu-ko:20160409132604p:plain

はいはーい、今週のPythonです。
始めての方向けに説明すると、
毎週twitterで(手動で)キュレーションした記事を紹介してます。
で、その反応状態を見て、コメントをするシリーズ記事です。

今回は若干趣向を変えて、いきなり記事を全部紹介します。

Python3のmap等の生成物(イテレーター)・丸括弧でのジェネレーター内包表記は使い捨て

Python: ast (Abstract Syntax Tree: 抽象構文木) モジュールについて

PythonでFizzbuzz(1行で)

感想など

渋いですね。
こういぶし銀な凄さが伝わってきます。
なんせリスト内包表記、ジェネレータ内包表記、イテレータ、astですよ。

先週は画像処理記事ばっかりで、
なんか派手感ありましたが、その反動なんでしょうか。

で、
せっかくなんで、今週は真剣に理解するとすごく分かりにくい、
イテレータやジェネレータについてまとめてみます。

イテレーターとは

まずデザインパターン(実装の型のようなもの)にIteratorパターンというものがあります。

Iteratorパターンは、コレクション型データやオブジェクト集合に対して、その実装の内部を公開せずに、その要素に順番にアクセスする方法を提供する。(実践Python3)

データ構造がどのくらいのサイズなのか、どのように実装されているのかを知らなくても、データ構造の各要素を操作できるのだ。(入門 Python3)

ある集合の要素を順に扱える、ということですね。
そしてそのような機能を有するオブジェクトをイテレータブル(反復可能)というわけです。

ここでPythonのforをjavaと比較してみます。

# Python
dat = ["1","2","3"]
for i in dat:
    print i

# 1
# 2
# 3
# java
String[] dat = new String[3];
dat[0] = "1";
dat[1] = "2";
dat[2] = "3";

for(int i = 0;i<3;i++){
    System.out.println(dat[i]);
}

javaの方は、ループを回すために、配列の大きさを知っておく必要があります。
その大きさ分だけループを回し、配列の要素取り出しています。

対して、Pythonの方は、リストの大きさは知らなくても、forの処理を行えます。

イテレータオブジェクトとは

先程はイテレーターの基本的な説明だったわけですが、
具体的にイテレータオブジェクトについて説明します。

初めてのPythonによると

ビルトインオブジェクトは、ビルトイン関数iterを使用することで、対応するイテレータオブジェクトを作成できるよう、あらかじめ設計されてています。

コンテナ型(他のオブジェクトへの参照を持ったオブジェクト)は、
__iter__()という特殊メソッドを持つことでイテレータブルになります。

ややこしいのは、この__iter__()メソッドが返すオブジェクトがイテレータオブジェクトである、ということです。

イテレータオブジェクトイテレータプロトコルに対応したオブジェクトであり、
__iter__()メソッド__next__()メソッドを持っている必要があります。

つまりコンテナからイテレータオブジェクトがつくられ、
そのイテレータオブジェクトは自身を返す__iter__()メソッドを持っています。

このイテレータオブジェクトは__next__()でコンテナ内の次のアイテムがあればそれを返し、
なければ例外を発生させます。

forはどう動くのか

forが使用される場合、
与えられたオブジェクトが__iter__()メソッドを持っているかを確認します。

これを持っている場合は、イテレータオブジェクトが生成され、
__next__()がエラーを出すまで処理を繰り返し、イテレータパターンが実現されます。

ところで、イテレータの機能をつけるためにはもう一つ、
シーケンス型プロトコルをサポートさせるという方法があります。
シーケンス型プロトコルとは__getitem__()メソッドであり、
これをもたせるとインデクシング([]を使った要素へのアクセス)が可能になります。

イテレーターパターンでは、渡されたオブジェクトが、まず__iter__メソッドを持っているか確認し、
持っていない場合は__getitem__で0からエラーが発生するまで、順次インデクシングを行うわけです。

最初の記事の説明

ここまでくると、最初の記事のmapの返り値は一度イテレーションしきると空になり、
リストはそうならない現象というのが説明できるようになります。

リストはイテレータブルですが、イテレータオブジェクトではないので、__next__()メソッドを持っていません。
イテレーションする場合は、__iter__()イテレータオブジェクトを生成し、それをイテレーションするか、
__getitem__()を使ってイテレーションしているので、繰り返しイテレーションできます。

対してpython3系のmap等はイテレータオブジェクトそのものを返し、
イテレーションする際に自身の__next___()を使用するため、
最後までイテレーションすると、空になってしまうわけです。

なんでイテレータの方がメモリ効率が良いのか

まず、リストはそのリストの要素分+増加予定分のメモリを確保します。
これをイテレーションする場合、前述したイテレータオブジェクトを生成するメモリまで保持することになり、
大量にメモリを使用するわけです。

対してイテレータオブジェクトはイテレーション時は自身を使用するため、
メモリ使用量が少なくなるわけです。

で、ジェネレータとイテレータの違い

最後にyieldを用いたジェネレータ関数や、ジェネレータ内包表記を使用したジェネレータオブジェクトと
イテレータの違いを考えて見ようと思います。

ジェネレータはイテレータプロトコルを持っているので、イテレーション可能です。
ただし、ジェネレータは現在の状態を保持し、呼び出される度に次の「区切り」までの処理を実行します。

#  yieldを用いたジェネレータ関数
def gen_test():
    print "first step"
    yield 1 #<- 最初のイテレーションの区切り

    print "second step"
    yield 2 #<- 次のイテレーションの区切り

gen = gen_test()# ジェネレータ関数を呼び出すと、ジェネレータオブジェクトを返す

# ジェネレータオブジェクトはイテレータプロトコルを持つ
gen.next()#最初のイテレーションまでの処理が走る

# 'first step'
# 1

"""
このとき、最初の区切りまで来たという状態を保持している
"""

gen.next()#二回目のイテレーションまでの処理が走る
# 'second step'
# 2

今までのイテレータはコレクションから順次要素を取り出すだけでした。
ジェネレータはイテレーションされる度に、返す値を生成していることになります。
ジェネレータは現在の状態を保持しているだけなので、今まで返した値を覚えていません。
そのため、イテレーションするコレクションのメモリを保持する必要がなく、
サイズが無限のデータを扱えるイテレータとなるわけです。

まとめ

  • イテレータブルなオブジェクト:__iter__()イテレータオブジェクトを返すか、__getitem__()でインデクシングが可能
  • イテレータオブジェクト:__iter__()で自身を返し、__next__()でコレクション内の要素を返す
  • ジェネレータ:__next__()で区切りまでの処理を行い、自身はどこまで処理したかを保持している。今までの処理をコレクションとしては持っていない

おまけ

ちなみによく勘違いされるのですが、
Python2系のxrangeは特殊なシーケンス型です。

この関数は range() に非常によく似ていますが、リストの代わりに XRange 型 を返します。このオブジェクトは不透明なシーケンス型で、対応するリストと同じ値を持ちますが、それらの値全てを同時に記憶しません。

2. 組み込み関数 — Python 2.7.x ドキュメント

なので挙動としてはジェネレータに似ていますが、
イテレータオブジェクトではありません。
(__iter__()__getitem__()は持っていますが、
__next__()を持っていません。)