魅力的なPython

イテレーターとシンプル・ジェネレーター

Python 2.2の新しいコンストラクト

David Mertz
配信 2001年 9月 01日

素敵なフロー制御の世界へようこそ。Python 2.2（現在は3回目のアルファ・リリース。この記事末尾の参考文献を参照）により、プログラマーは以前のバージョンのPythonではできなかった（少なくとも容易でなかった）プログラムを実現するための新しいオプションをいくつか手にすることになります。

Python 2.2で提供されるジェネレーターとイテレーターは、Stackless Pythonの完全継続コードやマイクロスレッドほど「スグレ」ものではないかもしれませんが、従来の関数やクラスと若干異なることをするものです。

イテレーターの方が理解しやすいため、まずイテレーターについて検討しましょう。基本的に、イテレーターは.next()メソッドを持つオブジェクトと言えるでしょう。完全にそうとは言い切れませんが、当たらずとも遠からずといったところです。実際、ほとんどのイテレーター・コンテキストでは、新しいiter()組み込み関数の使用に際してイテレーターを生成するオブジェクトが必要です。ユーザー定義クラス（必要な.next()メソッドを持つ）がイテレーターを返すようにするには、__iter__()メソッドがselfを返すようにしなければなりません。この点は、ここで示す例によって明確にわかるでしょう。イテレーターの.next()メソッドは、イテレーション（反復）に論理的終了がある場合にStopIteration例外を発生します。

ジェネレーターの方がもう少し複雑で汎用的です。しかし、ジェネレーターの最も典型的な用途はイテレーターの定義です。したがって、微妙な用途についてはいつも気にする必要はありません。ジェネレーターは、その関数本体内で直前に返したポイントを記憶する関数です。ジェネレーター関数を2回目（以降）に呼び出すと、すべてのローカル変数が前回の呼び出しから保持された状態で関数の中にジャンプします。

ある意味でジェネレーターは、このコラムの（関数プログラミングに関する）以前の記事（参考文献を参照）で説明したクロージャーに似ています。クロージャー同様、ジェネレーターはデータの状態を「記憶」しています。ただし、ジェネレーターの方がクロージャーよりも機能が若干高度で、フロー・コントロール・コンストラクト（命令型プログラミングでは単なるデータ値ではない）における自らの位置も「記憶」しています。呼び出し側コンテキストに必ず直接戻る（ジェネレーター同様）のではなく、実行フレーム間で任意にジャンプできるため、継続性はより汎用的です。

幸い、ジェネレーターの使用は、プログラムのフローや状態に関するすべての概念的問題を理解するよりはるかに簡単です。実際、少し練習すれば、ジェネレーターは普通の関数のように簡単に感じられます。

ランダム・ウォークの実行

それでは、簡単な問題について考えてみましょう。これらはいくつかの（新旧）方法によって解決できます。後方向制約に従った1未満の正の乱数ストリームが必要だとします。具体的には、連続数がそれぞれ直前の数より少なくとも0.4以上または以下になるようにします。さらに、ストリーム自体は無限でなく、任意のステップ数の後に終了するものとします。この例では、わかりやすくするため0.1未満の数が生成されたときにストリームを終了させるようにしています。以上の制約は、「十分な」、または「局所的な極小」の結果を終了条件とする「ランダム・ウォーク」アルゴリズムに見られるものに少し似ています。しかしながら、この制約は、現実にある殆どの条件より全く単純なものです。

Python 2.1以前では、この問題はいくつかの方法によって解決できます。その1つとして、ストリーム内の数のリストを生成して返すという方法があります。これは以下のようになります。

RandomWalk_List.py

import random
def randomwalk_list():
last, rand = 1, random.random()# init candidate elements
nums = []# empty list
while rand > 0.1:# threshhold terminator
if abs(last-rand) >= 0.4:# accept the number
last = rand
nums.append(rand)# add latest candidate to nums
else:
print'*',# display the rejection
rand = random.random()# new candidate
nums.append(rand)# add the final small element
return nums

この関数の使用は以下のように簡単です。

ランダム・ウォーク・リストのイテレーション

for num in randomwalk_list():
print num,

この方法には、いくつかの注目すべき制限があります。この例では巨大なリストが生成されることはまずありません。しかし、終了のしきい値をより厳しいものとすることで、任意に大きな（実際の大きさは任意であるが、概算は予想可能な）ストリームを作成することができます。この方法は、ある時点を超えると、メモリーとパフォーマンスの点で適さないか必要なくなる場合があります。以前のバージョンのPythonにxrange()とxreadlines()が追加されたのは、これと同様の問題によります。さらに重要なことは、多くのストリームが外部イベントに依存するにもかかわらず、各要素が使用可能であるとその処理が必要になるということです。たとえば、ストリームがポートからの入力やユーザー入力を待つ場合も考えられますが、そうした場合、ストリームから完全なリストを作成することは難しくなります。

Python 2.1以前で使えるトリックの1つに、スタティックな関数のローカル変数を使用して直前の関数呼び出しに関する情報を記憶するという方法があります。確かにグローバル変数でも同じことが行えますが、よく聞かれるグローバル・ネームスペースの汚染や、非局所性による誤りが生じる危険があります。このトリックを知らなかった方は、Pythonには「正式」のスタティックなスコープの宣言がないと知り、驚かれたかもしれません。しかし、名前付きパラメーターに可変のデフォルト値を与えれば、パラメーターを直前の呼び出しの永続メモリーとして用いることができます。特にリストは、複数の値でも保持できる便利な可変オブジェクトです。

「スタティック」アプローチによって、以下の関数を作成できます。

RandomWalk_Static.py

import random
def randomwalk_static(last=[1]):# init the "static" var(s)
rand = random.random()# init a candidate value
if last[0] < 0.1:# threshhold terminator
return None# end-of-stream flag
while abs(last[0]-rand) < 0.4:# look for usable candidate
print'*',# display the rejection
rand = random.random()# new candidate
last[0] = rand# update the "static" var
return rand

この関数は、メモリーをあまり消費しません。この関数は、直前の1つの値のみを記憶し、単一の数値のみ（大きな数値リストではなく）を返します。また、これに類似の関数により、外部イベントに（部分的または完全に）対応する連続数を返すことも可能です。しかし、この関数は、簡潔さに欠け、複雑さが増すという欠点があります。

スタティックなランダム・ウォークのイテレーション

num = randomwalk_static()
while num is not None:
print num,
num = randomwalk_static()

ウォークの新たな方法

実際のところ、Python 2.2のシーケンスはすべてイテレーターです。お馴染みのPythonのイディオム「for elem in lst:」は、lstにイテレーターの生成を要求するようになりました。そのため、forループはStopIteration例外が発生するまでこのイテレーターの.next()メソッドを繰り返し呼び出します。幸い、通常の組み込み型はすべてそれぞれのイテレーターを自動的に生成するため、Pythonプログラマーはここで行われることを詳細に知る必要はありません。実際、現在のディクショナリーにはイテレーター生成用のメソッド.iterkeys()、.iteritems()、.itervalues()が含まれています。最初に挙げたメソッドは、新しいイディオム「for key in dct:」で使用されます。同様に、新しいイディオム「for line in file:」は、.readline()を呼び出すイテレーターを介してサポートされます。

しかし、Pythonインタープリター内で実際に行われることを考えると、組み込み型イテレーターのみを使用するのではなく、独自のイテレーターを生成するカスタム・クラスを使用すべきであることは明らかです。randomwalk_list()による直接の使用とrandomwalk_staticによる「1度に1要素」という節約の双方を可能にするカスタム・クラスは、きわめてわかりやすいものです。

RandomWalk_Iter.py

import random
class randomwalk_iter:
def __init__(self):
self.last = 1# init the prior value
self.rand = random.random()# init a candidate value
def __iter__(self):
return self# simplest iterator creation
def next(self):
if self.rand < 0.1:# threshhold terminator
raise StopIteration# end of iteration
else:# look for usable candidate
while abs(self.last-self.rand) < 0.4:
print'*',# display the rejection
self.rand = random.random()# new candidate
self.last = self.rand# update prior value
return self.rand

このカスタム・イテレーターの使用は、関数が生成する真のリストの場合とまったく同様の外観をしています。

ランダム・ウォーク・クラスによるイテレーション

for num in randomwalk_iter():
print num,

実際、イディオム「if elem in iterator」もサポートされ、真理値決定に必要な数のイテレーター要素のみを試します（当然ですが、最後に偽になった場合はすべての要素を試す必要があります）。

記録を残す

当面の問題には前述のアプローチで十分です。しかし、いずれのアプローチも、ルーチンがその過程において多数のローカル変数を作成し、ループと条件のネストに徐々に入り込むような場合にはうまく適応できません。スタティック（またはグローバル）変数を伴うイテレーター・クラスまたは関数が複数のデータ状態に依存する場合、2つの問題が生じます。1つは、各データ値を保持するための複数のインスタンス属性またはスタティックなリスト要素の作成という一般的な問題です。しかし、それよりはるかに重要な問題は、そのデータ状態に対応するフロー・ロジックの関連部分に正確に戻る方法を見つけなければならないことです。さまざまなデータのイテレーションや共依存関係は非常に見落としやすいものです。

ジェネレーターを使うことによってこれらすべての問題を回避できます。ジェネレーターは、新しいキーワードyieldによって「戻り」ますが、戻ったときの実行ポイントを正確に「記憶」しています。ジェネレーターは、次に呼び出されると、（関数フローでも変数値でも）以前の場所を見つけます。

Python 2.2+では、ジェネレーターが直接作成されるのではなく、呼び出しに応じてジェネレーターを返す関数が作成されます。これは奇妙に思われるかもしれませんが、「関数ファクトリー」はよく知られたPythonの機能であり、「ジェネレーター・ファクトリー」は明らかにその概念を拡張したものです。Python 2.2+では、関数本体のどこかに1つ以上のyieldステートメントが存在する場合に、関数はジェネレーター・ファクトリーになります。yieldが出現する場合、returnは戻り値を伴わずに出現しなければなりません。一方、関数本体はyieldがすべて実行された後に実行が「終了」するように構成した方が良いでしょう。しかし、returnが出現すると、生成されたジェネレーターがさらに値を生成するのではなく、StopIteration例外を発生させることになります。

私の考えでは、ジェネレーター・ファクトリーにおける構文の選択はあまり適切でなかったと思います。関数の本体にyieldステートメントをうまく組み込むことはできますが、関数がその最初のN行のどこかでジェネレーター・ファクトリーとして機能することになっているかどうかを判定できないかもしれません。もちろん、関数ファクトリーについても同じことが言えますが、関数ファクトリーであっても関数本体の実際の構文は変わりません（場合によっては、関数本体が単純値を返すことも認められますが、おそらく優れた設計とは言えません）。個人的には、defの代わりにgeneratorを使用するなど、新しいキーワードを使用した方が良かったと考えてます。

では、構文のことはひとまず終わりにしましょう。ジェネレーターの優れた点は、呼び出しに応じて自動的にイテレーターとして機能することです。この場合、クラスの.__iter__()メソッドのようなものは必要ありません。出現したyieldはすべて、ジェネレーターの.next()メソッドの戻り値となります。簡単なジェネレーターを見てみましょう。

簡単なPython 2.2ジェネレーター

>>>from __future__import generators
>>>def gen():
yield 1
>>> g = gen()
>>> g.next()
1
>>> g.next()
Traceback (most recent call last):
File"<pyshell#15>", line 1,in ?
g.next()
StopIteration

サンプルの問題にジェネレーターを組み込んでみましょう。

RandomWalk_Generator.py

from __future__import generators# only needed for Python 2.2
import random
def randomwalk_generator():
last, rand = 1, random.random()# initialize candidate elements
while rand > 0.1:# threshhold terminator
print'*',# display the rejection
if abs(last-rand) >= 0.4:# accept the number
last = rand# update prior value
yield rand# return AT THIS POINT
rand = random.random()# new candidate
yield rand# return the final small element

この簡潔さは魅力的です。このジェネレーターは、手動でもイテレーターとしても使用できます。手動の場合、プログラム内の至るところでジェネレーターを渡し、必要なときに必要な場所で呼び出しできます（きわめて柔軟です）。以下に、手動の場合の簡単な例を示します。

手動によるランダム・ウォーク・ジェネレーターの使用

gen = randomwalk_generator()
try:
while 1: print gen.next(),
except StopIteration:
pass

しかし、ジェネレーターをイテレーターとして使用することの方が多いと思われます。その場合はより簡単です（この場合も従来のシーケンスに似ています）。

イテレーターとしてのランダム・ウォーク・ジェネレーター

for num in randomwalk_generator():
print_short(num)

yieldの活用

Pythonプログラマーがジェネレーターの特性をよく理解するには少し時間がかかるでしょう。こうした単純なコンストラクトでもその機能は非常に優れたものであり、（Pythonの開発者のような）熟練したプログラマーでも、ジェネレーターをしばらく使用するうちに、いろいろなテクニックを発見することでしょう。

最後に、Python 2.2に付属するtest_generators.pyモジュールからのもう1つのジェネレーターの例をご紹介しましょう。ここでは、ツリー・オブジェクトがあり、そのリーフを左から右に向かって検索すると仮定します。状態監視変数によるクラスまたは関数の最適化は難しいことですが、ジェネレーターを使用すると驚くほど簡単にそれが行えます。

>>>> # A recursive generator that generates Tree leaves in in-order.
>>> def inorder(t):
...     if t:
...         for x in inorder(t.left):
...             yield x
...         yield t.label
...         for x in inorder(t.right):
...             yield x

ダウンロード可能なリソース

• このコンテンツのPDF

関連トピック

• Python 2.2のβ版リリース第2版を入手できます。
• イテレーターの詳細についてはPEP234をご覧ください。
• このコラム記事で示したコードは、1つのソース・ファイルに入っています。
• developerWorksに掲載されているDavid Mertz氏の他の関連記事もご覧ください。
  • Pythonでの関数プログラミング：第1回
  • Pythonでの関数プログラミング：第2回
  • Pythonでの関数プログラミング：第3回
• developerWorksに掲載されている他のLinux関連記事もご覧ください。
• developerWorksに掲載されている他のオープン・ソース関連記事もご覧ください。