Variable Annotation と Cython でお手軽高速化

みなさん Cython 使ってますか？私は使っていません.

というのも次の理由があったからです.

- コンパイルが面倒...
- C じゃなくて Python が書きたいんだけど...
- Python のコードを実行不可にしたくない or デコレータが見にくい...

これらのうち上記2つはこれまでも解決されていました.

- IPython の Cython Magic を使う
- Pure Python Mode を使う

 最後の一つに関しては先日 Cython 0.27 によって解決されました。

- Variable Annotation を使う

Python は v.3.5 より Type Hints ([PEP 484](https://www.python.org/dev/peps/pep-0484/)) が追加され, v.3.6 より Variable Annotation ([PEP 526](https://www.python.org/dev/peps/pep-0526/)) が追加されました.

そして, 現在最新版である Cython 0.27 より Variable Annotation のサポートが開始されました.

従ってほぼ純粋な Python コードを Cython で適切にコンパイルすることができるようになりました.

ということでどのようにコードを記述していくのか紹介したいと思います. なお, この記事では Cython に深く突っ込まず, 型指定のみ行います.

## 環境

```
- Manjaro Linux
- Python 3.6.2
- Cython 0.27.2
- IPython 6.2.1
```

Variable Annotation を使う以上, Python3.6以上の環境が必要となります.

## Type Hints と Variable Annotation

詳しくは Document を読んでください.

ここでは概要のみ説明します.

Type Hints は以下のコードのように関数の引数と戻り値に型を指定します.

```python
def greeting(name: str) -> str:
    return 'Hello ' + name
```

これだけです.

今回指定した型はインタープリタには無視されます. 従ってパフォーマンスにはなんの影響も与えず, mypy 等によって静的解析するときにのみ有効となります.

次に Variable Annotation です.

```python
primes: List[int] = []

captain: str  # Note: no initial value!
```

1つめは変数 primes を空リストで初期化しつつ int 型のみが入るリストであることを宣言します.

2つ目のように初期化せず型のみを定義するような使い方もでき, これらも Type Hints 同様インタープリタに無視されます.

## Cython

### チュートリアル

ここから本題に入ります.

以下のコードは Jupyter のように IPython Kernel が動作する環境を想定していますが, 普通にコンパイルしても動作すると思います. (未検証)

なお, サンプルコードは [Cython のチュートリアル](http://cython.readthedocs.io/en/latest/src/tutorial/cython_tutorial.html)を改変しています.

```python
"""Fibonacci Fun"""
# python only
def fib(n):
    """Print the Fibonacci series up to n."""
    a, b = 0, 1
    while b < n:
        print(b)
        a, b = b, a + b

    
# using cython
%load_ext Cython
%%cython -a
import cython as c
def fib_c(n: c.int):
    a: c.int = 0
    b: c.int = 1
    while b < n:
        print(b)
        a, b = b, a + b

    
"""Primes"""
# python only
def primes(kmax):
    p = [0] * 1000
    result = []
    if kmax > 1000:
        kmax = 1000
    k = 0
    n = 2
    while k < kmax:
        i = 0
        while i < k and n % p[i] != 0:
            i = i + 1
        if i == k:
            p[k] = n
            k = k + 1
            result.append(n)
        n = n + 1
    return result

  
# using cython
%%cython -a
import cython as c
def primes_c(kmax: c.int):
    p: c.int[1000] = [0] * 1000
    result = []
    if kmax > 1000:
        kmax = 1000
    k: c.int = 0
    n: c.int = 2
    while k < kmax:
        i: c.int = 0
        while i < k and n % p[i] != 0:
            i = i + 1
        if i == k:
            p[k] = n
            k = k + 1
            result.append(n)
        n = n + 1
    return result
```

Type Hints や Variable Annotation で与える型が Cython のオブジェクトになっただけで特に大きな変更はないことがわかると思います. なお, Python の int, float, bool 等を指定した場合, 内部で C の型 int, double, bint などに変換してくれるそうですが, Cython のオブジェクトを使って明示したほうが高速化できました.

また, Cython の公式にも書かれていますが, 無闇に型を定義するのではなくボトルネックとなっているところを中心に活用していくと良いでしょう. Cython の Cell Magic のオプション -a は行ごとにプロファイルをしてくれるのでそれを見ながら型定義していくのが良さそうです.

%timeit を用いて測定した速度(ms)は以下のようになりました. 

なお, Cython without type とは python only のコードをそのままコンパイルしたものです.

|      関数       | CPython | Cython without type | Cython with type |
| :-----------: | :-----: | :-----------------: | :--------------: |
|   fib(1000)   |  1.29   |        1.15         |       1.66       |
| primes(10000) |  78.4   |        48.6         |       2.56       |

fib は print 関数がネックになっており, 期待する速度は出ませんでした. Cython 公式でもIOのネックを高速化するのに不向きとあるので妥当な結果だと思われます.

一方 primes は型指定の効果が顕著です. このように適切に指定してやるだけで圧倒的な速度を出すことができます.

### Julia lang. との比較

Julia lang. を知らない方は[こちら](https://julialang.org/)をざっとお読みください.

コードは[こちら](http://bicycle1885.hatenablog.com/entry/2014/12/23/170745)から拝借しましたNクイーン問題です. およそ3年前の記事で Julia の情報としてはかなり古いので Julia 自体について知りたい場合は必ず最新版(10/25時点でv.0.6.1)を参照するようにしてください.

```julia
function solve(n::Int)
    places = zeros(Int, n)
    search(places, 1, n)
end

function search(places, i, n)
    if i == n + 1
        return 1
    end

    s = 0
    @inbounds for j in 1:n
        if isok(places, i, j)
            places[i] = j
            s += search(places, i + 1, n)
        end
    end
    s
end

function isok(places, i, j)
    qi = 1
    @inbounds for qj in places
        if qi == i
            break
        elseif qj == j || abs(qi - i) == abs(qj - j)
            return false
        end
        qi += 1
    end
    true
end
```

```python
%%cython
import cython as c
def solve(n: c.int):
    places: c.int[:] = [-1] * n
    return search(places, 0, n)


def search(places, i: c.int, n: c.int):
    if i == n:
        return 1

    s: c.int = 0
    j: c.int
    places: c.int[:]
    for j in range(n):
        if isok(places, i, j):
            places[i] = j
            s += search(places, i + 1, n)
    return s


def isok(places, i: c.int, j: c.int):
    qi: c.int
    qj: c.int
    places: c.int[:]
    for qi, qj in enumerate(places):
        if qi == i:
            break
        elif qj == j or abs(qi - i) == abs(qj - j):
            return False
    return True
```

単位は ms です.

|  N   | Julia v.0.6.0 | CPython 3.6.2 | Cython 0.27.2 |
| :--: | :-----------: | :-----------: | :-----------: |
|  11  |      65       |     3,000     |      232      |
|  12  |      195      |    18,100     |     1,310     |
|  13  |     1,150     |       -       |     7,920     |

ここでの CPython は実行時に Cell Magic を除外したものです. Cython を用いるとコードを非破壊的な変更を加えることなく高速化することができることがわかると思います.

ただしそれでもこのケースでは Julia には敵いませんでした. Cython もなかなかいい速度を出してると思いますが, Julia のほうが数枚上手ですね.

もちろん Python には Numba の jit もあり今回のコードに適用すると Julia に肉薄する速度を出せました. しかし Numba は現在, 全てのコードに対して有効ではなく, 使ったからといって速くなる保証はありません.

Python を高速化しようとしてあれこれ試すより素直に Julia を使うほうが余計な労力を必要としないので魅力的ですね.



## まとめ

Variable Annotation を用いることで Python の記法を損なうことなく Cython の型定義による恩恵を受けられることがわかりました. Python の中に別言語を書くというのではなく, Python の自然なコードで高速化できるのでかなり敷居も低くなると思います.

速いコードを書きたい場合には Python は不向きですが, 目的は別にあり, ただその中でもある程度の速度を出したいということがあると思います. その際に今回のような型定義のみを用いた Cython を使ってみるというのは一つの手です.

また, Julia lang. のような Python のようにかけて C 並の速度が出せる言語もあるので, 目的に合わせた言語選択ができると幸せになれそうです.

Julia はいいぞ.

## 参考

Cython について同じコンセプトで簡単に説明してあるので公式ドキュメントと合わせて読むとよいと思います.

[深入りしないCython入門](https://qiita.com/pashango2/items/45cb85390193d97523ca)

[深入りしないCython入門-2-](https://qiita.com/pashango2/items/fed0a1c06c7077639edc)