Python
python3
Cython
高速化
Numba

🍺Python3でLRUキャッシュを用いてプログラムを高速化

 卒論でPythonのプログラムを回していたが時間がかかりすぎてうんざりしていた。Python初心者の僕がいろいろ調べていたら高速化のために以下の二つに関するポストが頻繁に見られた。

 しかし、僕のプログラムに対してはこれらの高速化はそれほど効果はなかった。forで1万回、回したりするプログラムには効果が大きいっぽい。僕のプログラムはscipyの積分を多く回すようなプログラムで、積分の処理がボトルネックになっていると思われて効果は薄かった。

 そこで、lru_cacheというものを発見した。

LRUキャッシュ

 LRUとは、Least Recently Used の略である。メソッドのある引数に対する計算結果を保存しておき、後で同じ引数が与えられた時、計算結果を再利用するというものである。使い方はとても簡単で、ライブラリをimportしたあとに@lru_cacheと関数の頭にデコレータをつけるだけでよい.maxsize=Noneはキャッシュできる量を表している。

 例えば、ポアソン分布を計算するループに関する実験を行う。jupyterでは、%timeを実行するときつければ実行時間を計測してくれる。

from functools import lru_cache
# 上がうまく使えない場合、以下を使う(僕はうまくいかなかったのでこっちを使った)
# from functools32 import lru_cache 

@lru_cache(maxsize=None)
def poisson_probability_with_lru(n, t, lambda_poisson):
    return math.e**(-lambda_poisson * t) * (lambda_poisson * t)**n / math.factorial(n)

def poisson_probability_without_lru(n, t, lambda_poisson):
    return math.e**(-lambda_poisson * t) * (lambda_poisson * t)**n / math.factorial(n)

def test_with_lru():
    test_range = [10,20,30,10,20,30,40,50,60]*1000000
    count = 0
    for i in test_range:
        count += poisson_probability_with_lru(i, 10, 1)
    print count

def test_without_lru():
    test_range = [10,20,30,10,20,30,40,50,60]*1000000
    count = 0
    for i in test_range:
        count += poisson_probability_without_lru(i, 10, 1)
    print count

%time test_with_lru()
%time test_without_lru()

# ---------- 出力------------

253952.576403
CPU times: user 7.35 s, sys: 103 ms, total: 7.45 s
Wall time: 7.46 s
253952.576403
CPU times: user 28.9 s, sys: 509 ms, total: 29.4 s
Wall time: 29.1 s

 ポアソン分布がどのような計算かわからなくても、LRUキャッシュによって高速化されていることがわかると思う。LRUキャッシュを用いた場合では実行時間7.45秒で、LRUキャッシュを用いない場合では実行時間は29.1秒である。積分の結果をキャッシュに保存すれば、実行時間を大きく短縮できることも期待できる。

ポアソン分布については詳しくはこちら