問題タブ [memoization]

私はまだ実装していないアイデアを持っています。なぜなら、間違ったツリーを吠えているのではないかと心配しているからです...主に、トピックに関するグーグル検索で返される結果が非常に少ないためです。

基本的に、時間のかかるサブクエリがあるため、遅い SQL クエリがいくつかあります。たとえば、「10 歳から 15 歳までの男の子が乗っている赤い自転車をすべて数えてください」といったようなことを行うかもしれません。これはすべての自転車をスロッシングするためコストがかかりますが、最終結果は 1 つの数値になります。私の場合、その数値が 100% 最新である必要はありません。

この種の問題に対する究極の解決策は、OLAP ベースのエンジンを適用してこれらの順列を事前にキャッシュすることです。ただし、私の場合、大量のメトリクスに基づいてデータを細かく分割しようとしているわけではなく、別のプロセス/データストアを実行してアーキテクチャを複雑にする必要はありません。

だから...私の考えは、基本的にデータベース内のこれらのサブクエリをメモ化することでした。「BicycleStatistics」というテーブルがあり、上記のサブクエリの出力を入力と出力の名前と値のペアとして保存する場合があります。

例の名前: "c_red_g_male_a_10-15" 値: 235

また、クエリが実行されるときに、それらの値をそのテーブルにメモするメカニズムがあります。

誰かがこの状況にあり、同様のことを試みましたか? このようなソリューションが「DB に大量の RAM を投入し、データベースに処理させる」よりも価値があると考える理由は、(A) 私のデータベースは、便利に投入できる RAM の量よりも大きく、( B) データベースは、これらの統計の正確な数値を取得することを保証します。上記の私の大きな利点は、数値が 1 日か 2 日遅れても問題ないことです。

ご意見やご感想をお寄せいただきありがとうございます。

トム

現在人気のある関数型言語のいずれかがメモ化を適切にサポートしていますか？メモ化の強さから1つを選択する場合、どのようなものをお勧めしますか？その理由は何ですか？

更新：有向グラフ（ノードは関数またはデータである可能性があります）を最適化することを検討しています。グラフ内のノードが更新されたときに、変更されたノードに依存している場合にのみ、他のノードの値を再計算したいと思います。

Update2：無料またはオープンソースの言語/ランタイムが必要です。

Ruby on Railsを使用していますが、別のサーバーに接続して取得した検索結果セットを保存する必要があります。問題は、結果セットをセッションに保存したくないことと、結果セットオブジェクトを複数のリクエストに保存できるものが必要なことです。

クエリには時間がかかるので、繰り返したくありません。オブジェクトを保存したり、オブジェクトをキャッシュしたりして、何度もクエリを実行する必要がないようにする方法はありますか？

ある種のオブジェクトストアを使用できますか？

どんな助けでも素晴らしいでしょう。

メモ化がオプションの場合、オブジェクトをメモ化するにはどうすればよいですか？接続にはまだ時間がかかるので、結果セットを保存する方法。

ここに示されている方法を使用する：http：//cslibrary.stanford.edu/110/BinaryTrees.html#java

n（n-1）（n-2）... 1、つまりn！

メモ化ツールを使用する場合、複雑さはO（n）ですか？

pow()末尾再帰的であり、メモ化を使用して繰り返し計算を高速化する計算アルゴリズムを探しています。

パフォーマンスは問題ではありません。これは主に知的な演習です。電車に乗って、可能な限りさまざまなpow()実装を考え出しましたが、これら 2 つの特性を備えた満足のいく実装を思い付くことができませんでした。

私のベストショットは次のとおりでした。

動作しますが、すべての計算結果を記憶するわけではありません - 指数1..exp/2とexp.

私は整数のセットを持っています。動的計画法を使用して、そのセットの最長増加サブシーケンスを見つけたいです。

System.Transactionsは、同じデータベースへの複数の接続を含むトランザクションをDTCにエスカレートすることで有名です。以下のモジュールとヘルパークラスはConnectionContext、同じデータベースに対する複数の接続要求が同じ接続オブジェクトを返すようにすることで、これを防ぐことを目的としています。これは、ある意味でメモ化ですが、メモ化されるものは複数あり、2番目は最初のものに依存しています。このモジュールで同期および/または可変状態（おそらくメモ化を使用）を非表示にする方法、またはより機能的なスタイルで書き直す方法はありますか？

（Transaction.Currentはであるため、接続文字列で接続を取得するときにロックがないことは何の価値もありませんThreadStatic。）

任意の数の引数を持つ関数のメモ化インターフェイスを作成しようとしていますが、悲惨なことに失敗しています。私のソリューションはあまり柔軟ではないように感じます。実行時に自動的にメモ化される関数のインターフェイスを定義しようとしましたが、各関数はこのインターフェイスを実装する必要があります。これは、2つのパラメーターの指数移動平均関数を使用した例です。

これが私の関数のテストです：

更新：
私のn00bishエラーを指摘してくれてありがとう...私はいつもストップウォッチでリセットを呼び出すのを忘れています！

メモ化への別のアプローチも見ました...これはn引数のメモ化を提供しませんが、関数ごとにクラスを作成する必要があるため、インターフェイスを使用したアプローチはそれほど有利ではありません。これらのアイデアをより堅牢なものにマージできる合理的な方法はありますか？ユーザーが使用する関数ごとにクラスを作成することなく、関数を簡単にメモ化できるようにしたいと思います。

スキームで配列を使用するにはどうすればよいですか?

特に、メモ化を使用して再帰的なフィボナッチ プロシージャを実装しようとしています。配列はSchemeにも存在しますか?

そうでない場合、メモ化をどのように実装できますか?

新生児のクロジュリアンとして、私は言語を学ぶ方法としてプロジェクトオイラーの問題を経験することを勧められました。それは間違いなくあなたのスキルを向上させ、自信を得るのに最適な方法です。問題＃14の答えを終えたところです。正常に動作しますが、効率的に実行するには、メモ化を実装する必要がありました。コードの構造が原因で、あらかじめパッケージ化された関数を使用できませんでした。とにかく自分でロールするのは良い経験だったと思います。私の質問は、関数自体の中にキャッシュをカプセル化する良い方法があるかどうか、または私が行ったように外部キャッシュを定義する必要があるかどうかです。また、私のコードをより慣用的にするためのヒントをいただければ幸いです。memoize