Pythonの技法:ジェネレータを用いた遅延リストの構築

文:Nick Gibson(Builder AU)  翻訳校正:原井彰弘
2008-01-17 15:00:00
  • このエントリーをはてなブックマークに追加

 ここまでは、ジェネレータをリストを構築する目的で使用し、計算時間を節約してきた。確かにこれはすばらしいことだ。しかし、ジェネレータがその本領を発揮するのは、リスト全体を計算するのが不可能な場合である。ここではフィボナッチ数列を例にとってみよう。フィボナッチ数列は、それぞれの値が手前の2つの値の和になっている数列のことだ。指定した値までのフィボナッチ数列のシーケンスを生成する関数が欲しいとしよう。関数は以下のようになる。

>>> def fib(n):
...     a, b = 0, 1
...     l = [a]
...     while b < n:
...             l += [b]
...             a, b = b, a+b
...     return l
... 
>>> fib(20)
[0, 1, 1, 2, 3, 5, 8, 13]

 この関数は正しく動作するが、それは特定の数に達したときに計算を停止したい場合においてである。もし停止する条件を変更したい場合は、関数を書き直さなければならない。しかし、ここでジェネレータを使用すると以下のように実装できる(この実装は、ジェネレータについてのPython PEPから借用した)。

>>> def xfib():
...     a,b = 0,1
...     while True:
...             yield b
...             a, b = b, a+b
... 
>>> fibseries = xfib()
>>> b = fibseries.next()
>>> while b < 20:
...     print b
...     b = fibseries.next()
... 
1
1
2
3
5
8
13

 この実装の場合は、たとえば(2桁以上の)最初の回文的な数値で停止したいといったような場合でも、以下のようにしてループの条件を変更するだけでよい。

>>> fibseries = xfib()
>>> b = fibseries.next()
>>> while b < 10 or not list(str(b)) == list(reversed(str(b))):
... print b
... b = fibseries.next()
...
1
1
2
3
5
8
13
21
34

 たったこれだけである(ちなみに次の数列の値は55だ)。このようにしてジェネレータを用いれば、必要になった値のみを計算する機能を維持しつつも、さらに、リストを構築する際の実装と生成の停止を判断するロジックを分離することが可能になるのだ。

 いつリストの内包表記の代わりにジェネレータを用いるべきなのだろうか?もし、必ずリストの要素すべてを使用することが分かっているのなら、リストの内包表記を用いた方がよいだろう。なぜなら、リストの内包表記にはジェネレータが関数を呼び出す際に生じるオーバーヘッドがないからだ。一方、リストの最初の部分のみを使用するつもりなら、CPUの処理時間を節約できるジェネレータを使用すべきだろう。

このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]