自動メモ化

ウィキペディア小見出し辞書

自動メモ化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/14 17:00 UTC 版)

「メモ化」の記事における「自動メモ化」の解説

上述の factorial の例のように、メモ化は一般にプログラマが関数内部に明示的に施すものであるが、参照透過性のある関数は外部で自動的にメモ化することもできる。ピーター・ノーヴィグが採用した技法は Common Lisp （ノーヴィグの論文で自動メモ化の例に使われていた言語）だけでなく、様々なプログラミング言語で応用可能である。自動メモ化は項書き換えや人工知能の研究でも応用が模索されている。 関数が第一級か第二級オブジェクトであるようなプログラミング言語（例えば 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 なお、言語によってはこれらのステップの一部は言語の機能として実装されている。上記はあくまで説明のための擬似コードである。