4

我决定使用 PostSharp（与魔法无异）来读取属性和记忆函数。函数调用的哈希将是键，并且将返回缓存（在Velocity中）的结果，而不是再次调用该函数。简单的peasy，mac-and-cheesy。

我已经放弃了检测装饰函数中的副作用，这被证明是一个“难题”，即使对于专家来说也是如此，我当然不是。接下来，我必须弄清楚还有哪些其他函数可以用于记忆。

  • 将复杂引用类型作为参数的方法呢？
  • 依赖于调用它们的实例内部数据的方法呢？

最后一个是 ActiveRecord 式的数据对象。

我是否将不得不重构一周前的代码以支持记忆？

4

3 回答 3

4

如果函数的所有输入都是值类型或不可变引用类型，如果它返回值类型或引用类型的新实例，并且没有副作用，则只能记忆函数。时期。

记忆依赖于输入和输出之间的确定性映射。每次调用F(a, b, c)a、b 和 c 包含相同的值时，都必须返回相同的结果，以便记忆化成为可能。

如果参数是引用类型，那么即使它的值没有改变，多次调用使用它的函数可能会产生不同的结果。一个简单的例子：

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

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

类似地，如果一个函数依赖于它外部的值，那么使用相同参数多次调用该函数可能会返回不同的结果：

int Value = 0;

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

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

如果你的记忆函数做的不是返回值或新的引用类型，那么天堂会帮助你：

int Value = 0;

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

如果您调用该函数 10 次，Value将是 10。如果您将其重构为使用记忆化，然后调用它 10 次，Value将是 1。

你可以开始研究如何记忆状态，这样你就可以伪造一个记忆引用类型的函数。但是你真正记住的是函数工作的一组值。您可以类似地破解具有副作用的记忆函数，使其副作用发生在记忆之前。但这都是自找麻烦。

如果您想将 memoization 实现为采用引用类型的函数，正确的方法是重构仅适用于值类型的函数部分，并 memoize 该函数，例如：

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

对此：

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

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

您采取的任何其他实现记忆的方法a）通过更晦涩的方式做同样的事情，或者b）将不起作用。

于 2009-07-29T20:27:09.943 回答
3

好吧，理论上，任何函数都是记忆化的候选者。但是，请记住，记忆化就是为了速度而交易空间——

一般来说，这意味着，一个函数需要或依赖的状态越多来计算答案，空间成本就越高，这降低了记忆该方法的可取性。

您的两个示例基本上都是需要保存更多状态的情况。这有两个副作用。

首先，这将需要更多的内存空间来记忆函数，因为需要保存更多信息。

其次，这可能会减慢记忆函数，因为空间越大，查找答案的成本就越高，而且查找结果是否先前保存的成本也越高。

一般来说，我倾向于只考虑可能输入很少且存储要求低的函数，除非计算答案的成本非常高。

我承认这是含糊的，但这是建筑“艺术”的一部分。如果不实现两个选项（记忆和非记忆函数）、分析和测量，就没有“正确”的答案。

于 2009-07-29T17:55:50.523 回答
2

您已经想到了一种方法来提供 AOP 解决方案来提供围绕 function 的 memoization Foo，那么还有什么需要弄清楚的呢？

是的，您可以将任意复杂度的对象作为参数传递给记忆函数，只要它是不可变的，就像它所依赖的所有东西一样。同样，目前这一点也不容易静态地发现。

您是否仍然坚持可以静态检查代码以便就“将记忆应用于函数是否是个好主意”这个问题向您的用户提供建议的想法Foo？

如果您将其作为您的要求之一，您将加入一项迄今已持续多年的全球研究工作。取决于你有多大的野心，我猜。

于 2009-07-29T20:43:29.730 回答