イテレータ，ジェネレータ，リスト包括表記と集合構成記法

イテレータ，ジェネレータ，リスト包括表記と集合構成記法

私は今Think Complexityでアルゴリズムと複雑系について勉強しています． 今回は，自分の勉強を兼ねてThinkComplexity(chap2とchap3)で勉強した

• iterator(イテレータ)とlistの違い
• generator（ジェネレータ）
• list comprehension（リスト包括表記）
• プログラマのための集合構成記法(Set-builder notation)

についてまとめを行いたいと思います． Think Complexity は無料で読む事もできます！

iteratorとは

pythonでいうiteratorとは __iter__メソッドと次の要素を返す __next__メソッドを持つオブジェクトの事です． __next__メソッドは要素が無くなると StopIteration例外を送出します．

下記がiteratorの実装例です． counter.pyとgen_counter.pyの counterクラスは無限に1,2,3,4,5, . . . . . とカウントするiteratorです． counter.pyのcounterクラスはnextメソッドが呼ばれると カウントします．for文では初めにiterメソッドが呼ばれ， 次にnextメソッドが呼ばれます．

gen_counter.pyのcounterクラスはiterが呼ばれると yield文を使って，カウントを行います．このように yieldを使ってiteratorを簡単に生成する関数（メソッド）を generator（ジェネレーター）と呼びます． 今回の例ではiterメソッドがジェネレーターです． ちなみにyieldは関数・メソッド内でのみ使用する事が可能です．

iteratorとlistの違い

iteratorとlistの大きな違いは for文を使う時の速さです．もちろん先程説明した通り， iteratorはイテレータプロトコル（__iter__とnextメソッド）を 実装している必要があるため，オブジェクト的に全く違います．

例えば，辞書を走査（traverse）するとき， 主に２つの方法があります．

• １つはitemsメソッドでタプルのリストを生成して，走査する方法．

• ２つ目は，iteritemsメソッドでイテレータを生成して イタレータを走査する方法．

• itemsでの走査

d = dict(a=1, b=2, c=3)
for k, v in d.items():
    print k, v

• iteritemsでの走査

d = dict(a=1, b=2, c=3)
for k, v in d.iteritems():
    print k, v

d.items()とすることで，タプルのリスト[('a', 1), ('c', 3), ('b', 2)] が生成されます．このリストを生成するのにO(n)掛かりますが， d.iteritems()でイテレータオブジェクト を生成するのにはO(1)しか掛かりません．

ループで走査(O(n))するため，d.items()ではO(n)+O(n)でオーダはO(n)． d.iteritems()での走査はO(1)+O(n)でオーダがO(n)と結局オーダは変化しませんが， 係数が変ってくるためオバーヘッドを抑える事が出来ます． また，イテレータはリストに比べてメモリを消費しません． リストはn個の要素を生成するのに対して，イテレータは1個のオブジェクトだけで済むからからです．

従って，走査する時はiteratorを使っほうが良いです．ただし， iteratorは走査中にiteratorのサイズを変更できず，index演算 (d['a']のような演算の事)が出来ません．

＊注意 この例ではprint文の計算量を含んでいません．

list comprehension

まずはいきなり例から

nums = [1,2,3,4,5]
sqr = []
for num in nums:
    sqr.append(nums**2)
print sqr # > [1, 4, 9, 16, 25]

この例では，numsの要素を2乗して新しいリストsqrに 追加しています．これはエレガントとは言えませんよね．

list comprehesionを使うとエレガントで高速になります．

nums = [1,2,3,4,5]
sqr = [num**2 for num in nums]
print sqr

これがlist comprehensionです．list comprehensionは エレガントにかけるだけでなく，ループがc言語で実行される ため高速です．またネストさせることも可能です．

ネストの例:

tpl = [ (i,j) for i in range(10)
                for j in range(i)
                    if i != i ]

は次のコードと同じ意味になります

tpl = []
for i in range(10):
    for j in range(i):
        if i != j:
            tpl.append((i,j))

list comprehensionのようにgeneratorã‚’yiledを使わず に生成することもできます．以下のように()で囲むことで generatorを生成できます．

nums = [1,2,3,4,5]
sqr = (num**2 for num in nums)
print sqr # <generator object <genexpr> at 0x10af870f0>

プログラマのための集合構成記法の解釈

Set-builder notation （集合構成記法） とは数学で扱う集合を表す記法で，条件や属性を示したりします．

例えば， S = {2x| x ∈ N, x^2 > 3} があるとします．これをプログラム記法(list comprehension)で簡単に表す事ができます． ここでの，xは変数で，x ∈ Nは変数xの範囲となります．次にx^2 > 3 は条件です．Sは自然数の範囲で，かつx^2が3より大きい条件を満たすxã‚’2倍した値の集合となります． 従って，この集合Sは

N = range(10000) #Nは自然数ですが，ここでは簡易化のため0 ~ 10000とします
S = [2*x for x in N if x**2 > 3]

と表現することができます． よくコンピュータサイエンスなどの本に出てくる 集合の記法もプログラム風に考えればしっくりくるかとおもいます．

まとめ

今日はThink Complexity のchap2とchap3で紹介されていた iterator(イテレータ)とlistの違い，generator（ジェネレータ）， list comprehension（リスト包括表記） についてまとめました．おまけとしてSet-builder notationについても 紹介しました．次回はchap3で勉強した計算量，二分探索法，ハッシュテーブルについて紹介します．

reference

• Think Complexity
• python docs
• List comprehension
• python doc:iterator
• python doc:generator