Pythonで素数生成

November 17, 2007 at 08:04 AM | View Comments

記録: [メモ]数学の記述ではやはりHaskellがPythonよりも上手ですが、変態的Pythonなら肉薄できそう と 4 TopCoder: Python - generatorで素数生成 が面白かった。

これらをみると僕はitertoolsのcountもifilterも知ってることは知ってるがうまく使えてないのが良く分かる。

itertools.count()は

>>> a=count(1)
>>> a.next()
1
>>> a.next()
2
>>> a.next()
3

のように次の整数を返すgeneratorです。

ちなみにgeneratorとはイテレータになってる関数で例のようにnextメソッドで次々に新しい値を返します。

ちなみにcountを自分で実装すると以下のようになります。return の代わりにyieldで値を返すのがポイントです。

>>> def mycount(i=0):
....     if not isinstance(i, int):
....         raise TypeError, 'an integer is required'
....     while True:
....         yield i #nextメソッドが呼ばれたときに返す値
....         i+=1
....
>>> m = mycount()
>>> m.next()
0
>>> m.next()
1
>>> m.next()
2
>>> m.next()
3
>>> m.next()
4

イテレータなのでfor構文でまわすことも出来ます。

#例
>>> for i in mycount():
....     if i>10:break
....     print i,
....
....
0 1 2 3 4 5 6 7 8 9 10

countにifilterをかけることによって特定の数字を抜かすことができるgeneratorを試しに作ってみます。

#例
>>> a = count(1)
>>> a = ifilter(lambda x:x!=4, a) #4以外を通すフィルター
>>> a.next()
1
>>> a.next()
2
>>> a.next()
3
>>> a.next() #4はフィルターを通らなかったので次の5を返す
5

ifilterは遅延評価なので 2行目で4以外の整数のリストを作っているのではなく、nextメソッドが呼ばれるたびに4じゃないかどうかを評価しています。

つまり、 4 TopCoder: Python - generatorで素数生成 の中にある以下は

>>> def sieve():
...     g = count(2)
...     while True:
...         prime = g.next()
...         yield prime
...         g = ifilter(lambda x, prime=prime: x%prime, g)
...

これは

2行目で2,3,4,5,6...とnextメソッドで次々と整数を返すgeneratorを生成してgとする。

3行目で無限ループ

4行目でgの次をprimeという変数に入れる

5行目yieldでprimeを返す

6行目gをprimeで割ったら0にならないフィルターを追加したgeneratorに変更する。

となっています。つまり

1週目

primeは2

gは2で割ったら0にならない整数を返すgenerator

2週目

primeはg.next()で2で割っても0にならない2の次の整数ということで3

gは2で割っても、3で割っても0にならない3の次の整数を生成するgenerator

3週目

primeはg.next()で2でも3で割っても0にならない3の次の整数ということで4じゃなくて5

gは2,3,5で割っても0にならない5の次の整数を生成するgenerator

4週目

primeはg.next()で2,3,5で割っても0にならない5の次の整数ということで6じゃなくて7

gは2,3,5,7で割っても0にならない7の次の整数を生成するgenerator

と一巡するたびに増えていくフィルターを通るかどうかをg.next()するたびに計算しているわけですね。

再帰を避ける方法も含めて実にエレガンス。すばらしい。
categories: python
blog comments powered by Disqus
track feed ueblog