【Cython】Pythonの高速化に挑戦！

# はじめに
普段、Pythonを触っていて処理がもうちょっと速くなればなぁとことありませんか？

自分は、多次元ベクトルの類似度を計算する際に概算で50時間ということがありました。そこで、書きやすいPythonと処理が速いC言語を合わせたCythonに興味を持ったという感じです。

この記事では、Cythonを簡単に触れるという点を重視して説明したいと思います。
もっとこうしたら速くなるっていうのがあれば、コメントお願いします。

# 導入
今回は、jupyterを使っていこうと思います。

jupyterにはマジックコマンドと言われる(%や%%から始まる)コマンドがいくつか存在する。その中に、Cythonをコンパイルすることができるコマンドがあります。jupyter有能。

# 環境

* OSX
* jupyter ver4.2
* Cython ver0.26.1

# 実際に触ってみる
## フィボナッチ数列
よくあるフィボナッチ数列で簡単にCythonに触れてみます。

まずは純pythonでの実装。
jupyterのマジックコマンドを使って時間計測する。

<img width="1245" alt="スクリーンショット 2017-11-19 23.37.53.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/5126109d-7971-cae6-f725-3a09fe40979e.png">


これがCythonを使ってどのくらい速くなるのかというのが気になるとこです。

<img width="1261" alt="スクリーンショット 2017-11-19 23.41.55.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/c1b3c7ee-f27a-d5f5-3a57-37d04f8b85b0.png">

まず、Cythonを使う上でJupyter上で```%load_ext Cython```を実行します。

そして、Cythonでコンパイルするためには```%%cython```というマジックコマンドを宣言したセルで実装します。

ポイントはcdefによる静的な型宣言です。計算で用いてるa,bの型宣言はもちろんですが、for文で用いるiにも宣言をするのが重要なようです。

たった、これだけで16.5msという速さになりました。


次に、もう少し具体的な計算でCythonを触っていこうと思います。

## コサイン類似度
フィボナッチ数列より少し複雑な計算で検証していきます。

対象のデータは、1ユーザーあたり100次元のベクトルを持つデータとします。これを5000ユーザー×1000ユーザーのデータ量に対して計算します。

<img width="1102" alt="スクリーンショット 2017-11-20 0.00.50.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/7d6783e8-6d9a-6f9b-d16b-5e24fa5bf9c6.png">

フィボナッチ数列同様、純Pythonでの実装から見ていきます。

### 純Python

リストにインデックスでアクセスしたりと、かなり雑な実装になっていますが気にしないでください。

<img width="1100" alt="スクリーンショット 2017-11-20 0.16.45.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/be04524c-dbdc-62c2-779c-be3ee1829c8a.png">

このrun2関数を実行すると、

<img width="1102" alt="スクリーンショット 2017-11-20 0.26.33.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/53bf71bc-1fdd-a759-cf57-a333d8dfe706.png">

この計測時間がベースラインになります。

### Python + Cython
cdefで静的な型宣言したバージョン。
listで宣言するとappendが速くなったりするようです。

Cythonでコンパイルした関数でもdefで宣言しているなら、Pythonから呼び出すことができます。
なのですが、あえて関数wrap1でラップしています。


<img width="1110" alt="スクリーンショット 2017-11-20 0.39.18.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/3fa95a10-76a7-465c-dec0-11d6759f4c16.png">

実行時間は以下です。

<img width="1100" alt="スクリーンショット 2017-11-20 0.49.08.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/d1f70b07-be98-7259-35c8-4bc2b3fbaf9e.png">

40秒ほど縮まりました。思ったほど、速くなりませんでしたね、、。

少し最適化しようと思います。

### Cython 最適化①
最適化の1歩目として、関数のくくりだしやってみます。

def関数内ではPythonオブジェクトが介入するため、遅くなるようです。なので、cdef関数を使ってみます。静的な型宣言ではなく、関数の宣言で使います。

cdef関数はPythonから呼び出すことができなくなります。ですが、計算にPythonオブジェクトが介入しなくなるため処理が速くなようです。

<img width="983" alt="スクリーンショット 2017-11-20 1.09.23.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/3af327c8-8c8e-d7f8-b246-a84a35574ea4.png">

<img width="935" alt="スクリーンショット 2017-11-20 1.10.30.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/516dde46-2774-22eb-ce10-49347ade1c45.png">


今回は、単純な計算処理(乗算,除算)をcdef関数でくくりだしてみました。
cdef関数はCython内のdef関数から呼び出すことが可能です。

たったこれだけ、本当に速くなるのか、、。

<img width="935" alt="スクリーンショット 2017-11-20 1.11.15.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/a062e79b-097f-3f1a-b29f-88061782ac0f.png">

だいぶ速くなった。

### Cython 最適化②
今度は、cpdef関数を使ってみます。cython内ではcdef関数はCython内のdef関数から呼び出せますが、Pythonからは呼び出すことができません。一方、Cython内のdef関数はPythonから呼び出すことができます。

そうなると、cdefで定義した関数に対してPythonから呼び出すことができるCython内のdef関数が１つは必要になります。

いちいちラッピング用の関数を用意するのは面倒ということことから、cpdef関数が便利になります。
cpdef関数は、cdef関数とdef関数を混ぜたような関数だそうです。

ということで、今まで分けてたcython内のdef関数とcdef関数をcpdef関数にまとめてみます。

<img width="943" alt="スクリーンショット 2017-11-20 1.35.55.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/0e14a26b-7a47-df92-57fd-74033d219b07.png">

実行結果が以下。

<img width="941" alt="スクリーンショット 2017-11-20 1.44.35.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/ca3b6863-33c1-257c-ed7d-b322e555f2ad.png">


期待が外れましたね。しかし、Python+Cythonと同じ実装でもcpdef関数での実行の方が多少速くなっています。このことから、cpdef関数の方がCython内def関数よりもアクセスが速いのかもしれません。

ということで、最後にcpdef関数での宣言とcdef関数のくくりだしをやってみます。

### Cython 最適化③

<img width="934" alt="スクリーンショット 2017-11-20 1.48.34.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/02de0ae0-b09d-ac5a-2a7d-fa3cabc9a539.png">

実行結果が以下。

<img width="936" alt="スクリーンショット 2017-11-20 1.49.34.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/0693e46d-a71a-d79f-025a-a910390adb88.png">

若干、変わりましたけど誤差ですかね。
cpdef関数は、戻り値と引数にも静的な型宣言が行えるためdef関数より速くなりそうな気がしてたんですが、、、。

### Cython 最適化④
Cythonでは、C言語のライブラリを使うことができます。
コードを見直してみるとnumpyを使っている部分があります。pythonのライブラリをC言語のライブラリに変えてみたら速くなるのではと思いやってみました。

<img width="937" alt="スクリーンショット 2017-11-20 1.54.18.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/29552df9-7eba-8f12-c921-d7d1fcae6117.png">
<img width="939" alt="スクリーンショット 2017-11-20 2.02.10.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/6b12f683-c9a3-368b-6ab4-ff16780d32a4.png">

実行結果が以下。

<img width="938" alt="スクリーンショット 2017-11-20 2.03.03.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/d59a16ec-ee5b-2a74-1c31-6836a5284b06.png">

ちょっと速くなった。できるだけC言語のライブラリを使った方がいい感じですね。

### Python + Cython + 並列処理
試しに、このコードで並列処理してみました。
ちなみにMacbook Proなので1コア2スレッドです。
<img width="947" alt="スクリーンショット 2017-11-20 23.08.42.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/471b6cc9-8c0c-be06-d720-ad084b1e557e.png">


<img width="934" alt="スクリーンショット 2017-11-20 2.07.28.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/994dfb30-e8f9-78ca-7c58-f517c3875834.png">

順調に速くなりましたね。

### 追記(11/20)
コメントいただいたので、C言語ライブラリを使った実行結果と除算に関するコンパイラディレクティブを追加した実行結果を追加します。

#### pow関数
cdef関数でc_powとしていたのですが、これを```from libc.math import pow```でやってみました。

<img width="934" alt="スクリーンショット 2017-11-20 22.31.45.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/58f5cab6-0faa-afa5-5fa3-c21c5c8b29f9.png">
<img width="933" alt="スクリーンショット 2017-11-20 22.32.08.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/06388ef4-3993-eae4-1402-015df802844e.png">
<img width="937" alt="スクリーンショット 2017-11-20 22.33.30.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/eda1d651-fc7d-9f88-b875-4c89dee88b72.png">

やはり、pythonのライブラリからC言語のライブラリに変えたというのが上記では大きかったことがわかりました。

#### cdivision=True
つぎに、コンパイラディレクティブで```#cython: cdivision=True```を追加したものです。
コンパイラディレクティブとは```Cython のコードの挙動に影響を及ぼす命令```というふうに公式ドキュメントに書いてありました。

```#cython: cdivision=True```の効果としては、

```
False にセットすると、Cython は C の型に対する除算・剰余演算子に関 する仕様を、(被演算子間の符号が異なる場合の振る舞いが異なる) Python の int の仕様に合わせ、除算する数が 0 の場合に ZeroDivisionError を送出します。この処理を行わせると、速度に 35% ぐらいのペナルティが生じます。 True にセットすると、チェックを 行いません。
```

と書いていありました。

<img width="944" alt="スクリーンショット 2017-11-20 22.44.08.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/1a00b111-8df9-63c1-af05-f575defaa06a.png">
<img width="947" alt="スクリーンショット 2017-11-20 22.44.19.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/618ed579-fb9d-d017-8ba4-bd08dc8286e6.png">
<img width="939" alt="スクリーンショット 2017-11-20 22.44.27.png" src="https://qiita-image-store.s3.amazonaws.com/0/148317/2791bbac-403d-e4d4-2474-5e0c322246f3.png">

最適化④に比べて1秒ほど縮みました。
cythonを使う上でコンパイラディレクティブにも注目してみると良いかもしれません。
勉強になりました。

# おわりに

まとめるとこんな感じです。

| | 純Python | Python+Cython |最適化|C言語ライブラリ|Python+Cython+並列処理|
|:-----------:|:------------:|:------------:|:------------:|:------------:|:------------:|
|Time         | 1min56s   | 1min14s |9.96s |6.77s|3.64s|
|向上率      |0%|43%|85%|90%|97%|

割と速さを実感できる結果になりました。

このようにjupyterで簡単にcythonを使えることが伝わったと思います。

この最適化に関しては、自分なりに試行錯誤した結果なのでこれが必ずしも正しいというわけではないのであしからず。

高速化の手助けに少しでもなればと思います。