メモ化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/09/10 08:00 UTC 版)
概要
メモ化という用語は1968年にドナルド・ミッキーがラテン語の memorandum（覚えておく）から作った造語である[1]。memorization（記憶、暗記）は同根語であってよく似ているが、メモ化という言葉は情報工学では特別な意味を持つ。
メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。メモ化可能な関数は参照透過性を備えたものに限られる。すなわち、メモ化されたことで副作用が生じない場合に限られる。メモ化の実装ではルックアップテーブルなどの参照方式が使われるが、メモ化では参照されるテーブルの内容は必要に応じて格納されるという点で、通常のテーブル参照とは異なる。
メモ化は関数の時間コストを領域コストに交換して、時間コストを低減させる手段である。すなわち、メモ化された関数は速度の面で最適化され、記憶装置の領域という面ではより多く消費する。計算複雑性理論は、アルゴリズムの時間と領域のコストを扱う。全ての関数には時間と領域についての複雑性が定義される。
このようにトレードオフが発生するが、同様のトレードオフがある最適化とは異なる。というのも、演算子強度低減などの最適化はコンパイル時のものだが、メモ化は実行時の最適化であるためである。さらに言えば、演算子強度低減は例えば、乗算を加算の組合せで表すことで性能を改善しようとするもので、プラットフォームのアーキテクチャに深く依存している。一方、メモ化はプラットフォームからは独立した戦略である。
例
function factorial (n) // n は非負整数
if n == 0 then
return 1
else
return factorial(n - 1) * n // 再帰呼び出し
end if
end function
n ≥ 0 であるような全ての整数 n について、関数 factorial の結果は不変である。つまり、x = factorial(3) としたとき、x の値は常に 6 である。上記のメモ化する前のコードでは、結果を得るのに n + 1 回の再帰呼び出しが必要であり、それが計算における時間コストに相当する。プラットフォームのアーキテクチャにも依存するが、時間コストは以下のコストの総和である。
- 関数のスタックフレームを設定するのにかかるコスト
- n と 0 を比較するのにかかるコスト
- n から 1 を引くのにかかるコスト
- 再帰呼び出しのためのスタックフレームを設定するのにかかるコスト
- 再帰呼び出しの結果と n の乗算を行うコスト
- 結果を呼び出し側に返すのにかかるコスト
メモ化していない実装では、これらのコストのうち 2 番から 6番が n に比例した回数かかることになる。
factorial をメモ化したバージョンを以下に示す。
function factorial (n) // n は非負整数
if n == 0 then
return 1
else if (テーブルに n の階乗が格納されている) then
return (テーブルに格納された n の階乗の値)
else
x = factorial(n - 1) * n // 再帰呼び出し
x を n の階乗の値としてテーブルに格納する
return x
end if
end function
このメモ化バージョンでは、「テーブル」は広域の永続性のある変数であり、n をキーとする連想配列のようなものである。このルックアップテーブルが領域（すなわちコンピュータのメモリ）を使うことによって、factorial を同じ引数で繰り返し呼び出したときに要する時間が削減される。
例えば、factorial を最初に引数 5 で呼び出すと、その後 5 以下の引数で呼び出したとき、それらの値は既にメモ化されている。なぜなら、factorial は引数 5、4、3、2、1、0 で再帰的に呼び出され、それぞれの呼び出しについて結果が記憶されるからである。また、引数 5 で呼び出された後に引数 7 で呼び出されると、再帰呼び出しは 2 回で済み（7 と 6）、5! の値は既に記憶されているのでそれが使われる。このように、メモ化された関数は呼び出される度により効率化されていき、結果として全体の高速化が図られる。
自動メモ化
上述の factorial の例のように、メモ化は一般にプログラマが関数内部に明示的に施すものであるが、参照透過性のある関数は外部で自動的にメモ化することもできる[2]。ピーター・ノーヴィグが採用した技法は Common Lisp （ノーヴィグの論文で自動メモ化の例に使われていた言語）だけでなく、様々なプログラミング言語で応用可能である。自動メモ化は項書き換え[3]や人工知能[4]の研究でも応用が模索されている。
関数が第一級か第二級オブジェクトであるようなプログラミング言語（例えば Lua）では、自動メモ化は関数を特定の引数付きで実行するたびに、その結果の値で（実行時に）置き換えてやることで実装される。このような置き換えを行う汎用関数を本来の関数を呼び出す代わりに呼び出せばよい。擬似コードを以下に示す（この例では関数は第一級オブジェクトであると仮定している）。
function memoized-call (F） // F は関数オブジェクト
if (F には対応する配列 values がない) then
allocate an associative array called values;
attach values to F;
end if;
if F.values[arguments] is empty then
F.values[arguments] = F(arguments);
end if;
return F.values[arguments];
end function
factorial を自動メモ化する場合もこの戦略を使い、factorial を直接呼び出すのではなく、memoized-call(factorial(n)) を呼び出す。呼び出されると、まず結果を格納する配列が確保されているかどうかを調べ、なければ配列を確保して割り当てる。次に、values[arguments] の位置にエントリが無ければ（ここで arguments は連想配列のキーとして使われている）、実際の factorial を呼び出す。最後に、配列のキー位置のエントリが呼び出し側に返される。
この戦略では、メモ化される関数を呼び出す箇所で明示的な対処が必要となる。クロージャが可能な言語では、メモ化はメモ化関数オブジェクトをラップする functor オブジェクトとして暗黙的に実現できる。これを擬似コードで表すと、次のようになる。
function construct-memoized-functor (F） // F は関数オブジェクト
allocate a function object called memoized-version;
let memoized-version(arguments) be
if (self に対応する連想配列 values がない) then // self は いわゆる this オブジェクト
allocate an associative array called values;
attach values to self;
end if;
if self.values[arguments] is empty then
self.values[arguments] = F(arguments);
end if;
return self.values[arguments];
end let;
return memoized-version;
end function
factorial の代わりに使われる新たな関数オブジェクト memfact は次のように生成される。
memfact = construct-memoized-functor(factorial)
この例では、関数 factorial は construct-memoized-functor を呼び出す前に定義されているものとしている。そしてそれ以降、n の階乗を計算したい場合は常に memfact(n) を呼び出す。Luaなどの言語では、関数名を変えずに置き換えることも可能であり、次のようにできる。
factorial = construct-memoized-functor(factorial)
基本的にこのような技法では、生成された functor にオリジナルの関数オブジェクトをアタッチし、必要な場合（無限の再帰呼び出しを避けるため）にオリジナルの関数をエイリアスを通して呼び出す。これを擬似コードで表すと次のようになる。
function construct-memoized-functor (F) // F は関数オブジェクト
allocate a function object called memoized-version;
let memoized-version(arguments) be
if (self に対応する連想配列 values がない) then // self は いわゆる this オブジェクト
allocate an associative array called values;
attach values to self;
allocate a new function object called alias;
attach alias to self; // F を後で間接的に呼び出すため
self.alias = F;
end if;
if self.values[arguments] is empty then
self.values[arguments] = self.alias(arguments); // F の直接呼出しではない
end if;
return self.values[arguments];
end let;
return memoized-version;
end function
なお、言語によってはこれらのステップの一部は言語の機能として実装されている。上記はあくまで説明のための擬似コードである。
- ^ Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19-22, 1968.
- ^ a b Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1, pp. 91-98, March 1991.
- ^ Hoffman, Berthold, "Term Rewriting with Sharing and Memoïzation," Algebraic and Logic Programming: Third International Conference, Proceedings, H. Kirchner and G. Levi (eds.), pp. 128-142, Volterra, Italy, 2-4 September 1992.
- ^ Mayfield, James, et al, Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems, TBD, 1995.
- ^ Johnson, Mark, "Memoization of Top-Down Parsing,” Computational Linguistics, Vol. 21 No. 3, pp. 405-417, September 1995.
- ^ a b Johnson, Mark & Dörre, Jochen, "Memoization of Coroutined Constraints," Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, 1995.
- ^ a b Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, September, 2002.
- ^ Acar, Umut A. A. et al., "Selective Memoization," Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisiana, pp. 14-25, 15-17 January 2003.
- メモ化のページへのリンク
