代码之家 › 专栏 › 技术社区 › Chris McCall

记忆化的候选函数是什么?

memoization c#

Chris McCall · 技术社区 · 15 年前

我决定用PostSharp(与魔法无法区分)来读取属性和 memoize functions . 函数调用的哈希将是键和缓存的 Velocity )将返回结果,而不是再次调用函数。简单的花生,苹果和奶酪。

我已经 given up 在能够检测到装饰功能的副作用上,这是一个“难题”,即使是对专家来说,我当然不是。接下来,我要弄清楚还有哪些功能是记忆化的候选者。

在最后一个问题上,我们想到了ActiveRecord风格的数据对象。

我需要重构一周前的代码来支持内存化吗?

3 回复 | 直到 15 年前

Robert Rossney 15 年前

只有当一个函数的所有输入都是值类型或不可变的引用类型、返回值类型或引用类型的新实例以及没有副作用时,才能对该函数进行memoize。期间。

记忆化依赖于输入和输出之间的确定性映射。每次召唤 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));

如果您的memoized函数除了返回一个值或一个新的引用类型之外还执行其他操作,那么天堂会帮助您:

int Value = 0;

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

如果你调用这个函数10次, Value 将是10。如果您重构它以使用memoization,然后调用它10次, 价值 将是1。

你可以开始研究如何记忆状态,这样你就可以伪造一个记忆引用类型的函数。但是你真正记忆的是函数所使用的一组值。你同样可以破解一个有副作用的记忆函数,使其副作用发生在记忆之前。但这都是在乞求麻烦。

如果要将memoization实现为采用引用类型的函数,则正确的方法是重构只对值类型起作用的函数部分,并将该函数memoization,例如:

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)都不起作用。

Reed Copsey 15 年前

从理论上讲,任何函数都是记忆化的候选者。然而,记住,记忆化是关于速度的交易空间。-

一般来说,这意味着,函数在计算答案时需要或依赖的状态越多,空间成本就越高,这就降低了对该方法进行记忆的必要性。

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

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

第二,这可能会减慢记忆化功能的速度,因为空间越大,查找答案的成本就越高,而且查找结果之前是否保存的成本也越高。

一般来说,我倾向于只考虑具有很少可能的输入和低存储需求的功能,除非在计算答案时有非常高的成本。

我承认这是模糊的,但这是建筑中“艺术性”的一部分。如果不实现这两个选项(memozied和non memoized函数)、分析和测量,就没有“正确”的答案。

Daniel Earwicker 15 年前

您已经想到了一种方法来提供AOP解决方案,以提供围绕函数的memoization Foo 还有什么问题要解决?

是的,可以将任意复杂度的对象作为参数传递给一个memoized函数,只要它是不变的,它所依赖的所有东西也是不变的。再说一次,目前静态地发现这一点并不容易。

您是否仍然坚持这样一个观点,即您可以静态地检查代码,以便就“将memoization应用于函数是一个好主意吗?” 福 “

如果你把这作为你的要求之一,你将加入一个持续多年的全球研究工作。我想这取决于你有多雄心勃勃。