Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

 卒論で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秒である。積分の結果をキャッシュに保存すれば、実行時間を大きく短縮できることも期待できる。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away