メモ化

コンピューティングにおいて、メモ化（memoization）は、主にコンピュータプログラムの高速化を目的とした最適化手法です。これは、純粋関数への高価な呼び出し結果を保存することで機能します。これにより、同じ入力が再び発生した場合、これらの結果を迅速に返すことができます。これはキャッシュの一種であり、通常はハッシュテーブルを用いて実装されます。また、メモリ使用量を増やすことでプログラムの実行時間を短縮する、空間と時間のトレードオフの典型的な例です。メモ化はどのプログラミング言語でも実装できますが、一部の言語には、プログラマが関数を簡単にメモ化できるようにする組み込みサポートが用意されており、他の言語では特定の関数がデフォルトでメモ化されます。

メモ化は、単純な相互再帰下降構文解析など、他のコンテキストでも（速度向上以外の目的で）使用されています。^[1]一部の論理型プログラミング言語のコンテキストでは、メモ化はテーブル化とも呼ばれます。^[2]

語源

メモ化（memoization）という用語は、 1968年にドナルド・ミチーによって造語されました^[3]^{[検証失敗]。}ラテン語のmemorandum（「記憶される」）に由来し、アメリカ英語では通常memoと省略され、「関数の結果を記憶できるものに変換する」という意味を持ちます。memoizationはmemorizationと混同されることがあります（語源的に同義語であるため）。しかし、memoizationはコンピューティングにおいて特別な意味を持ちます。

概要

メモ化された関数は、特定の入力セットに対応する結果を「記憶」します。記憶された入力を用いた後続の呼び出しでは、結果を再計算するのではなく、記憶された結果を返します。これにより、特定のパラメータを用いた関数の最初の呼び出しを除くすべての呼び出しにおいて、そのパラメータを用いた呼び出しの主なコストが排除されます。記憶された関連付けのセットは、関数の性質と用途に応じて、置換アルゴリズムによって制御される固定サイズのセット、または固定セットになります。関数は、参照透過性がある場合にのみメモ化できます。つまり、関数を呼び出すことが、その関数呼び出しをその戻り値に置き換えることと全く同じ効果を持つ場合のみです。（ただし、この制限には特別な例外が存在します。）参照テーブルに関連していますが、メモ化は実装においてそのようなテーブルを使用することが多いため、メモ化は結果のキャッシュを事前にではなく、必要に応じて透過的にオンザフライで設定します。

メモ化された関数は、コンピュータのメモリ空間をより多く使用することと引き換えに、速度を重視して最適化されています。アルゴリズムの時間／空間コストは、コンピューティングの世界では「計算複雑性」と呼ばれます。すべての関数は、時間（つまり実行に時間がかかること）と空間の計算複雑性を持ちます。

メモリ使用量とメモリ時間のトレードオフ（つまり、メモリ使用量が速度向上につながる）は発生しますが、メモリ使用量削減などのメモリ使用量とメモリ時間のトレードオフを伴う他の最適化とは異なり、メモ化はコンパイル時ではなく実行時の最適化です。さらに、メモリ使用量削減は乗算などの高コストな演算を加算などの低コストな演算に置き換える可能性があり、その結果得られるメモリ使用量削減はマシンに大きく依存する（マシン間での移植性がない）可能性があります。一方、メモ化はマシンに依存しないクロスプラットフォーム戦略です。

nの階乗を計算する次の疑似コード関数を考えてみましょう。

関数階乗（nは負でない整数）nが0の
    場合
        1を返す [ 0! = 1という慣例により ]
    それ以外
        return factorial( n – 1) times n [ nより小さいパラメータ1でfactorialを再帰的に呼び出す 
                                        ]
    終了の場合
終了関数

となるような任意の整数 nに対してn ≥ 0、関数の最終結果は不変factorialです。つまり、として呼び出された場合、結果としてx には常に値 6 が割り当てられます。上記のメモ化されていない実装では、関係する再帰アルゴリズムの性質を考えると、結果に到達するまでにをn + 1回呼び出す必要があり、これらの呼び出しのそれぞれには、関数が計算された値を返すのにかかる時間というコストがかかります。マシンによっては、このコストは次の合計になる可能性があります。 x = factorial(3)factorial

機能呼び出しスタックフレームをセットアップするためのコスト。
nを 0 と比較するコスト。
nから 1 を引くコスト。
再帰呼び出しスタックフレームをセットアップするためのコスト。(上記と同じ)
再帰呼び出しの結果をnfactorial倍にするコスト。
呼び出しコンテキストで使用できるように、戻り結果を格納するコスト。

メモ化されていない実装では、へのすべてのトップレベルの呼び出しには、nfactorialの初期値に比例したステップ 2 から 6 の累積コストが含まれます。

関数のメモ化されたバージョンはfactorial次のとおりです。

関数階乗（nは負でない整数）nが0の
    場合
        1を返す [ 0! = 1という慣例により ]
    そうでない場合、nがルックアップテーブル内にある場合nのルックアップテーブルの値
        を返す
    それ以外
        let x = factorial(n – 1) times n [ nより小さいパラメータ1でfactorialを再帰的に呼び出す
                                         ]x をルックアップテーブルのn^番目のスロットに
        格納します[ n! の結果を後で使用するために覚えておいてください]
        xを返す
    終了の場合
終了関数

この特定の例では、factorial関数が最初に5で呼び出され、その後5以下の任意の値で呼び出された場合、それらの戻り値もメモ化されます。これは、関数がfactorial5、4、3、2、1、0という値で再帰的に呼び出され、それぞれの戻り値が保存されているためです。その後、関数が5より大きい数値、例えば7で呼び出された場合、再帰呼び出しは2回（7と6）のみ行われ、5!の値は前回の呼び出しから保存されます。このように、メモ化によって関数は呼び出される回数が増えるほど時間効率が向上し、最終的には全体的な速度向上につながります。

メモ化の極端な例はシングルトンパターン、具体的にはそのゲッターの実装です。ゲッターは、最初の呼び出し時にオブジェクトを作成し、そのインスタンスをキャッシュし、後続のすべての呼び出しで同じオブジェクトを返す関数です。

その他の考慮事項

関数型プログラミング

メモ化は、関数型プログラミング言語のコンパイラで多用されます。これらの言語では、名前による評価戦略がよく用いられます。引数値の計算に伴うオーバーヘッドを回避するため、これらの言語のコンパイラは、引数値の計算に「サンク」と呼ばれる補助関数を多用し、これらの関数をメモ化することで繰り返し計算を回避します。

自動メモ化

メモ化は、上記のメモ化された関数の実装とほぼ同じ方法で、コンピュータプログラマによって関数内部で明示的に追加される可能性があるが、参照透過的な関数は外部的に自動的にメモ化される可能性もある。^[1]Peter Norvigが用いた手法は、 Common Lisp（彼の論文で自動メモ化が実証された言語）だけでなく、他のさまざまなプログラミング言語にも応用できる。自動メモ化の応用は、項書き換え^[4]や人工知能^[5]の研究でも正式に研究されてきた。factorial

関数が第一級オブジェクトであるプログラミング言語（ Lua、Python、Perl ^[6]など）では、与えられたパラメータセットに対して値が計算された後、実行時に関数をその計算値に置き換えることで自動メモ化を実装できます。この関数オブジェクトへの値の置き換えを行う関数は、参照透過な任意の関数を汎用的にラップできます。次の擬似コードを検討してください（関数は第一級値であると仮定しています）。

関数メモ化呼び出し（Fは関数オブジェクトのパラメータ）Fに配列値が添付されていない
    場合はvaluesと呼ばれる連想配列
        を割り当てます。Fに値を
        添付します。
    終了の場合;
F . values[arguments]が空の
        
    場合、 F . values[arguments] = F (arguments) となります。
    終了の場合;
F.values[引数]
    を返します。
終了関数

factorial上記の戦略を用いての自動メモ化バージョンを呼び出すには、factorial直接呼び出すのではなく、を呼び出します。各呼び出しでは、まず結果を格納するためのホルダー配列が割り当てられているかどうかを確認し、割り当てられていない場合はその配列にアタッチします。の位置（が連想配列のキーとして使用されている位置）にエントリが存在しない場合は、指定された引数を用いてを実際に呼び出します。最後に、配列内のキー位置のエントリが呼び出し元に返されます。 memoized-call(factorial)(n)values[arguments]argumentsfactorial

上記の戦略では、メモ化対象となる関数の各呼び出しにおいて明示的なラップが必要です。クロージャを許容する言語では、ラップされたメモ化関数オブジェクトをデコレータパターンで返すファンクタファクトリを介して、メモ化を暗黙的に行うことができます。擬似コードでは、これは次のように表現できます。

関数construct-memoized-functor（Fは関数オブジェクトのパラメータ）memoized-version
    という関数オブジェクトを割り当てます。

    memoized-version(引数)を自身に配列値が接続されていない
        場合は[自身はこのオブジェクトへの参照です]values
            と呼ばれる連想配列を割り当てます。自分自身に価値
            を置く;
        終了の場合;

        self.values [arguments]が空の場合
            self.values [引数] = F (引数);
        終了の場合;
self.values[引数]
        を返します。
    終了let;
メモ化されたバージョン
    を返します。
終了関数

を呼び出すのではなくfactorial、次のように新しい関数オブジェクトmemfactが作成されます。

memfact = メモ化された関数を構築する(階乗)

上記の例では、関数がを呼び出す前に既に定義されていることを前提としています。このfactorial時点以降、nの階乗を求める必要がある場合はいつでもが呼び出されます。Lua などの言語では、より洗練された手法が存在し、関数を同じ名前の新しい関数に置き換えることができます。これにより、次のようなことが可能になります。 construct-memoized-functormemfact(n)

階乗 = メモ化関数構築(階乗)

基本的に、このような手法では、元の関数オブジェクトを作成されたファンクタにアタッチし、実際の関数の呼び出しが必要な場合に、（無限再帰を回避するため）エイリアスを介してメモ化されている元の関数への呼び出しを転送します。以下に例を示します。

関数construct-memoized-functor（Fは関数オブジェクトのパラメータ）memoized-version
    という関数オブジェクトを割り当てます。
メモ化されたバージョン（引数）
    を自身に配列値が接続されていない
        場合は[自身はこのオブジェクトへの参照です]values
            と呼ばれる連想配列を割り当てます。自分自身に価値
            を置く;alias
            という新しい関数オブジェクトを割り当てます。自分自身にエイリアス
            を付ける; [後でFを間接的に呼び出すため]
            self.alias = F ;
        終了の場合;

        self.values [arguments]が空の場合
            self.values [arguments] = self.alias ( arguments); [ Fへの直接呼び出しではありません]
        終了の場合;
self.values[引数]
        を返します。
    終了let;
メモ化されたバージョン
    を返します。
終了関数

(注: 上記の手順の一部は、実装言語によって暗黙的に管理される場合があり、説明のために提供されています。)

パーサー

トップダウンパーサーが曖昧な文脈自由文法（CFG）に基づいて曖昧な入力を解析しようとする場合、CFGのすべての代替案を試してすべての可能な構文木を生成するには、入力の長さに対して指数関数的なステップ数が必要になる場合があります。これは最終的に指数関数的なメモリ空間を必要とします。メモ化は1991年にピーター・ノーヴィグによって解析戦略として研究され、彼は、アーリーのアルゴリズム（1970年）における動的計画法と状態集合、そしてコック、ヤンガー、カサミのCYKアルゴリズムにおけるテーブルの使用と同様のアルゴリズムを、単純なバックトラッキング再帰下降パーサーに自動メモ化を導入することで生成し、指数関数的な時間計算量の問題を解決できることを実証しました。^[1] Norvigのアプローチの基本的な考え方は、パーサーが入力に適用されると、その結果がメモテーブルに保存され、同じパーサーが同じ入力に再度適用された場合に再利用できるというものです。

リチャード・フロストとバーバラ・シドロウスキーもメモ化を利用してパーサコンビネータの指数関数的時間計算量を削減し、その結果をメモ化された純粋に機能的なトップダウンバックトラッキング言語プロセッサと表現した。^[7]フロストは、基本的なメモ化されたパーサコンビネータを構成要素として使い、CFGの実行可能な仕様として複雑なパーサを構築できることを示した。^[8]^[9]

メモ化は1995年にマーク・ジョンソンとヨッヘン・デーレによって構文解析の文脈で再び研究された。^[10]^{[11] 2002年にはブライアン・フォードによって}パックラット構文解析と呼ばれる形でかなり深く研究された。^[12]

2007 年に、Frost、Hafiz、Callaghan ^[要出典]は、冗長な計算を控えるためにメモ化を使用し、あらゆる形式の曖昧な CFG に多項式時間 ( Θ (n ⁴ )左再帰文法では Θ(n 3 ) 非左再帰文法では Θ(n ³ ) ) で対応するトップダウン構文解析アルゴリズムを説明した。彼らのトップダウン構文解析アルゴリズムは、「コンパクトな表現」と「局所的曖昧性のグループ化」によって、潜在的に指数関数的な曖昧な構文木に対しても多項式空間を必要とする。彼らのコンパクトな表現は、Tomita のボトムアップ構文解析のコンパクトな表現に匹敵する。^[13]彼らのメモ化の使用は、パーサーが同じ入力位置に繰り返し適用されたときに以前に計算された結果を取得すること (これは多項式時間要件に不可欠) に限定されるのではなく、次の追加タスクを実行するように特化されている。

メモ化プロセス (これは、あらゆるパーサー実行の「ラッパー」として考えることができます) は、入力の長さと現在の入力位置に関する深さの制限を課すことによって、拡大し続ける直接左再帰解析に対応します。
このアルゴリズムのメモテーブル「検索」手順は、保存された結果の計算コンテキストとパーサーの現在のコンテキストを比較することで、保存された結果の再利用可能性も判断します。このコンテキスト比較は、間接的（または隠れた）左再帰に対応するための鍵となります。
メモテーブル内で検索が成功すると、プロセスは完全な結果セットを返すのではなく、実際の結果の参照のみを返すため、最終的には全体的な計算が高速化されます。
メモテーブルの更新中に、メモ化プロセスは (潜在的に指数的な) あいまいな結果をグループ化し、多項式空間要件を保証します。

^{Frost、Hafiz、Callaghanは、PADL'08 [要出典]}において、このアルゴリズムの実装をHaskellの高階関数（パーサーコンビネータと呼ばれる）の集合として発表しました。これにより、CFGを言語プロセッサとして直接実行可能な仕様を構築することが可能になります。彼らの多項式アルゴリズムは、トップダウン解析によって「あらゆる形式の曖昧なCFG」に対応できるため、自然言語処理における構文解析と意味解析において極めて重要です。X-SAIGAのサイトでは、このアルゴリズムと実装の詳細についてさらに詳しく説明しています。

Norvigはメモ化によって構文解析器の性能を向上させたが、拡張された構文解析器は依然としてEarleyのアルゴリズムと同程度の時間複雑性しか持たず、これは速度最適化以外の目的でメモ化が用いられた例を示している。JohnsonとDörre ^[11]は、速度とは関係のないメモ化の別の応用例を示している。それは、言語制約の解決を、制約を解決するのに十分な情報が蓄積されるまで構文解析中に遅らせるためにメモ化を使用するというものである。対照的に、メモ化の速度最適化への応用において、Fordは、最悪のケースでバックトラッキング動作を引き起こす言語であっても、メモ化によって構文解析式文法が線形時間で構文解析できることを保証できることを示した。 ^[12]

次の文法を考えてみましょう。

S → (A c ) | (B d )
A → X ( a | b )
B → X b 
X → x [X]

(表記上の注意: 上記の例では、生成規則S → (A c ) | (B d ) は「SはAの後に c が続くか、Bの後にdが続くかのいずれかです。」と解釈されます。生成規則 X → x [X] は「Xはxの後にオプションのXが続くものです。」と解釈されます。)

この文法は、文字列の次の 3 つのバリエーションのいずれかを生成します: xac、xbc、またはxbd (ここで、 x は1 つ以上のxを意味します)。次に、解析仕様として使用されるこの文法が、文字列xxxxxbdの上から下、左から右への解析にどのように影響するかを考えます。

規則Aはxxxxxb を認識します（まずXに下降してx を1つ認識し、再びXに下降してxをすべて消費し尽くした後、bを認識します）。その後Sに戻りますが、 cは認識されません。 Sの次の節は B に下降し、さらに B はXに下降してXへの多数の再帰呼び出しによって x を認識し、次にbを認識し、Sに戻って最終的にd を認識します。

ここで鍵となる概念は、「再びXに降りる」という句に内在しています。前方を見て失敗し、後退し、次の選択肢を再試行するプロセスは、構文解析ではバックトラッキングと呼ばれ、構文解析においてメモ化の機会を提供するのは主にバックトラッキングです。RuleAcceptsSomeInput(Rule, Position, Input)以下のパラメータを持つ関数を考えてみましょう。

Rule検討中のルールの名前です。
Position入力内で現在考慮されているオフセットです。
Input検討中の入力です。

関数の戻り値は、RuleAcceptsSomeInputが受け入れる入力の長さRule、または、その規則が文字列のそのオフセットで入力を受け入れない場合は0とします。このようなメモ化を伴うバックトラッキングシナリオでは、解析プロセスは次のようになります。

ルールA がオフセット 0 でXに下降すると、その位置とルールXに対して長さ 5 をメモ化します。 dで失敗した後、B はXに再度下降するのではなく、メモ化エンジンでルールXに対して位置 0 を照会し、長さ 5 を返します。これにより、実際にXに再度下降する必要がなくなり、以前と同じ回数だけXに下降したかのように処理が続行されます。

上記の例では、xxxxxxxxxxxxxxxxbdのような文字列が許されるため、Xへの降下は1回または複数回発生する可能性があります。実際、bの前には任意の数のxが存在する可能性があります。 S の呼び出しはxの数だけ X を再帰的に降下する必要がありますが、B はX に降下する必要はまったくありません。これは、（この特定のケースでは）戻り値が16になるためです。 RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

構文述語を利用するパーサーは述語解析の結果をメモ化することもできるため、次のような構文を削減できます。

S → (A)? A
A → /* 何らかのルール */

Aへの 1 つの降下。

パーサーが解析中に構文解析木を構築する場合、特定の規則に対してあるオフセットで一致する入力の長さをメモ化する必要があるだけでなく、入力のそのオフセットでその規則によって生成されるサブツリーも保存する必要がある。これは、パーサーによる後続の規則呼び出しでは、実際にはそのツリーを辿って再構築するわけではないためである。同じ理由で、規則が一致した際に外部コード（セマンティックアクションルーチンと呼ばれることもある）への呼び出しを生成するメモ化パーサーアルゴリズムは、そのような規則が予測可能な順序で呼び出されることを保証する何らかの仕組みを用いる必要がある。

バックトラッキングや構文述語機能を備えたパーサでは、すべての文法がバックトラッキングや述語チェックを必要とするわけではないため、入力のすべてのオフセットに対して各規則の解析結果を保存するオーバーヘッド（そして、解析プロセスが暗黙的に構文木を保存する場合）は、実際にはパーサの速度を低下させる可能性があります。この影響は、パーサがメモ化する規則を明示的に選択することで軽減できます。^[14]

参照

近似計算– 効率を向上させる技術のカテゴリ
計算複雑性理論– アルゴリズムの複雑性に関する詳細情報
ディレクター文字列– 式内の自由変数を素早く見つける
フライウェイトパターン- オブジェクトプログラミングのデザインパターンで、メモ化の一種も使用します。
Hashlife –セルオートマトン計算を高速化するメモ化技術
遅延評価- メモ化といくつかの概念を共有している
マテリアライズドビュー– データベースクエリにおける類似のキャッシュ
部分評価– 自動プログラム最適化の関連技術

参考文献

^ abc Norvig, Peter (1991). 「自動メモ化技術と文脈自由構文解析への応用」.計算言語学. 17 (1): 91–98 .
^ Warren, David S. (1992-03-01). 「論理プログラムのためのメモ化」. Communications of the ACM . 35 (3): 93–111 . doi : 10.1145/131295.131299 . ISSN 0001-0782.
^ ミチー、ドナルド (1968). 「『メモ』関数と機械学習」(PDF) . Nature . 218 (5136): 19– 22. Bibcode :1968Natur.218...19M. doi :10.1038/218019a0. S2CID 4265138.
^ Hoffman, Berthold (1992). 「共有とメモ化による項書き換え」. Kirchner, H.; Levi, G. (編).代数的および論理的プログラミング：第3回国際会議議事録, イタリア、ヴォルテッラ, 1992年9月2日～4日. コンピュータサイエンス講義ノート. 第632巻. ベルリン: Springer. pp. 128– 142. doi :10.1007/BFb0013824. ISBN 978-3-540-55873-6。
^ メイフィールド、ジェームズ他 (1995). 「実世界AIシステムにおけるソフトウェアエンジニアリングツールとしての自動メモ化の利用」(PDF) .第11回IEEE人工知能応用会議 (CAIA '95) 議事録. pp. 87– 93. doi :10.1109/CAIA.1995.378786. hdl :11603/12722. ISBN 0-8186-7070-3. S2CID 8963326。
^ 「ブリコラージュ：メモ化」。
^ リチャード・フロスト、バーバラ・シドロウスキー (1996). 「純粋関数型トップダウンバックトラッキング言語プロセッサのメモ化」.科学計算プログラム. 27 (3): 263– 288. doi : 10.1016/0167-6423(96)00014-7 .
^ フロスト、リチャード (1994). 「メモ化を用いた非決定性トップダウンパーサの純粋機能的実行可能仕様の多項式計算量の実現」SIGPLAN Notices . 29 (4): 23– 30. doi :10.1145/181761.181764. S2CID 10616505.
^ リチャード・フロスト (2003). 「モナド式メモ化による正確性維持型探索削減」.カナダAI会議2003.コンピュータサイエンス講義ノート. 第2671巻. pp. 66– 80. doi :10.1007/3-540-44886-1_8. ISBN 978-3-540-40300-5。
^ ジョンソン、マーク (1995). 「トップダウン構文解析のメモ化」.計算言語学. 21 (3): 405– 417. arXiv : cmp-lg/9504016 . Bibcode :1995cmp.lg....4016J.
^ ab Johnson, Mark & Dörre, Jochen (1995). 「コルーチン制約のメモ化」.計算言語学会第33回年次会議議事録. マサチューセッツ州ケンブリッジ. arXiv : cmp-lg/9504028 .{{cite book}}: CS1 maint: location missing publisher (link)
^ ab Ford, Bryan (2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (修士論文). マサチューセッツ工科大学. hdl :1721.1/87310.
^ 富田勝(1985).自然言語処理のための効率的な構文解析. ボストン: クルーワー. ISBN 0-89838-202-5。
^ Acar, Umut A.; et al. (2003). 「選択的メモ化」. Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 15–17 January 2003 . Vol. 38. New Orleans, Louisiana. pp. 14– 25. arXiv : 1106.0447 . doi :10.1145/640128.604133. {{cite book}}:|journal=無視されました (ヘルプ)CS1 maint: location missing publisher (link)

外部リンク

無料辞書のウィクショナリーで「メモ化」を調べてください。

さまざまなプログラミング言語におけるメモ化の例

groovy.lang.Closure#memoize() – Memoize はApache Groovy 1.8 言語機能です。
Memoize – Memoize は、Tim Bradshaw によって書かれた、 Common Lispでメモ化を実行するための小さなライブラリです。
IncPy – 自動メモ化を実行するカスタムPythonインタープリタ（ユーザーによる注釈は不要）
Racketでメモ化された手順を定義するための Dave Herman のマクロ。
Memoize.pm –メモ化された関数を実装するPerl モジュール。
Java メモ化 – 動的プロキシクラスを使用して汎用メモ化パターンを作成する Java の例。
memoization.java - Java メモ化ライブラリ。
C++Memo – C++メモ化フレームワーク。
C-Memo – プリプロセッサ関数ラッパーマクロを使用して実装された、C 用の汎用メモ化ライブラリ。
Tek271 Memoizer – アノテーションとプラグ可能なキャッシュ実装を使用するオープンソースの Java メモライザー。
memoizable –メモ化されたメソッドを実装するRuby gem。
Python メモ化 –メモ化のPythonの例。
OCaml メモ化 – Camlp4構文拡張として実装されています。
Lua でのメモ化 – Luaでの一般的なメモ化関数の 2 つの実装例。
Mathematica でのメモ化 – Mathematicaでのメモ化と限定的なメモ化。
Javascript でのメモ化 – JavaScriptでの関数プロトタイプの拡張( http://talideon.com/weblog/2005/07/javascript-memoization.cfm のアーカイブバージョン)。
Javascript でのメモ化 – 独自のキャッシュ機構と YUI ライブラリを使用した JavaScript でのメモ化の例
X-SAIGA – 文法の実行可能な仕様。多項式時間と空間における左再帰と曖昧性をサポートするトップダウン構文解析アルゴリズムに関する出版物が含まれています。
Scheme でのメモ化 –クラス Web ページでのメモ化のSchemeの例。
組み合わせロジックのメモ化 -データベース内のすべてのステップをメモ化しながら組み合わせロジックを削減する Web サービス。
MbCache – .NETでのメソッドの結果をキャッシュします。