問題タブ [memoization]

次の関数をメモ化しようとしています。

これを見て、私は次の解決策を思いつきました：

私はそれからこのように呼ぶことができます：

Haskellで複数のパラメーターを持つ関数をメモ化するためのより簡単で簡潔で一般的な方法（gwlistメモ化リストにアクセスできるように2Dから1D空間に変換するために関数の最大グリッド次元をハードコーディングする必要があることに注意してください）はありますか？

私はHaskellを学び始めたばかりで、演習として、フィボナッチ数が合計されるプロジェクトオイラー問題に入りました。私の現在の方法はこの関数で、次の要素で新しいリストを作成します。

結果に関数を再適用する関数を見つけましたiterate。ただし、結果はリストのリストになります[[2,1],[3,2,1],[5,3,2,1],..]。iterate中間結果に興味がない場合の代替手段は何ですか？takeWhile最後に生成された番号の条件でを実行したいと思います。これはそれについて完全に考える間違った方法ですか？

（私はフィボナッチ数列を生成するためのより良い/より短い/より良い方法を見てきました、それで私は実際にfib関数に関するフィードバックを探していません-しかし私はそれを機能させたいです、次善の方法かどうか）

怠惰なセマンティクスを持つ純粋な関数型言語（Haskellなど）では、計算結果がメモ化されるため、同じ入力を持つ関数をさらに評価しても、値は再計算されず、メモ化された値のキャッシュから直接取得されます。

これらのメモ化された値は、ある時点でリサイクルされるのでしょうか。

1. もしそうなら、それはメモ化された値が後で再計算されなければならないことを意味し、メモ化の利点は私見からそれほど離れていません。
2. そうでない場合は、OK、これはすべてをキャッシュするのに賢いです...しかし、プログラムが-十分に長い期間実行された場合-常により多くのメモリを消費することを意味しますか？

集中的な数値解析を実行するプログラムを想像してみてください。たとえば、二分法アルゴリズムを使用して、数十万の数学関数のリストの根を見つけます。

プログラムが特定の実数で数学関数を評価するたびに、結果はメモ化されます。ただし、アルゴリズム中にまったく同じ実数が再び表示され、メモリリーク（または少なくとも非常に悪い使用法）が発生する可能性は非常に低いです。

私の考えでは、メモ化された値は、プログラム内の何か（たとえば、現在の継続、呼び出しスタックなど）に単純に「スコープ」されますが、この主題に関して実用的なものを見つけることができませんでした。

Haskellコンパイラの実装を深く調べていないことは認めますが（怠惰ですか？）、実際にどのように機能するかを誰かに説明してもらえますか？

編集：わかりました、最初のいくつかの答えから私の間違いを理解しています：純粋なセマンティクスは参照透過性を意味します。これは自動メモ化を意味しませんが、問題がないことを保証するだけです。

初心者の観点からは、暗黙のメモ化が可能であるため、参照透過性プロパティは非常に優れているように思われるため、Web上のいくつかの記事はこれについて誤解を招くと思います。

私はこのようなクラスを持っています:

そして、私は疑問に思っています

1) これは、 static classes should not have stateというフレーズに違反していますか?

2) 任意の関数を受け入れることができるように関数を変更するにはどうすればよいですか (上記の状況の代わりに と でのみ動作しF(TResult)ますF(T, TResult)。つまり、別の関数を作成できるということです:

などですが、明らかに、まったくうまくスケーリングしません。

このようなデコレータをどのように書くのでしょうか。デコレーターを呼び出すときに max_hits の値を指定できるようにしたい (または省略可能)。

たとえば、望ましい用途は次のようになります。

また

(最初の例を使用すると、引数が正しくないというエラーが発生します。)

デコレータ:

私が取り組んでいるプロジェクトの場合、同じ結果を返すために計算を信頼できる（そして副作用がない）状態がいくつかあります。明らかな解決策は、コストのかかるすべての機能にメモ化を使用することです。

複数の状態を処理するメモ化が必要になります（別のキャッシュセットを無効にせずに1つのキャッシュセットを無効にできるようにするため）。誰かがこの種のもののための良いCライブラリを知っていますか？（C ++にすることはできません。Cについて話していることに注意してください。）

私はPythonでいくつかの優れた実装を使用して、デコレータを使用してさまざまな関数を柔軟にメモできるようにしました。Cで同様のことを実行できる汎用ライブラリがあるのではないかと思います（ただし、便利な構文ではなく明示的な関数ラッピングを使用している可能性があります）。それが十分に一般的な問題である場合、各関数に個別にキャッシュを追加しなければならないのはばかげていると思います。それに対するいくつかの既成の解決策が必要です。

私が探している特徴は次のとおりです。

1. さまざまなタイプの入力と出力で関数をキャッシュできます
2. 複数の異なるキャッシュを管理します（したがって、短期および長期のキャッシュを使用できます）
3. キャッシュを無効にするための優れた機能があります
4. 既存の関数を変更するのではなく、関数をラップすることによって使用されることを目的としています

これらの必要条件のすべてまたはほとんどを処理できるC実装を知っている人はいますか？

この質問について正確に何をグーグルするかわからないので、SOに直接投稿します：

1. Haskell の変数は不変です
2. 純粋な関数は、同じ引数に対して同じ値になる必要があります

somePureFunc somevar1 somevar2これら 2 つの点から、コードを 2 回呼び出した場合、最初の呼び出し時に値を計算することだけが意味があると推測できます。結果の値は、ある種の巨大なハッシュ テーブル (またはそれに類するもの) に格納でき、その後の関数呼び出しで参照できます。2 つの質問があります。

1. GHC は実際にこのような最適化を行っているのでしょうか?
2. もしそうなら、結果を調べるよりも計算を繰り返す方が実際に安価な場合の動作は何ですか?

ありがとう。

何度か読んだ後でも、 Stoyan Stefanov の「JavaScript パターン」の76 ページにあるこのサンプル コードがどのように機能するかをまだ理解していません。私はまだ忍者ではありません。しかし、私には、空のオブジェクトのみを格納しているように見えます:

その目に見えない「高価な操作」が に保存されていない限り、result何も保持されていません。

結果はどこに保存されますか?

PS: 私はCaching the return results of a function from John Resig's Learning Advanced JavaScriptを読みましたが、これは同様の演習であり、それを取得しました。しかし、ここではコードが異なります。

（動的計画法への）ボトムアップアプローチは、最初に「より小さな」サブ問題を調べ、次により小さな問題の解決策を使用してより大きなサブ問題を解決することから成ります。

トップダウンは、「自然な方法」で問題を解決し、以前にサブ問題の解決策を計算したことがあるかどうかを確認することで構成されます。

私は少し混乱しています。これら2つの違いは何ですか？