リストの先読み
リストを先読みするには以下のようにイテレータを複製して、ポインタを必要な分だけ進めておく。そして並列に回す。
>>> from itertools import * >>> xs = range(7) >>> xs1 = chain(xs, [None, None]) >>> xs1, xs2, xs3 = tee(xs1, 3) >>> xs2.next() 0 >>> xs3.next(); xs3.next() 0 1 >>> for x1, x2, x3 in zip(xs1, xs2, xs3): ... print x1, x2, x3 ... 0 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 None 6 None None
このアイデアでcompact-number-listの拡張版のお題を実装した例を以下に示す。
# coding: cp932 from itertools import * def compact_number_list(seq): seq1 = chain(seq, [None, None]) seq1, seq2, seq3 = tee(seq1, 3) # seq1を2つコピー seq2.next() # 1つ先読みするために1つ進めておく start = seq3.next() next_ = seq3.next() # 2つ先読みするために2つ進めておく if not start: return if not next_: yield start return diff = next_ - start for c, c2, c3 in izip(seq1, seq2, seq3): if not c3 or diff != c3 - c2: if start == c: yield c else: if diff == 1: yield [start, c2] else: yield [start, c2, diff] c, c2, c3 = seq1.next(), seq2.next(), seq3.next() start = c2 if c3: diff = c3 - c2 L = [1, 3, 4, 5, 6, 12, 13, 15, 20, 25, 26, 27] print list(compact_number_list(L)) #=> [1, [3, 6], 12, 13, [15, 25, 5], 26, 27]
以前の実装よりもだいぶすっきりした。compact_number_listで与えられる引数は正の整数のリストおよびイテレータの両方に対応。
補足(2008/10/21):
リストを先読みするには通常インデクシングを行う。しかしイテレータを先読みする場合この方法は有用。インデクシングを使用するとリストのみしか扱えない。この方法ならリストとイテレータを統一して扱える。
再帰の考え方
まず例を見てみよう。
for i in range(10): print i
上記の例では、iの状態を0から9まで変えながらループしている。ここで、1つのループをフレームと呼ぶことにする。次に再帰のコード例を見てみる。
def fib(n): if n==0 or n==1: return 1 else: return fib(n - 1) + fib(n - 2) # 過去のフレームの情報を取得!
さらにfor文を使用した例を見てみる。
def fib(n): num1, num2, tmp = 1, 1, 1 for i in range(1, n): tmp = num1 + num2 num1 = num2 num2 = tmp return tmp
ここで、1つのフレームに対応して1つの状態が決まり、なおかつ同一フレーム内で別のフレームの情報も利用したいケースを考えよう。すると、再帰の例では、あるフレームにおいて別のフレームの情報を取得している。そして、for文の例では別のフレームに対応する状態を保存している。
さらに、リストデータを使用した場合を考えてみよう。あるフレームの状態はリストのあるインデックスに対する値に対応している。ここで、状態はリストとして保存されているので状態を保存ではなく参照できれば良いことに気が付く。
つまり、前述の先読みのテクニックとは、過去や未来のフレームの状態を現在のフレームで取得する方法ということになる。再帰の強みは過去や未来の状態を保存していなくてもいつでも取り出せることである。それに対して、for文を使用すると過去や未来の状態を保存したり参照したりする方法を管理しないといけない。その部分が再帰とfor文との本質的な違いではないかと思う。