Cython(7) 素数のリストを求める


2022年 07月 28日

素数を求めるのは、プログラミングの入門でよく取り上げられる。その中でも有名なのは「エラトステネスの篩」であろうが、ここではもっとダサイ、愚直な方法を紹介する。あくまでも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_list

primes_list というモジュールの中に、primes(p_num)という関数が1つ入っているだけである。

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倍は超えた。

今回は、リストはそのまま残したが、次回はリストを他のものに置き換えてみよう。

< 前の記事へ 次の記事へ >