問題タブ [memoization]

初期化中にキャッシングするために、通常、DB からグローバル定数にデータをロードして保存する方法を教えてください。グローバル定数は後で再び変更されることはありません。読み込み時に DB クエリを作成して定数に入れるだけですか、それとも何らかの遅延読み込みメカニズムを使用しますか?

私が念頭に置いているのは、次のようなグローバル スコープのコードです。

空のテスト データベースを使用してテストを実行すると、問題が発生しました。オプションは、必要なすべてのデータをフィクスチャに入れることですが、個々のテストを必要のない無関係なデータと結合することは避けたいと思います。

以下は良いスタイルと見なされますか?

それとも、一般的な再利用可能なメカニズムが優先されますか?

怠惰な関数呼び出しをカプセル化するPythonの方法はありますか？それにより、関数を最初に使用するf()と、以前にバインドされた関数がg(Z)呼び出され、後続の呼び出しf()でキャッシュされた値が返されますか？

メモ化は完全に適合しない場合があることに注意してください。

私は持っています：

g(Z)コードは機能しますが、値が使用されている場合にのみ呼び出されるように再構築したいと思います。の定義を変更したくないので、キャッシュするg(...)にZは少し大きいです。

編集：私はそれfが関数でなければならないと思いましたが、そうではないかもしれません。

このコードを含む記事を見つけました：

これを説明してもらえますか？ここでは多くのことを理解できませんが、最も奇妙なことは、キャッシュがローカルで静的ではないことですが、おそらく私は間違っていて...

私はこの素敵なメモ化デコレータを見つけました:

http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

特定のアプリケーションは人工知能であり、不変の状態クラス内に存在します。問題は、要求されたオペレーターが適用された状態で、親状態の copy.copy を返すことによって、オペレーターの適用を実行することです。copy.copy は、ほとんどの状態がその親と同じであるため、無駄になる時間を大幅に節約します。

さて、ここに私の問題があります。クラス内で上記のメモ化クラスを使用すると、潜在的に無効な値にメモ化される関数のメモ化されたコピーが渡されますか? どうにかしてメモ化されたコピーを無効にする必要があると思います。

私は、numpy 行列と ndarray を扱う、かなり計算量の多い計算に取り組んでいます。掘り下げてみると、メモ化を実装しない方法が約 12 あります。通常は衝突が多く、ndarray が変更可能なオブジェクトであるという問題があります。

派手なオブジェクトを処理できるかなり一般的なメモ化デコレータに出くわした人はいますか?

最近いくつかのコードを最適化する際に、メモ化の「タイプ」と思われるものを実行することになりましたが、それをそう呼ぶべきかどうかはわかりません。以下の疑似コードは実際のアルゴリズムではありません (アプリケーションで階乗をほとんど必要とせず、そのコードを投稿することは違反であるため)、私の質問を説明するには十分なはずです。これはオリジナルでした：

十分に単純ですが、次のように、より大きな数に対して多数の計算を回避できるように、固定小数点を追加しました。

もちろん、これは が効率の悪い ではなく12!として計算されたことを意味します。12 * 11 * 362880012 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

しかし、これをメモ化と呼ぶべきかどうかは疑問です。これは、過去の計算結果を記憶して使用することと定義されているようです。これは、ハードコーディングされた計算 (覚えていない) とその情報を使用することに関するものです。

このプロセスに適切な名前はありますか? それとも、メモ化は、実行時に行われる計算だけでなく、コンパイル時に行われる計算にも、コードを書き始める前に頭の中で行われる計算にも及ぶと主張できますか?

レーベンシュタイン距離(編集距離)の通常の動的計画法のアルゴリズムを実装したいとしましょう。再帰を考え出すのはとても簡単です:

これは指数関数的な実行時間の影響を受けるため、関数をメモする必要があります。私は Data.Memocombinators を使用してこれを行いたいと考えており、いくつかの方法を試しました。これが私の現在の試みです：

ただし、少なくとも多項式であるため、メモ化によって実行時間が大幅に改善されると予想されますが、メモ化には何の効果もないようです。実装の何が問題になっていますか? 編集距離の高レベルの定義を可能な限り維持しながら、適切な実行時間を取得するにはどうすればよいですか?

次のような IO アクションがあるとします。

これは、DNS ルックアップや、時不変データに対する Web サービス呼び出しなどの単純なものである可能性があります。

次のように仮定します。

1. 操作は例外をスローしたり、発散したりしません。

2. モナドがなければIO、関数は純粋になります。つまり、同じ入力パラメータに対して結果は常に同じになります。

3. アクションは再入可能です。つまり、複数のスレッドから同時に安全に呼び出すことができます。

4. このlookupStuff操作にはかなりの (時間) 費用がかかります。

私が直面している問題はunsafe*IO*、複数のスレッドから呼び出すことができる再入可能キャッシュを適切に (そしてチートを使用せずに) 実装し、同じ入力パラメーターに対する複数のクエリを単一の要求に結合する方法です。

私は、純粋な計算のための GHC のブラックホールの概念に似たものを求めていると思いますが、IO の「計算」のコンテキストにあります。

上記の問題に対する慣用的な Haskell/GHC ソリューションは何ですか?

この回答とこのwikiページは、Haskellでのメモ化の優れた紹介であることがわかりました。しかし、彼らは私に答えを期待している質問を残しています。

使用されている手法では、メモ化を保存するために使用するデータ構造を「開く」(「内部にアクセスする」など) 必要があるように思えます。たとえば、セクション 3で1はテーブル構造を実装し、 2はツリーを実装します。事前に作成されたデータ構造で同様のことを行うことは可能ですか? たとえば、これは本当に素晴らしいと思い、メモ化された値をそのような .xml ファイルに保存したいとします。構造自体を実装せずに、事前に作成されたものを使用する、このような事前に作成されたデータ構造を使用してメモ化にアプローチできますか?Data.MapMap

うまくいけば、誰かが私に考え方のヒントを与えてくれるか、またはおそらく、機能的なメモ化全般に関する私の誤解を正してくれるでしょう。

編集：私はそれを行う1つの方法を考えることができますが、それはまったくエレガントではありません：もしf :: a -> b、f' :: Map a b -> a -> (Map a b, b)最初の引数がメモ化ストレージであり、出力ペアが潜在的に更新されたストレージと計算値。この状態渡しは確かに私が望んでいるものではありません (モナドでラップすることもできると思いますが、 1と2のアプローチよりも数桁醜いです)。

編集 2:私の現在の (間違った) 考え方を表現するのに役立つかもしれません。現在、私は自分の意志に反して、非解決に自分自身を引き込むことを繰り返しているようです

これを見れば見るほど、基本的なことを誤解していることに気づきます。ほら、 my はmemoizer の1memo [True, False]と同等だと私には思えます。bool

Haskellを介してCRCを調べ続けると、CRC32計算用のテーブルを生成するために次のコードを記述しました。

これにより、テーブルが正しく生成されます。このテーブルに頻繁にアクセスしたいのですが、1）結果をコードにハードコードしたくない、2）参照するたびにこのテーブルを再計算したくない。

Haskellでこの配列をメモ化するにはどうすればよいですか？Haskellのメモ化ページは私に手がかりを与えてくれませんでした。