気ままNote

個人の技術メモ

LRU方式とlru_cacheデコレータについて

とあるPython製のOSSを眺めていたら見慣れない書き方があったので調べてみました。 lru_cache は python3.2から functoolsに追加されたデコレータです。

そもそも lru とはIT用語辞典によると、

LRUとは、キャッシュアルゴリズムなどで用いられる、置換対象のデータを定める方式のうち、参照されていない時間が最も長いデータを置換対象にする方式のことである。

例えば、仮想記憶管理におけるページング方式では、主記憶装置(メインメモリ)上で補助記憶装置へ退避させるデータ単位(ページ)を選ぶ方式としてLFUを用いることがある。主記憶装置で扱うことのできる容量には限度があるため、主記憶装置の記憶容量を超えるデータを扱う場合は、データの一部を補助記憶装置へと置換することで空き容量を確保する。このとき、LRUでは、それぞれのデータが参照された時間に基づき、その時間が最も古い(least recently)データを置換対象とする。

と説明されています。
Pythonのドキュメントには、

高価な関数や I/O に束縛されている関数を定期的に同じ引数で呼び出すときに、時間を節約できます。

とあります。

まとめると、 lru はキャッシュアルゴリズムの一種であり、lru_cache は高速化を目的としたときに有効となる手段の一つのようでした。

参考