ド素人がCythonによる高速化を試してみる

Pythonは普段から仕事で使っているものの、Cythonについては「なんかそういう亜種があるらしい」としか思っていなかったド素人(私)がちょっと触ってみた記録。
本記事は、素数判定処理の高速化を題材にしたCython入門となります。

サマリ

  • CythonはPythonのコードをそのまま流用できる
  • Cython自身のインストールもpipコマンド1発で可能
  • Pythonと比較して、優に10倍以上の高速化を実現することができる

環境

  • OS: Linux Mint 18.1 (この記事の内容はLinuxならほぼ共通)
  • Python 2.7.12

Cythonのインストール

1
2
3
4
$ pip install cython

$ cython -V
Cython version 0.28.2

これだけです。

Cythonとはそもそも何か

読み方は?

ググッててみたが、サイソンでいいらしい。

Cythonはなにをするもの?

細かいところは不正確かもしれないが、ざっくりと以下の理解をしている。

  • CythonとPythonは別言語。
  • ただし文法はほぼ共通。Cythonの文法はPythonの文法を拡張した形になっている。(従ってPythonのソースコードは、そのままCythonのコードとして成立する)
  • Pythonはインタプリタ型言語だが、Cythonはコードを事前にコンパイルすることができる。
  • Cythonで書いたモジュールはPythonにimportして呼び出すことができる。

大事なのはPythonコードを事前にコンパイルしてバイナリにしておける、ということ。
通常のPythonはインタプリタ言語であるからC/C++の様なコンパイル型の言語と比べて遅い。
処理時間のボトルネックとなる処理をCythonによって事前にコンパイルしておくことで、実行時の処理を省き速化する。

Cythonの拡張文法によって変数の型を指定することで、更なる高速化が可能。


Python vs. Cython

通常のPythonの場合

ソースコード

自然数 n を引数として受け取り、素数であれば True, 素数でなければ Falseを返す関数を定義する。
今は愚直に1より大きくnより小さい整数で割り切れるか否かのループを組む。
(偶数で割る必要ないとか、$\sqrt{n}$まででいいとかあるけど、ここではPythonとCythonの比較が問題なので、気にしない)

1
2
3
4
5
6
7
8
# prime_check.py
def is_prime(n):
i = 2
while i < n:
if n % i == 0:
return False
i += 1
return True

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/env python
# prime_main.py
from prime_check import is_prime

if __name__ == '__main__':
N = 6700417
is_prime = is_prime(N)

if is_prime:
print('%d is prime!' % N)
else:
print('%d is not prime!' % N)

実行時間

約370msでした。(i5-6500@3.2GHz)

1
2
3
4
5
6
$ time python prime_main.py 
6700417 is prime!

real 0m0.369s
user 0m0.369s
sys 0m0.000s

Cythonバージョン

ソースコード

Cythonのソースファイルの拡張子は.pyxになります。

1
2
3
4
5
6
7
8
9
# prime_check_cython.pyx
def is_prime_cython(unsigned int n):
cdef unsigned int i = 2
while i < n:
if n % i == 0:
return False
i += 1

return True
1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python
# prime_main_cython.py
from prime_check_cython import is_prime_cython

if __name__ == '__main__':

N = 6700417
is_prime = is_prime_cython(N)

if is_prime:
print('%d is prime!' % N)
else:
print('%d is not prime!' % N)

純Pythonとの実質的な差分は、is_prime_cython関数の引数 n とローカル変数 i に型情報を付与したのみです。
is_prime_cython関数内のローカル変数にはcdefというキーワードがついていますが、
これがあるとC言語の型を使って変数定義していることになります。

コンパイル

以下が最も簡便な方法のようです。

1
cythonize -i prime_check_cython.pyx

iオプションは “build inplace” の意で、カレントディレクトリにprime_check_cython.c と prime_check_cython.so が生成されます。
setup.pyを使用した方法が真っ当(?)なようです。
Basic setup.pyを参照。

実行時間

約28ms・・・ということで、純Pythonと比較して10倍以上高速化しました。
プロトタイプでPythonで組んだコードを、時間ないからとりあえず高速化して実機で動かしたい・・・みたいな時は使えそう。

1
2
3
4
5
6
$ time python prime_main_cython.py 
6700417 is prime!

real 0m0.029s
user 0m0.028s
sys 0m0.000s

ちなみに、型情報を付与しなくても cythonize でコンパイル可能ですが、その場合は約200msでした。
やはり型情報の付与は高速化に絶大に貢献するようです。