イテレータ,ジェネレータ,リスト包括表記と集合構成記法
イテレータ,ジェネレータ,リスト包括表記と集合構成記法
私は今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)するとき, 主に2つの方法があります.
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
で勉強した計算量,二分探索法,ハッシュテーブルについて紹介します.