4

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

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

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

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

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

4

3 に答える 3

4

You can only memoize a function if all of its inputs are value types or immutable reference types, if it returns either a value type or a new instance of a reference type, and if it has no side effects. Period.

Memoization depends on a deterministic mapping between inputs and outputs. Every call to F(a, b, c) in which a, b, and c contain the same values must return the same result in order for memoization to be possible.

If a parameter's a reference type, then even though its value doesn't change, multiple calls to the function using it may produce a different result. A trivial example:

public int MyFunction(MyType t)
{
   return t.Value;
}

Console.WriteLine(MyFunction(t));
t.Value++;
Console.WriteLine(MyFunction(t));

Similarly, if a function depends on a value external to it, then multiple calls to that function with the same parameters can return different results:

int Value = 0;

public int MyFunction(int input)
{
   return Value;
}

Console.WriteLine(MyFunction(1));
Value++;
Console.WriteLine(MyFunction(1));

And heaven help you if your memoized function does something other than return a value or a new reference type:

int Value = 0;

public int MyFunction(int input)
{
   Value++;
   return input;
}

If you call that function 10 times, Value will be 10. If you refactor it to use memoization and then call it 10 times, Value will be 1.

You can start going down the path of figuring out how to memoize state, so that you can phony up a function that memoizes a reference type. But what you're really memoizing is the set of values that the function works on. You can similarly hack a memoized function that has side effects so that its side effects occur before the memoization. But this is all begging for trouble.

If you want to implement memoization into a function that takes a reference type, the proper approach is to refactor out the part of the function that only works on value types, and memoize that function, e.g.:

public int MyFunction(MyType t)
{
   return t.Value + 1;
}

to this:

public int MyFunction(MyType t)
{
   return MyMemoizableFunction(t.Value);
}

private int MyMemoizableFunction(int value)
{
   return value + 1;
}

Any other approach to implementing memoization that you take either a) does the same thing, through more obscure means, or b) won't work.

于 2009-07-29T20:27:09.943 に答える
3

理論的には、どの関数もメモ化の候補です。ただし、メモ化とはスペースと速度のトレードオフであることを忘れないでください -

一般に、これは、関数が応答を計算するために必要とする、または依存する状態が多いほど、空間コストが高くなり、メソッドをメモ化する望ましさが低下することを意味します。

どちらの例も基本的に、より多くの状態を保存する必要がある場合です。これには 2 つの副作用があります。

まず、より多くの情報を保存する必要があるため、関数をメモ化するために、より多くのメモリ空間が必要になります。

第 2 に、これはメモ化された関数の速度を低下させる可能性があります。これは、スペースが大きいほど、回答の検索のコストが高くなり、結果が以前に保存されているかどうかを確認する際のコストも高くなるためです。

一般に、答えを計算するコストが非常に高くない限り、考えられる入力が少なく、ストレージ要件が低い関数のみを考慮する傾向があります。

これが漠然としていることは認めますが、これは建築における「芸術性」の一部です。両方のオプション (メモ化された機能とメモ化されていない機能)、プロファイリング、および測定を実装せずに「正しい」答えはありません。

于 2009-07-29T17:55:50.523 に答える
2

function の周りにメモ化を提供する AOP ソリューションを提供する方法を既に考えていFooます。

はい、任意の複雑さのオブジェクトをパラメーターとしてメモ化された関数に渡すことができます。これは、それが依存するすべてのものと同様に、不変である限りです。繰り返しますが、現時点ではこれを静的に発見するのは簡単ではありません。

Foo「関数にメモ化を適用するのは良い考えですか?」という質問についてユーザーにアドバイスするために、コードを静的に調べることができるという考えにまだ執着していますか?

それを要件の 1 つにすると、これまで何年も続いてきた世界的な研究活動に参加することになります。あなたがどれだけ野心的かによると思います。

于 2009-07-29T20:43:29.730 に答える