メモ化

メモ化（英: Memoization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。

概要

メモ化（memoization）という用語は1968年にドナルド・ミッキーがラテン語の memorandum（覚えておく）から作った造語である。memorization（記憶、暗記）は同根語であってよく似ているが、メモ化という言葉は情報工学では特別な意味を持つ。
メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。メモ化可能な関数は参照透過性を備えたものに限られる。すなわち、メモ化されたことで副作用が生じない場合に限られる。メモ化の実装ではルックアップテーブルなどの参照方式が使われるが、メモ化では参照されるテーブルの内容は必要に応じて格納されるという点で、通常のテーブル参照とは異なる。
メモ化は関数の時間コストを領域コストに交換して、時間コストを低減させる手段である。すなわち、メモ化された関数は速度の面で最適化され、記憶装置の領域という面ではより多く消費する。計算複雑性理論は、アルゴリズムの時間と領域のコストを扱う。全ての関数には時間と領域についての複雑性が定義される。
このようにトレードオフが発生するが、同様のトレードオフがある最適化とは異なる。というのも、演算子強度低減などの最適化はコンパイル時のものだが、メモ化は実行時の最適化であるためである。さらに言えば、演算子強度低減は例えば、乗算を加算の組合せで表すことで性能を改善しようとするもので、プラットフォームのアーキテクチャに深く依存している。一方、メモ化はプラットフォームからは独立した戦略である。

自動メモ化

上述の 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
なお、言語によってはこれらのステップの一部は言語の機能として実装されている。上記はあくまで説明のための擬似コードである。