メモ化
メモ化（英: memorization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。
概要
[編集]メモ化という用語は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
なお、言語によってはこれらのステップの一部は言語の機能として実装されている。上記はあくまで説明のための擬似コードである。
構文解析
[編集]ピーター・ノーヴィグは1991年、構文解析戦略にメモ化を応用し、単純なバックトラッキング式の再帰下降構文解析に自動メモ化を適用することでアーリー法のようなアルゴリズムになることを示した[2]。1995年には Johnson と Dörre も構文解析でのメモ化の応用を提案した[5][6]。2002年、Ford はこれのパックラット構文解析への応用をかなり詳細に論じた[7]。
ノーヴィグは構文解析器をメモ化によって強化したが、時間計算量はアーリー法と同じであった。つまりこれは、速度的性能の最適化以外にメモ化を応用した例である。Johnson と Dörre[6] も同様に時間短縮以外の応用を示した。それは、言語的制約の解決を必要な情報が構文解析によって十分集まった時点にまで遅延されることにメモ化を利用するものだった。一方、Ford は時間的性能の最適化にメモ化を応用し、パックラット構文解析が最悪ケースのバックトラッキングが必要な形式言語でも線形時間で構文解析できることを示した[7]。
次のような形式文法を考えてみよう。
S → (A c) | (B d) A → X (a|b) B → X b X → x [X]
ここで、生成規則 S → (A c) | (B d) の意味は、「S は、A の後に1つの c が続くか、あるいは B の後に1つの d が続くかのどちらかである」となる。また、生成規則 X → x [X] の意味は、「X は、1つの x の後にオプションの X が続く」となる。
この文法が生成する文字列は、xac、xbc、xbd（なお、x は1つ以上の x の連続となりうる）のいずれかである。次にこの文法から構文解析の仕様をトップダウンでかつ左から右に解析するものとしたとき、文字列 xxxxxbd の解析がどうなるかを考える。
- トップダウンであるから、まず全体が S に置換可能であるとの前提で、S の規則から、まず全体が (A c) であると仮定する。最後の文字がここで既に違っていることは明らかだが、左から右に構文解析するので、構文解析器にはまだ最後の文字が見えていない。次に A の生成規則を見て、さらに X の生成規則を見ていく。ここで初めて先頭の文字が一致する。そして、x が続いている間は X の規則を再帰的に適用し、次の文字 b も A の規則に一致するが、その次の d と c が一致しない。ここでバックトラックが発生し、S のもう一方の選択肢である B の規則を適用し、同様に X を必要な回数適用して、最終的に最後の文字まで一致する。以上によりこの文字列は、この文法で認識される。
ここで重要となるのは、以上の説明の中で X の繰り返し適用が2回出現することである。このように処理を進めていって失敗し、元に戻って別の選択肢に移って処理を再開することをバックトラッキングと呼ぶ。そして、構文解析におけるバックトラッキングにメモ化を応用する余地があることがわかる。ここで、関数 RuleAcceptsSomeInput(Rule, Position, Input) を考える。引数の意味は次の通りである。
Ruleは、検討中の生成規則の名前Positionは、現在検討中の入力上のオフセット位置Inputは、検討中の入力
関数 RuleAcceptsSomeInput のリターン値は Rule が受理した入力の長さとする。その生成規則が指定されたオフセット位置の入力文字を受理しなかった場合は 0 を返す。バックトラッキングとメモ化を使う場合、構文解析は次のようになる。
- オフセット 0 で、生成規則 A から生成規則 X へと下降していき、そこでその位置と生成規則 X について長さ 5 をメモ化（記録）する。d の位置で生成規則の適用に失敗すると、生成規則 B が選ばれ、再び X を適用するのではなく、メモ化エンジンに対して位置 0 と生成規則 X についての記録があるかを訊ねる。メモ化エンジンは長さ 5 が記録されているのでそれを返す。これにより実際に X を適用することなく処理を省略でき、前回と同じぶんだけ X を適用したのと同じ効果を得る。
この例では、X は再帰的に何度でも適用可能であるため、xxxxxxxxxxxxxxxxbd のような文字列もありうる。従って S を始点として X まで下降して再帰的に生成規則の適用を繰り返すが、バックトラックして B に移行した後は RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) のリターン値が 16 であることが分かっている（メモ化済みである）ので、実際に X を適用する必要がない。
統語的述語（syntactic predicate）を使った構文解析器でも、述語の構文解析結果をメモ化できる。例えば次のような構文規則があるとする。
S → (A)? A A → /* 何らかの規則 */
これは、入力の先頭で A で受理できるなら A で受理することを表している。述語部分 (A)? の結果をメモ化しておけば、実際の生成規則適用時は省略できる。
構文解析時に構文木を構築する場合、メモ化ではマッチした入力の長さだけでなく、その位置と生成規則によって生成された部分木も記憶しておく必要がある。同様に、生成規則がマッチしたときに外部のコードを呼び出す方式の構文解析器の場合、その呼び出し順序が本来期待されている順序になるよう注意してメモ化する必要がある。
全ての文法でバックトラッキングや統語的述語が必要となるわけではないので、個々の生成規則について結果を記憶しておくことで構文解析の性能が低下する可能性がある。これは、メモ化する生成規則を明示的に選択することで問題を限定することができる[8]。
関連項目
[編集]脚注
[編集]- ^ 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.
外部リンク
[編集]- 各種プログラミング言語におけるメモ化の例
- Memoize - Tim Bradshaw の作成したライブラリ。Common Lisp 向け
- Marty Hall's Automatic Memoization toolkit Common Lisp向け
- Memoize.pm - メモ化を実装したPerlモジュール
- Java memoization - 汎用メモ化パターンについての Java のコード例
- Memoization in C++ - C++向け自動メモ化ツールキット
- Tek271 Memoizer - オープンソースの Java 向けメモ化ツール
- memoize - Ruby向け
- Python memoization - Pythonでのメモ化の例
- OCaml memoization - Camlp4 での構文拡張によるメモ化
- Memoization in Lua - Luaでの2種類のメモ化の実装例