Python
memoization
OSS
メモ化
KurumiPy

Pythonの処理を高速化するメモ化ツール「KurumiPy」を作った

Pythonでメモ化を簡単に適応することができるツール「KurumiPy」を開発して、OSSとしてGitHubに公開しました。

プログラムを再実行してもキャッシュを利用することができます。

https://github.com/FujitsuLaboratories/kurumipy

そもそもメモ化って何?

フリー百科事典『ウィキペディア(Wikipedia)』(2018年10月5日時点)には以下のように書かれています。

メモ化(英: Memoization)とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン(関数)の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる(必ずしも高速化のためだけとは限らない)。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。

関数において、同じ入力データ(引数の値)に対して、同じ戻り値になる処理を何回もするのは無駄です。

そこで、1回目の関数の処理の結果をキャッシュ(保存)しておいて、2回目以降は、その関数内の処理はせずに、キャッシュしておいたデータをそのまま返すということをします。

これで、同じ処理を何回もすることを省略することができるため、その分、処理が高速になりますよ!といったものです。

なぜわざわざKurumiPyを作ったの?

そんなに処理が重くないシステムを開発している場合は、メモ化の必要性は低いです。

しかし最近は、AI!AI!データ分析!データ分析!AI!!データ分析!!と世の中で叫ばれまくっており、今の流行では、Pythonを使って、大量のデータ処理をすることが増えています。

例えば、下図のように、大量のセンサデータを入力として、いくつものデータ処理をするシステムがあるとします。

KurumiPy 説明図

このような時に、ほんのちょっとプログラムを変更してみて、プログラムを実行して出力結果を見ようとした場合、プログラムを書き換えていないデータ変換処理がある関数についても、再度実行されています。

例えば、上図の「データ変換処理C」の関数内のプログラムを変更して再実行する場合は、「データ前処理」と「データ変換処理A」と「データ変換処理B」の関数の部分については、前に実行した結果を再利用しても、結果は同じです。

このような時に、メモ化によってキャッシュしていたデータを再利用することで、「データ変換処理C」より前の処理を省略することができ、出力結果を素早く出力することができるようになります。

少量のデータの場合は、そこまで必要性はないかもしれませんが、入力データが数Mバイト以上になってくると利用価値が出てきます。

私はとあるシステムを開発していたのですが、そのシステムではデータ処理をして、結果を出力するまでに40秒以上掛かっていました。

しかし、KurumiPyでメモ化を適用することで、結果を出力するまでに掛かる時間が1秒以内になりました。

データ分析処理をするシステムを試行錯誤で開発しているときは、変数の値をちょっとだけ変更して、再実行して結果を見たいということがあります。

そのような時、結果を出力するまでに、毎回何秒も掛かっていたら、大きなストレスになります。

そういう時に、KurumiPyが本領発揮します。

そもそもDBを利用してキャッシュすれば…

実際、DB(データベース)をうま〜いこと使って、最適化したら、同じ処理を何回もする必要がありません。

だったら、メモ化ツールはいらないじゃん!となるかもしれませんが、仮説検証の開発フェーズやプロトタイプを作るときは、DBをわざわざ用意するのが面倒です。

また、DBを用いたとしても、うま〜いこと最適化することが難しい場合があります。

そういう時に、メモ化が欲しい!となってくるのです。

欲しい!となって来たので、KurumiPyを作ったのです。

KurumiPyの使い方

サポートしているPythonのバージョンは3.xです。

事前に、依存パッケージの「fasteners 0.14.1」を例えば以下のようにして、インストールしてください。

pip install fasteners==0.14.1

適用したいプロジェクトに、GitHubの「KurumiPyリポジトリ」にある「memoization」フォルダをコピーし、モジュールをインポートします。

そして、以下のようにして、メモ化を適用した関数の前にデコレータを書きます。

from memoization.memo_decorator import memo

@memo
def your_function(n):
    # ...

これだけでメモ化を適用することができます。

メモ化でキャッシュしたファイルは、以下のフォルダに格納されます。そのため、プログラムを再実行した時もキャッシュを利用できます。

[./memoization/memocache]

メモ化を適用した関数内のコードや依存する変数の値が変わった時は、関数の処理の振る舞いが基本的に変わるため、自動でキャッシュを破棄する仕組みになっています。

それ以外の時は、上記フォルダにキャッシュがどんどん溜まっていくため、必要があれば、上記フォルダのキャッシュファイルを適宜削除してください。

制約事項

  • 純粋関数のみ対応
  • 適用する関数の引数はstring type, numeric typeのみ対応(list type, dict type, set type, file objectsなどは対応していませんので、適宜string typeに変換処理などしてください。)
  • 複数スレッドの相互再帰関数(食事する哲学者の問題)には、対応していません。

その他設定

Python3.3では、デフォルトでstr, bytes, datetime objectsのハッシュでsaltが有効になっています。

そのような場合は、KurumiPyを適用したPythonのプログラムを実行する前に、以下のようにしてsaltを無効にする必要があります。

# bashの場合
export PYTHONHASHSEED=0

# Command promptの場合
set PYTHONHASHSEED=0

なぜ「“Kurumi”Py」という名なの?

kurumiは「クルミ」が由来です。

本当かどうかはわかりませんが、クルミを食べると記憶力が上がると言われているので、メモ化とマッチしていると考え、「kurumi」にしました。

KurumiPyを利用して、賢く効率良く、開発しましょう!