素数を求めるのは、プログラミングの入門でよく取り上げられる。その中でも有名なのは「エラトステネスの篩」であろうが、ここではもっとダサイ、愚直な方法を紹介する。あくまでもPythonからCythonにしたときの速度向上を計測するのが目的なのである。
Pythonのプログラム
ということで、CythonドキュメントのTutorialにある素数のプログラムを適当に変更を加えたものを紹介する。
関数primes(p_num) は、引数に求めたい素数の個数を与えて、最初のp_num個の素数のリストを返す。参考にしたプログラムにはコメントもいっぱいあったが、ここでは省略した。
# [Python] リストを利用した素数の計算
def primes(p_num):
p_list = []
n = 2
while len(p_list) < p_num:
for p in p_list:
if n % p == 0:
break
else:
p_list.append(n)
n += 1
return p_listprimes_list というモジュールの中に、primes(p_num)という関数が１つ入っているだけである。
In [1]: from primes_list import primes
In [2]: primes(10)
Out[2]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
In [3]: primes(10000)[-10:]
Out[3]:
[104677,
104681,
104683,
104693,
104701,
104707,
104711,
104717,
104723,
104729]
In [4]: timeit(primes(10000))
2.26 s ± 22.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)1万個の素数を、2.26秒で求めることができた。
Cythonのプログラム
このPythonの関数primesのCython版を用意した。
モジュール名をprimes_list、関数をprimes(int p_num)とすることで、Python版と同じにすることにして、Python版の入れ替え版となるようにした。
# [Cython] リストを利用した素数の計算
def primes(int p_num):
p_list = []
cdef int n = 2, p
while len(p_list) < p_num:
for p in p_list:
if n % p == 0:
break
else:
p_list.append(n)
n += 1
return p_list追記したのは、変数の型宣言だけである。
リストの各要素は色々な型で良いため、リストp_list はそのまま。
簡単なので、setup.py については省略。
コンパイルし、ipython3で実行してみた。
In [1]: from primes_list import primes
In [2]: primes(10)
Out[2]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
In [3]: primes(10000)[-10:]
Out[3]:
[104677,
104681,
104683,
104693,
104701,
104707,
104711,
104717,
104723,
104729]
In [4]: timeit(primes(10000))
185 ms ± 533 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)2260/185 = 12.2 倍速になった。一応10倍は超えた。
今回は、リストはそのまま残したが、次回はリストを他のものに置き換えてみよう。
＃人気の記事
＃タグ
