プログラムを高速化する手法の一つとしてメモ化がある。 これは、関数の返り値をキャッシュしておくことで、同じ呼び出しがあったときにそれを使い回すというもの。
今回は、メモ化でキャッシュした内容を補助記憶装置に永続化できる Python のパッケージとして percache を使ってみる。 キャッシュを補助記憶装置に永続化すると、その分だけ読み書きにはオーバーヘッドがかかる。 しかしながら、計算に多量の時間がかかる場合にはそれでもメリットがありそう。
ただし、先に断っておくと世間的にはほとんど使われていないパッケージなので実際に使うときは十分に検討した方が良い。 キャッシュの機構は、慎重にならないと不具合や脆弱性を生みやすいところなので、特に気をつけた方が良いと思う。 今回の動機としては、元々は似たようなパッケージを自分で書こうか悩んでいて、探したら API がいけてたので試してみたという感じ。
使った環境は次の通り。
$ sw_vers ProductName: Mac OS X ProductVersion: 10.13.6 BuildVersion: 17G65 $ python -V Python 3.6.6
下準備
まずは percache をインストールしておく。
$ pip install percache
標準モジュールの functools.lru_cache を使ったメモ化
percache の説明に入る前に、一般的なメモ化について扱っておく。
まず、補助記憶装置への永続化のないメモ化については Python の標準モジュールに実装がある。
具体的には functools.lru_cache を使うと簡単に実現できる。
サンプルコードを以下に示す。
このコードの中では add() 関数を @lru_cache() デコレータを使ってメモ化している。
add() 関数では a と b という二つの引数を足し算をして、その結果を返す。
それをメモ化しているということは、つまり引数の a と b が以前に呼び出した値と同じだったら、そのときの戻り値を使い回す。
また、関数の中では、実際に処理されたときと返り値が使い回されたときを区別できるように、デバッグ用の文字列を出力している。
#!/usr/bin/env python # -*- coding: utf-8 -*- from functools import lru_cache # add() 関数をメモ化する @lru_cache() def add(a, b): print('calculate') # 実際に処理されたことを確認するための出力 return a + b def main(): # メモ化された関数を二回呼び出す print(add(1, 2)) print(add(1, 2)) if __name__ == '__main__': main()
上記を保存して実行してみよう。
すると、関数は二回呼び出されているにも関わらず calculate という文字列は一回しか出力されていない。
これは、二回目の呼び出しは引数が同じなので戻り値が使い回されたことを示している。
$ python memoize.py calculate 3 3
ただし functools.lru_cache を使ったメモ化では、キャッシュが補助記憶装置に永続化されない。
そのため Python のプロセスが終了すると、主記憶装置にキャッシュしていた内容も揮発してしまう。
その証拠に、先ほどのプログラムを再度実行すると、同じ出力になる。
このとき、もしキャッシュしていた内容が補助記憶装置に永続化されているなら calculate という文字列は出力されないはず。
$ python memoize.py calculate 3 3
percache でキャッシュを永続化してみる
続いては今回の本題として percache を使ってキャッシュを補助記憶装置に永続化してみる。
使い方は percache.Cache のインスタンスを作って、そのインスタンスをデコレータとして使うというもの。
Flask 的な API になっている。
#!/usr/bin/env python # -*- coding: utf-8 -*- import percache # my-cache というファイル名でキャッシュを永続化する cache = percache.Cache('my-cache') # add() 関数をメモ化する @cache def add(a, b): print('calculate') return a + b def main(): import sys # 引数を整数として解釈して add() 関数を呼び出す result = add(int(sys.argv[1]), int(sys.argv[2])) print(result) if __name__ == '__main__': main()
上記を保存したら、同じ引数を使ってプログラムを何度か実行してみよう。
すると、同じ引数を使うと二度目以降は calculate という文字列が表示されない。
つまり、補助記憶装置に永続化されたキャッシュが使われていることが分かる。
$ python pmemoize.py 1 2 calculate 3 $ python pmemoize.py 1 2 3 $ python pmemoize.py 1 3 calculate 4 $ python pmemoize.py 1 3 4
percache の実装
基本的な使い方が分かったところで、続いては percache の実装について見ていこう。 このパッケージは一つのモジュールに収まるほどシンプルな作りになっている。
どのようにキャッシュの永続化が実現されているか確認しよう。
まず、先ほどの例を実行すると my-cache というファイルがカレントディレクトリにできているはず。
これが、永続化されたキャッシュ内容を保存するためのファイルになる。
$ ls my-cache
my-cache
$ file my-cache
my-cache: GNU dbm 1.x or ndbm database, little endian, 64-bit
中身を確認するために Python の REPL を起動しよう。
$ python
キャッシュの永続化は標準モジュールの shelve を使って実装されている。
次のコードを実行すると、キャッシュされた内容が確認できる。
>>> import shelve >>> with shelve.open('my-cache') as s: ... for key, value in s.items(): ... print(key, value) ... 936247610f625403ba55b32ab4dddfc6abd7c2ee 4 de71ece6a221c54c692400a6294839b2c02fd4f2:atime 1535584568.42677 936247610f625403ba55b32ab4dddfc6abd7c2ee:atime 1535584570.2073479 de71ece6a221c54c692400a6294839b2c02fd4f2 3
尚 shelve というモジュールは Python の辞書ライクなオブジェクトを補助記憶装置に永続化するための機能になっている。
12.3. shelve --- Python オブジェクトの永続化 — Python 3.6.6 ドキュメント
先ほど確認した内容から、いくつか分かることがある。 まず、辞書のキーとしてはハッシュと思われる値が使われており、それに対応する値にはメモ化した関数の計算結果が保存されている。 そして、それとは別に永続化した時刻と思われる内容についても保存されているようだ。
ちなみに辞書のキーとなる値については、ソースコードを確認したところ次のようなアルゴリズムで生成されていた。
まず、関数名と repr() した引数の内容を文字列として連結して UTF-8 でバイト列にエンコードする。
そして、その内容を SHA1 でハッシュ化する。
試しに add() 関数に 1 と 2 を渡した際のハッシュを手作業で生成してみよう。
>>> args = ''.join(['add', repr(1), repr(2)]).encode('utf-8') >>> hashlib.sha1(args).hexdigest() 'de71ece6a221c54c692400a6294839b2c02fd4f2'
上記が、先ほど確認した辞書のキーで、結果が 3 になっているものと一致していることが分かる。
バックエンドをオリジナルの実装に入れ替える
percache はキャッシュを永続化する部分をオリジナルの実装に入れ替えることもできる。 ちなみに、キャッシュを永続化する部分の実装を percache ではバックエンドと呼んでいる。 例えば、やろうと思えばクラウド上のストレージに永続化するバックエンドを書くこともできるはず。
以下にサンプルコードとして、保存されるキャッシュの件数を制限できるバックエンドを書いてみた。
#!/usr/bin/env python # -*- coding: utf-8 -*- from collections import OrderedDict import shelve import percache class LimitedSizeBackend(OrderedDict): """永続化する結果の数を制限したバックエンド""" def __init__(self, filename, limit_size=-1): self._filename = filename self._limit_size = limit_size self._shelve_dict = shelve.open(self._filename) self._load() self._check_size() def _load(self): """shelve から永続化されているデータを読み込む""" self.update(self._shelve_dict) def _check_size(self): if self._limit_size < 0: # サイズ上限が負なら何もしない return # サイズ上限に収まるように一番古い要素を削除する # NOTE: percache は 1 つのメモ化に 2 つ要素を使う while len(self) > self._limit_size * 2: # FIFO (Queue) self.popitem(last=False) def __setitem__(self, key, value): """要素の追加があったとき呼ばれる特殊メソッド""" super(LimitedSizeBackend, self).__setitem__(key, value) self._check_size() def _save(self): """shelve にデータを書き込んで永続化する""" # 一旦既存のデータをクリアする self._shelve_dict.clear() # 現在のデータを書き戻す self._shelve_dict.update(self) # 永続化する self._shelve_dict.sync() def sync(self): """shelve として振る舞う (ダックタイピング) ために必要""" self._save() def close(self): """shelve として振る舞う (ダックタイピング) ために必要""" self._save() # サイズ上限が 1 のバックエンドを用意する backend = LimitedSizeBackend('limited-cache', 1) # バックエンドを設定してキャッシュオブジェクトを作る cache = percache.Cache(backend) # add() 関数をメモ化する @cache def add(a, b): print('calculate') return a + b def main(): import sys # プログラムの第一引数と第二引数を整数として add() 関数に渡す result = add(int(sys.argv[1]), int(sys.argv[2])) print(result) if __name__ == '__main__': main()
サンプルコードではキャッシュのサイズを 1 に制限している。
これはつまり、直近一件の返り値だけがキャッシュされるということ。
上記を保存したら色々な値を入れて動作を確認してみよう。 同じ値を入れる限りはキャッシュの結果が使われるものの、別の値を入力すれば忘却することが分かる。
$ python limited.py 1 2 calculate 3 $ python limited.py 1 2 3 $ python limited.py 1 3 calculate 4 $ python limited.py 1 3 4 $ python limited.py 1 2 calculate 3 $ python limited.py 1 2 3
ちなみに、キャッシュのアルゴリズムでは、際限なくサイズが膨れ上がらないような仕組みを入れることが非常に重要となる。 具体的には、キャッシュする件数を制限したり、あるいは一定時間使われないものを消去するといった内容が考えられる。 そういった仕組みがないと、キャッシュによってシステムのリソースを使い尽くす可能性がある。
また、ユーザからの入力を元にキャッシュしているときにそうした仕組みがないと、意図的にリソースを枯渇させることも可能になってしまう。 これは DoS (Denial of Service) 攻撃への脆弱性になる。 ここらへんの制約は、主記憶装置よりも補助記憶装置の方がゆるい。 ただし、キャッシュの保存先が補助記憶装置だとしても、実際に使うときは主記憶装置の上に展開されることを忘れてはいけない。
読み書きがある毎に永続化する
percache は、デフォルトだと明示的に Cache#sync() メソッドや Cache#close() メソッドを呼ばないとバックエンドへの読み書きが発生しない。
これは、コストの高い補助記憶装置へのアクセスを最小限に留めるためと考えられる。
ただし、オプションの livesync に True を指定すれば、値の更新が生じた時点でバックエンドに読み書きが生じる。
以下のサンプルコードでは、デバッグ用に sync() メソッドと close() メソッドが呼ばれると文字列を出力するバックエンドを定義している。
それを用いた上で livesync オプションに True を指定している。
#!/usr/bin/env python # -*- coding: utf-8 -*- import percache class DebugBackend(dict): """デバッグ用のバックエンド (ディスクへの永続化はしない)""" def sync(self): """sync() メソッドが呼ばれたときに標準出力に書く""" print('sync') def close(self): """close() メソッドが呼ばれたときに標準出力に書く""" print('close') # 値の更新がある毎に永続化する debug_backend = DebugBackend() cache = percache.Cache(debug_backend, livesync=True) @cache def add(a, b): print('calculate') return a + b def main(): print(add(1, 2)) print(add(1, 2)) if __name__ == '__main__': main()
上記を保存して実行してみよう。 計算自体は一回しか実施されていないが、戻り値が返るごとにバックエンドへの読み書きが生じていることが分かる。
$ python livesync.py calculate sync 3 sync 3 close
オブジェクトの文字列表現をカスタマイズする
前述した通り percache では関数の引数を組み込み関数の repr() に渡して、その結果を元に辞書のキーに使うハッシュを作る。
つまり、関数の引数に渡すオブジェクトは repr() で適切な文字列を返すようになっていないといけない。
ここで補足しておくと 、組み込み関数の repr() というのは渡されたオブジェクトの文字列表現を取り出すために用いられる。
この repr() 関数にオブジェクトが渡されたときの振る舞いは、特殊メソッドの __repr__() を定義することでオーバーライドできる。
実際に試してみよう。
まずは User という自作クラスを用意する。
このクラスはインスタンス化するときに名前と年齢をメンバ変数に格納する。
そして、このクラスには特殊メソッドの __repr__() が定義されていない。
>>> class User(object): ... def __init__(self, name, age): ... self._name = name ... self._age = age ...
このクラスをインスタンス化して repr() に渡すと、デフォルトの文字列表現が返される。
これは、インスタンスの元となったクラス名やメモリ上の配置位置を示している。
>>> o = User('alice', 20) >>> repr(o) '<__main__.User object at 0x103519b00>'
上記のメモリ上の配置位置はオブジェクトを作る毎に変化する。
本来であれば、同じ名前と年齢を持ったオブジェクトからは同じ repr() がほしい。
そうなっていないと、同じ値を持っているにも関わらず生成したハッシュが異なってしまう。
それではメモ化するときのキーとしては使えない。
そこで、次のように特殊メソッドの __repr__() を定義する。
ここにはクラス名と名前と年齢が文字列に埋め込まれている。
>>> class User(object): ... def __init__(self, name, age): ... self._name = name ... self._age = age ... def __repr__(self): ... """repr() で呼ばれる特殊メソッド""" ... params = { ... 'name': self._name, ... 'age': self._age, ... } ... repr_msg = '<User name:{name} age:{age}>'.format(**params) ... return repr_msg ...
実際にインスタンス化したオブジェクトを repr() 関数に渡してみよう。
>>> o = User('alice', 20) >>> repr(o) '<User name:alice age:20>'
ちゃんとクラス名と名前と年齢を使ってオブジェクトの文字列表現が返るようになった。 これならオブジェクトが異なっても、同じ値さえ持っていれば同じハッシュが生成できる。
このように、自作のクラスについては上記のように特殊メソッドの __repr__() を実装してやればいい。
ただ、実際には自分で作っていないオブジェクトをメモ化した関数に渡すことも考えられる。
percache では、この問題の解決方法も用意してある。
具体的には組み込み関数 repr() の代わりにオブジェクトの文字列表現を取り出すための関数が登録できる。
以下のサンプルコードでは _repr() という関数でオブジェクトの文字列表現を取り出すための関数を定義している。
そして、それを Cache クラスのコンストラクタに渡している。
_repr() 関数の中では、全てのオブジェクトの文字列表現を生成する。
ただし、カスタマイズしたいオブジェクト以外については単純に repr() 関数の出力を返すだけで良い。
このサンプルコードでは User クラスのときだけ特別扱いして、名前と年齢を元に文字列表現を作っている。
#!/usr/bin/env python # -*- coding: utf-8 -*- import percache class User(object): def __init__(self, name, age): self._name = name self._age = age def _repr(args): if isinstance(args, User): # 引数に User のインスタンスが渡されたときの処理 params = { 'name': args._name, 'age': args._age, } repr_msg = '<User name:{name} age:{age}>'.format(**params) return repr_msg # それ以外のオブジェクト return repr(args) cache = percache.Cache('user-cache', repr=_repr) @cache def process(user): print('calculate') return user._name, user._age def main(): o1 = User('alice', 20) print(process(o1)) o2 = User('alice', 20) print(process(o2)) if __name__ == '__main__': main()
変数の o1 と o2 は異なるオブジェクトだけど、持っているメンバ変数の内容は同じなので等価と見なせる。
上記を実行してみよう。
calculate という文字列は一度しか出力されていないことから、ちゃんと戻り値が使い回されていることが分かる。
$ python myrepr.py calculate ('alice', 20) ('alice', 20)
めでたしめでたし。
スマートPythonプログラミング: Pythonのより良い書き方を学ぶ
- 作者: もみじあめ
- 発売日: 2016/03/12
- メディア: Kindle版
- この商品を含むブログ (1件) を見る
