Pythonを高速化する方法
Pythonで計算の高速化といえばNumPyやCythonなどが有名だと思いますが、それらを使うには色々と覚えることがあってすぐに使えるようにはなりません。特にNumPyは使いこなせれば非常に強力ですが、学習コストもかなり高いです。
実はPythonの標準ライブラリの中に超お手軽に高速化が実現できる関数が用意されています。それがメモ化を行うためのlru_cacheという関数です。
lru_cacheを使ったメモ化
メモ化の意味はおいといて、とりあえずどうやってメモ化するのかを見てみましょう。
効果をわかりやすくするために、再帰を使ったフィボナッチ関数を使います。
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
from functools import lru_cache
@lru_cache(maxsize=1000)
def fib_memoized(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
やることはlru_cacheをインポートして関数の前に@lru_cacheというデコレータを置くだけです。
maxsizeではキャッシュのサイズを指定します。
では、比較してみましょう。
%timeit [fib(i) for i in range(30)]
1 loop, best of 3: 715 ms per loop
%timeit [fib_memoized(i) for i in range(30)]
The slowest run took 149580.25 times longer than the fastest. This could mean that an intermediate result is being cached.
1 loop, best of 3: 5.37 µs per loop
メモ化をすると最初の１回目には時間がかかっていますが、２回目以降は速くなりこの例では100,000倍以上速くなっています。
メモ化ってなに
メモ化というのは関数型言語でよく使われる方法なのですが、早い話が一度計算した戻り値を覚えておくという方法です。つまり、すでに計算したことのある引数を受け取った場合には計算をしないでメモに書いてある戻り値をそのまま使うということです。（メモの実装にはいくつか方法がありますが、代表的なのは引数をキーとする辞書を使う方法です。）
いわばキャッシュなのですが、関数とは別にキャッシュした値を残すのではなく関数自体にキャッシュする機能を持たせることをメモ化と呼びます。
メモ化以外の高速化の方法
他にも色々な高速化の方法があります。
特にNumbaはlru_cacheと同じぐらい簡単に利用できるので、また別の記事で紹介したいと思います。
数値計算ライブラリ
JITコンパイラ
メモ化に関連する豆知識
なぜメモ化はあまり使われていないのか
実態はよくわかりませんが、記事を書いた時点ではQiitaで「Python "メモ化"」で検索すると14件だけでした。
なぜ関数型言語以外ではあまり使われていないかというと、二つの原因が考えられます。
一つは高速化の代償としてメモリを大量に消費するということ。
もう一つは、メモ化を行うためには「引数が同じであれば戻り値が同じ」という条件が必要だということです。別の言葉で言えば、関数の中での計算は状態に全く依存しないということです。
関数型言語では関数はこの条件を満たすことを基本としていて、またこれを強制するための仕組みを備えている言語もあります。この「引数が同じであれば戻り値が同じ」であることを参照透過性といいます。
参照透過性のこれまでとこれから
参照透過性のメリット
- 状態の変化を追跡する必要がなくなるのでソースコードの見通しが良くなる。
- 同じ値を再計算しない仕組みを利用できる。（メモ化など）
- どこで計算しても同じ結果になるので分散処理に適している。
参照透過性のデメリット
- 一般的にはメモリを多く消費する。（値を上書きできない仕組みを使っているため、新しい値ができるたびにメモリを消費する。）
- 参照透過性を守るためには、プログラマの頭の使い方を大きく変える必要がある。
おそらくこの「メモリを多く消費する」というデメリットが、これまで参照透過性のあるプログラミングが行われてこなかった理由じゃないかと思います。そもそも関数型言語以外では参照透過性があまり考慮されていないので、参照透過性を守るための支援機能がありません。
ところが、最近はメモリが十分すぎるほどあるケースが増えてきているのでメリットが活きるようになってきています。分散処理による「スケールアウト」を実現するのも参照透過性が前提となっています。計算を実行する度に別のマシンの状態を知らないといけないなら、マシンが何台あってもパフォーマンスは出ませんよね。
ムーアの法則が限界に近づいてきている今、ますます並列処理・分散処理が進んで行くはずです。今後は参照透過性を意識したプログラミングの重要性が高まってくると思います。
参考リンク：
functools.lru_cach — Python 3.6.0 ドキュメント
どうすればPythonをJuliaと同じくらい速く動かせるのか？ : 様々なやり方で計算の高速化を図る | プログラミング | POSTD
メモ化 - Wikipedia
参照透過性 - Wikipedia