問題タブ [memoization]

「Intermediate Perl」を試していますが、かなりクールです。「The Schwartzian Transform」のセクションを終えたところですが、それが沈んだ後、なぜ変換がキャッシュを使用しないのか疑問に思い始めました。いくつかの繰り返し値を持つリストでは、変換によってそれぞれの値が再計算されるため、結果をキャッシュするためにハッシュを使用しない理由を考えました。ここにいくつかのコードがあります：

何か不足していますか？Schwartzian 変換のキャッシュ バージョンが本にリストされていないのはなぜですか?

編集: daxim は、これは orcish操作として知られているコメントで指摘しました。だから、名前はよくわからないけど、頭がおかしくなったわけじゃない。

Pythonマルチスレッドメモ化は可能ですか? もしそうなら、どのように？

データベース内の文字列値の実際の変換値への変換をメモ化するために使用する一般的な方法があります。

問題は、初期化中にデータベース内のデータのタイプがわからないことです。この決定を行うことができるのは最初の呼び出しのみです。

キャッシュされている値の型をボックス化解除することを強制されないように構造化する方法はありますか? (包含クラスの署名を変更せずに)

私が欲しいのは、次のようなメモ化デコレータです。

• 引数とキーワード引数の両方でインスタンスメソッドをメモ化できます
• 1回の呼び出しで（グローバルに）クリアできるキャッシュがあります（関数ごとのキャッシュを使用するこのキャッシュ：python resettable instance method memoization decorator）
• かなり効率的です

私が見た例を微調整して、次のように思いつきました。

それに関する私の問題は、キャッシング部分が多くのオーバーヘッドを伴うように見えることです（たとえば、再帰関数の場合）。次の関数を例として使用すると、メモ化されていないバージョンでは、メモ化されたバージョンよりも短い時間で fib(30) を 10 回呼び出すことができます。

このデコレータを書くためのより良い方法を提案できる人はいますか? （または、私が望むことを行うより良い（つまり、より高速な）デコレータを教えてください）。メソッドのシグネチャを保持したり、イントロスペクション ツールが装飾された関数について「認識」できるようにすることには興味がありません。

ありがとう。

PS Python 2.7の使用

Data.MemoCombinatorsのソースを調べてきましたが、その中心がどこにあるのか実際にはわかりません。

これらすべてのコンビネータの背後にあるロジックと、実際のプログラミングでプログラムを高速化するために実際にどのように機能するかについて説明してください。

この実装の詳細と、オプションでメモ化に対する他のHaskellアプローチとの比較/対比を探しています。私はメモ化とは何かを理解しており、一般的にどのように機能するかについての説明を探していません。

以下のコードは、人気のあるトップコーダーの問題であるFourBlocks (ログインする必要があります) に対する回答です。このソリューションでは、ビットマスクメモ化を使用して、サイズ 1 のブロックとサイズ 4 の正方形ブロックを使用してグリッド内の最大合計を見つけます。これは何をしますか

また、関数 rec() はどのように正方形に収まりますか?? 2ビットを比較するだけです。

あなたがルビープログラマーなら、ハッシュブロックのメモ化パターンに出くわしたかもしれません。簡単な例として、フィボナッチ数列のメモ化バージョンを紹介します。

もちろん、これがフィボナッチ数列のメモ化バージョンを作成する唯一の方法ではありません。次のこともできます。

うまくいけば、ハッシュブロックのメモ化パターンが他の多くの言語ではるかに一般的な2番目のバージョンにどのようにマッピングされるかがわかります。私が知りたいのは、2つのバージョンの間に違いがあるかどうかです。ハッシュブロックバージョンの方が効率的だという気持ちを揺るがすことはできませんが、その理由を正当化することはできません。

インスタンス変数をキャッシュする手法には、特定の「アカデミック」な名前がありますが、思い出せません。私を助けてください。

マーシャリングはマーシャリングと呼ばれます。
遅延読み込みは遅延読み込みと呼ばれます。
説明されているテクニックは...と呼ばれていますか？

Haskell で0-1 ナップサック問題をコード化しました。これまでに達成された怠惰さと一般性のレベルについて、私はかなり誇りに思っています。

まず、遅延 2 次元行列を作成して処理するための関数を提供します。

次に、特定のナップザックの問題について特定の表を作成します

最後に、テーブルを表示するためのヘルパー関数をいくつか追加します。

ここまではかなり簡単でした。しかし、私はそれをさらに一歩進めたいと思っています。

テーブルのデータ構造を改善したい。理想的には、

• ボックス化されていない (不変) [編集] 気にしないで
• 怠惰
• 無制限
• O(1)構築する時間
• O(1)特定のエントリを検索するための時間の複雑さ
  (より現実的には、最悪のO(log n)場合、ni*jは行 i、列 j のエントリを検索するためのもの)

ソリューションがこれらの理想を満たしている理由/方法を説明できればボーナス ポイントです。

knapsackTableをさらに一般化し、それが効率的であることを証明できれば、ボーナス ポイントも得られます。

データ構造を改善するには、次の目標を満たすようにしてください。

• 最大重みが 10 であるソリューションを求める場合 (私の現在のコードではindexTable knapsackTable 5 10、5 は項目 1 ～ 5 を含むことを意味します)、必要最小限の作業のみを実行する必要があります。理想的には、これはO(i*j)、テーブルの各行の背骨を必要な列の長さに強制する作業がないことを意味します。DP がテーブル全体を評価することを意味すると考える場合、これは「真の」DP ではないと言えます。
• テーブル全体を印刷するように要求した場合 (のようなものprintTable knapsackTable 5 10)、各エントリの値は一度だけ計算する必要があります。特定のセルの値は、他のセルの値に依存する必要があります (DP スタイル: 考え方として、同じ部分問題を 2 回再計算しないでください)。

アイデア:

• Data.Array境界 :(
• UArray厳密 :(
• メモ化技術（HaskellのDPに関するSOの質問）これはうまくいくかもしれません

私の述べた理想にある程度の妥協をする回答は、有益である限り、（とにかく私によって）支持されます。妥協が最も少ない答えは、おそらく「受け入れられる」ものになるでしょう。