Pythonをいじってみた その2 アルゴリズムの改良

急に仕事が増え、時間がなくなってしまったのですが、
できる限り記事を増やしていきたいと思います。

今回は、前回の処理を改良してみたいと思います。

---

さっそく、プログラムリストから。

 1 #! c:/python27/python.exe
 2 
 3 import timeit
 4 
 5 def notFactor(x,a):
 6     return x % a != 0
 7 
 8 def PrimeNumber2():
 9     number_list = range(2,1000)
10     number_list.reverse()
11     prime_list = []
12     while len(number_list)>0:
13         a = number_list.pop()
14         prime_list.append(a)
15         number_list = filter( lambda x : notFactor(x,a), number_list)
16 
17     print "number\n"
18     print number_list
19     print "prime numbers are\n"
20     print prime_list
21 
22 
23 if __name__ == "__main__":
24     PrimeNumber2()

今回の変更点は、ラムダ式を使い、一括で要素の取捨選択をするfilterを使用していることです。
分かりやすいように、割り切れない場合に真になる関数を作りました。
ラムダ式がない場合、2で割る関数、3で割る関数と用意しなければならないのですが、
（関数の働きをするオブジェクトを作るなど）
ここでは、filterの呼び出しごとに、a（見つかった素数）で割る関数が定義しなおされることになります。

こうすることによって、内部のアルゴリズムはわかりませんが、
関数の戻り値が真になるものだけが残ります。
プログラムとしてもすっきりします。

実際、timeit関数を使って、10000未満の素数生成を10回繰り返した時間を計ってみました。
前回のプログラム
7.99秒
今回のプログラム
2.89秒
ということで、2倍以上はやくなりました。
いろいろな意味で、組み込みの関数は最適化されているのでしょう。
見た目にも、パフォーマンス的にも、
filterなどを積極的に使っていったほうがいいようです。