問題タブ [memoization]

この三角形には、0 から 4 までの整数の膨大な配列があります。私は Ruby で動的プログラミングを学ぼうとしていますが、次の 3 つの基準を満たす三角形内のパスの数を計算する際に助けが必要です。

1. 70 要素の行のゼロ点の 1 つから開始する必要があります。
2. あなたのパスは、あなたの 1 行真上 (真上に数字がある場合) または 1 行上、左斜め上にある可能性があります。これらのオプションのいずれかが常に利用可能です
3. 最初の行のゼロに到達するまでの経路の合計は、140 になる必要があります。

たとえば、一番下の行の 2 番目のゼロから開始します。1 まで直接移動することも、左斜め 4 まで移動することもできます。1 から真上にある 2 (合計 = 3)、または左斜め上にある 0 (合計 = 1) に移動できます。

2008年7月中旬に、メモ化がRailsコアに追加されました。使用法のデモンストレーションはここにあります。

メソッドをメモ化するタイミングと、それぞれのパフォーマンスへの影響について、良い例を見つけることができませんでした。たとえば、このブログ投稿は、メモ化をまったく使用すべきではないことを示唆しています。

パフォーマンスに多大な影響を与える可能性のあるものについては、簡単なチュートリアルを提供する以上のリソースはほとんどないようです。

自分のプロジェクトでメモ化が使用されているのを見た人はいますか？メソッドのメモ化を検討する要因は何ですか？

自分でさらに調査したところ、Railsコア内でメモ化がかなりの回数使用されていることがわかりました。

次に例を示します：http：//github.com/rails/rails/blob/1182658e767d2db4a46faed35f0b1075c5dd9a88/actionpack/lib/action_view/template.rb。

この使用法は、メモ化がパフォーマンスに悪影響を与える可能性があるという上記のブログ投稿の結果に反しているようです。

Class::DBIから継承するかなり複雑な ORM モジュールのセットがあります。データはめったに変更されないため、この上にキャッシング/メモ化レイヤーを使用して処理を高速化することを検討しています。モジュールClass::DBI::Cacheableを見つけましたが、RT に関する評価やレビューはありません。これまたは他の Class::DBI キャッシング スキームを使用したことがある人からの連絡をお待ちしています。

ありがとうございます。

次の点を考慮してください。

私は新しいのですが、キャッシュはデコレータに分解できると思います。私はそれのようなものを見つけられませんでした;）

PS実際の計算は可変値に依存しません

私は次のようなモデルを持っています:

balance メソッドを memoize して memcached に保存したい。もちろん、問題は、支払いまたは購入が作成されるたびに、キャッシュされた値が期限切れになる必要があることです。支払いと購入の after_save コールバックにコードを挿入して、キャッシュされたアカウントの残高を期限切れにすることもできますが、次のように言えば理解しやすく維持しやすいと思います。

これを行う既存の宝石/プラグインはありますか? そして、私が出かけて自分自身を書く前に、それは良い考えですか? 私が見るマイナス面は、 Purchase のdollar_mount メソッドを変更している人にとって、キャッシュの問題を考慮する必要があることがわかりにくくなる可能性があることです (SubPurchase などの別のモデルへの依存関係を無意識のうちに導入した場合、それはしかし、これはとにかく明白ではないので、きちんとした宣言構文を持つことには価値があると思います - 少なくともそれが壊れたとき、それを修正する方法は明らかです

考え？

編集：セマンティックアートの答えに応えて、「関連するコールバックに有効期限を入れるだけ」というアプローチで私の問題についてより明確にします-問題は、コードベース全体に有効期限が切れることです-それは after_save コールバックで始まります私が提案している構文では、開発者はこれらすべてのケースを 1 か所のきちんとしたリストに保持する必要があります。そうすれば、「ユーザーの残高が同期していないことがあり、問題を再現する方法がよくわからない」などのバグ レポートを受け取ったときに、何が起こっているのかを簡単に把握できます。

使うべきかif defined?

または||=

if defined?最近、この方法がますます使用されていることに気付きました。どちらか一方に利点はありますか？個人的に||=は読みやすさ重視。memoizeまた、Rails には、この動作を透過的に提供するマクロが含まれている可能性があると思います。これは事実ですか？

Pickle は特定の入力値に対して常に同じ出力を生成しますか? 内容が同じで挿入/削除の履歴が異なる辞書をピクルする場合、問題が発生する可能性があると思います。私の目標は、メモ化の実装のために、Pickle と SHA1 を使用して、関数の引数の「署名」を作成することです。

実装し始めているキャッシングのアイデアがあります。

関数をメモ化し、関数シグネチャのハッシュとともに戻り値をVelocityに保存します。PostSharpを使用して、関数を再度呼び出すのではなく、キャッシュをチェックして、戻り値の再水和された表現を返したいと思います。この動作を制御するために属性を使用したいと思います。

残念ながら、これは私の組織の他の開発者にとって危険であることが判明する可能性があります。彼らがパフォーマンスの向上に夢中になり、副作用のあるものも含めて、キャッシュ属性ですべてのメソッドを装飾し始める場合です。関数が副作用を引き起こす可能性があるとメモ化ライブラリが疑った場合、コンパイラの警告を出したいのですが。

CodeDomまたはReflectionを使用して、コードが副作用を引き起こす可能性があることをどのように知ることができますか？

PostSharp (魔法と見分けがつかない) を使用して属性を読み取り、関数をメモすることにしました。関数呼び出しのハッシュがキーになり、関数を再度呼び出す代わりに ( Velocityに) キャッシュされた結果が返されます。簡単にピージー、マックアンドチーズ。

私はすでに装飾された関数の副作用を検出できることをあきらめました。これは、専門家にとっても「難しい問題」であることが判明しましたが、私は確かにそうではありません。次に、メモ化の候補となる他の関数を特定する必要があります。

• 複雑な参照型をパラメーターとして受け取るメソッドについてはどうでしょうか?
• 呼び出されたインスタンス内のデータに依存するメソッドはどうですか?

ActiveRecord 風のデータ オブジェクトは、その最後のオブジェクトで思い浮かびます。

メモ化をサポートするために、1 週間前のコードをリファクタリングする必要がありますか?

ラップされたクラスと直接やり取りせずに、汎用クラスに機能を追加するクラスを作成しようとしています。この良い例は、スマート ポインターです。具体的には、ラッパーを介して呼び出された 1 つの (または任意の) メソッドのすべての i/o をキャッシュするラッパーを作成したいと考えています。理想的には、キャッシュ ラッパーには次のプロパティがあります。

• ラッピング クラスを何らかの方法で変更する必要はありません (つまり、ジェネリック)。
• ラップされたクラスを何らかの方法で変更する必要はありません (つまり、ジェネリック)。
• オブジェクトを使用するためのインターフェースや構文を大幅に変更することはありません

たとえば、次のように使用すると非常に便利です。

このような間抜けなものは問題ありませんが：

これは C++ で可能であるべきだと思いますが、おそらくどこかで構文上の体操が必要になるでしょう。

何か案は？