問題タブ [memoization]

高価な計算の結果をキャッシュするために使用しているコンピューティング マップ(ソフト値) があります。

ここで、特定のキーが次の数秒以内に検索される可能性が高いことがわかっている状況があります。そのキーは、ほとんどのキーよりも計算コストも高くなります。

最小優先度のスレッドで値を事前に計算して、値が最終的に要求されたときに既にキャッシュされているようにして、応答時間を改善したいと思います。

次のようにこれを行う良い方法は何ですか:

1. 計算が実行されるスレッド (具体的にはその優先度) を制御できます。
2. 重複作業が回避されます。つまり、計算は 1 回だけ実行されます。計算タスクが既に実行されている場合、呼び出し元のスレッドは、値を再度計算する代わりにそのタスクを待機します (FutureTaskこれを実装します。Guava の計算マップでは、呼び出しのみの場合は true ですがget、呼び出しと組み合わせた場合は異なりますput。)
3. 「事前に値を計算する」方法は、非同期で冪等です。計算がすでに進行中の場合は、その計算が完了するのを待たずにすぐに戻る必要があります。
4. 優先度の逆転を回避します。たとえば、優先度の高いスレッドが値を要求し、優先度が中程度のスレッドが無関係なことを行っているが、計算タスクが優先度の低いスレッドでキューに入れられている場合、優先度の高いスレッドを飢えさせてはなりません。おそらくこれは、計算スレッドの優先度を一時的に上げたり、呼び出しスレッドで計算を実行したりすることで実現できます。

関連するすべてのスレッド間でこれをどのように調整できますか?

追加情報
私のアプリケーションでの計算は画像フィルタリング操作です。つまり、すべて CPU バウンドです。これらの操作には、アフィン変換 (50 マイクロ秒から 1 ミリ秒までの範囲) と畳み込み (最大 10 ミリ秒) が含まれます。もちろん、さまざまなスレッドの優先度の有効性は、OS がより大きなタスクをプリエンプトする能力に依存します。

大量の場合、Haskell で次の関数を効率的に解決する方法に関するポインタ(n > 108)

Haskell でフィボナッチ数を解くためのメモ化の例を見てきました。これには、必要な n までのすべてのフィボナッチ数を (遅延して) 計算することが含まれていました。しかし、この場合、与えられた n に対して、ごく少数の中間結果を計算するだけで済みます。

ありがとう

Python の標準ライブラリのクラスが私のニーズに合わないことがわかった後difflib.SequenceMatcher、問題領域を解決するために一般的な「差分」モジュールが作成されました。再帰アルゴリズムは、何をしているのかをさらに考えるために数か月を費やした後、別の「検索スレッド」も調べた可能性のあるシーケンスで同じ領域を再検索することにより、必要以上に検索しているように見えます。

このモジュールの目的は、diff一連のシーケンス (リスト、タプル、文字列、バイト、bytearray など) の違いと類似性を計算することです。最初のバージョンは、コードの現在の形式よりもはるかに遅く、速度が 10 倍向上しました。次のコードにメモ化をどのように適用できますか? 可能な速度をさらに向上させるためにアルゴリズムを書き直す最良の方法は何ですか?

参照: 再帰アルゴリズムを最適化して繰り返さないようにする方法は?

インターネット上には、さまざまな言語用の自動メモ化ライブラリがいくつかあります。しかし、それらが何のために使用され、どこで使用され、どのように機能するかを知らなければ、その価値を理解することは困難です。メモ化を使用するための説得力のある議論は何ですか? また、メモ化が特に優れているのはどのような問題領域ですか? 情報を知らない人のための情報は、ここで特に高く評価されます。

Rubyにクラスがあるとします。

そして、その結果をメモしたいと思います。したがって、デバッグの目的で、次のようにクラスを変更しました。

そして、同じ引数でメソッドを呼び出すテストを作成して、何が出力されるかを確認しました...そして、メソッドはメモ化されていません。これを行う正しい方法は何ですか？

メモ化プロセスを処理できる以下のようなクラスを作成することは「良い習慣」ですか? メモ化の利点は非常に大きいため (この例のように、関数呼び出しが 501003 秒から 1507 秒に減少し、コンピューターの CPU 時間が 1.409 秒から 0.006 秒に減少する場合もあります)、このようなクラスが役立つと思われます。

ただし、の使用に関する否定的なコメントしか読んだことがありませんeval()。このアプローチが提供する柔軟性を考えると、この使用法は許されますか?

これにより、副作用が失われるという犠牲を払って、返された値を自動的に保存できます。ありがとう。

私はいくつかのHaskellを学び、プロジェクトオイラーの問題を進めてきました。私はオイラー問題（私は喜んでブルートフォースすることができます、または他の言語でそれを行うことができます）への答えについては本当に気になりませんが、方法です。

私は妥当な時間内に問題15を実行することに固執しています。20x20グリッドの左上から右下までの非バックトラックルートの数を要求します。ここにリンク

関数をメモ化（sp？）するというアイデアは当然だと思いますが、その方法がよくわかりません。私はグーグルで検索し、Haskell Cafeでこれに出くわしました。これは、素朴に適応しようとしましたが、最終的には次のようになりました。

これは見栄えが悪く、パフォーマンスがひどいです（ナイーブバージョンよりもはるかに遅い）。問題は、Haskellのメモ化がどのように機能するのか本当に理解していないことです。

例として私のコードを使用して、誰かがa）私のものがとても遅い理由
b）それがどのように行われるべきか（私が出くわした解決策であった可変性を使用せずに）
c）この場合のメモ化がどのように機能するかを説明したいと思いますか？

どうにかしてメモ化と末尾再帰を組み合わせることができますか? 私は現在 F# を学んでおり、両方の概念を理解していますが、それらを組み合わせることができないようです。

次のmemoize関数があるとします ( Real-World Functional Programmingから):

および次のfactorial関数:

メモ化factorialはそれほど難しくなく、末尾再帰にすることも難しくありません。

しかし、メモ化と末尾再帰を組み合わせることができますか? 私はいくつかの試みをしましたが、うまくいかないようです。それとも、これは単に不可能ですか？

私はLispを学ぼうとしているだけなので、プロジェクトオイラーの問題を経験しています。問題はありませんでした。14興味深い（この問題を解決することを計画している場合は、解決策を下部に貼り付けたので、今すぐ読むのをやめてください）。私のアルゴリズムでは非常に低速でしたが、メモ化を使用した後（Paul Grahamの「onLisp」の本から関数をコピーしました）、はるかに高速でした（約4〜8秒）。

私の質問は、私が受け取ったこの一連の警告についてです：私は何か間違ったことをしていますか？自分のスタイルを改善できますか？

これはコードです：

どうもありがとう、そしてありそうなエラーを許して、私はLispから始めたばかりです。Br

更新： 私が書いた最終的なコードを共有したいと思います。メモ化のためにカスタム外部ハッシュテーブルを使用し、最終ループを改善します。

画像を動的に生成するCherryPyアプリがあり、それらの画像は頻繁に再利用されますが、毎回生成されます。画像は変数を含むクエリ文字列から生成されるため、同じクエリ文字列は常に同じ画像を返し（生成コードを書き直すまで）、画像はユーザー固有ではありません。

これらの画像を積極的にキャッシュする必要があると思いましたが、どうすればよいかわかりません。CherryPyでメモ化する必要がありますか？Apacheに対してこのようなことをする必要がありますか？完全に別のレイヤー？