什么是备忘录有用,它真的有用吗？

Question

互联网上有一些自动记忆库可用于各种不同的语言; 但不知道它们的用途,使用方法以及它们的工作原理,很难看出它们的价值.使用memoization有什么令人信服的论据,以及memoization特别闪耀的问题域是什么？这里特别感谢不知情的信息.

Answer 1

在我看来,Fibonacci和阶乘计算并不是最好的例子.当你拥有以下内容时,备忘录真正发挥作用:

1. 有关计算的大量潜在输入,但范围仍然明显受到限制和已知
2. 您事先知道程序的任何实际使用只会使用一小部分可能的输入来计算(Fibonacci和factorial会失败)
3. 您不知道在运行时将使用哪些特定输入,因此需要记住哪些特定结果(Fibonacci和factorial也失败了,直到某一点)

显然,如果您确实知道所有可能的输入,并且空间允许,您可以考虑用查找替换该函数(这是我用的,例如,使用已知生成器的嵌入式CRC32实现).

...甚至比#2更好的是,如果对于程序的任何特定运行,您可以立即说"潜在输入的范围将被限制为满足这些条件的子集......".

请注意,其中很多可能是概率性的(或直观的) - 当然,有人可能会尝试所有10 ^ 13种可能的输入来进行魔法计算,但是你知道它们实际上不会.如果他们这样做,记忆的开销实际上对他们没有好处.但你可能会认为这是可以接受的,或者允许在这种情况下绕过备忘录.

这是一个例子,我希望它不是太复杂(或概括)来提供信息.

在我写的一些固件中,程序的一部分从ADC读取,可以是来自的任何数字0x000,0xFFF并计算程序的其他部分的输出.此计算还采用一组用户可调数字,但这些数字仅在程序启动时读取.这个计算在它第一次运行时非常受欢迎.

提前创建查找表是荒谬的.输入域是[ 0x000,...,0xFFF]和(大范围的浮点值)和(另一个大范围......)的笛卡尔积和... ...不,谢谢.

但是当条件变化很快时,没有用户要求或期望设备能够正常工作,并且当事情稳定时,他们更愿意更好地工作.因此,我在反映这些要求的计算行为中进行权衡:我希望这个计算在事情稳定时很好而且快速,而我不关心它们何时不是.

给定典型用户期望的"缓慢变化的条件"的定义,该ADC值将稳定到特定值并保持在其稳定值的约0x010内.哪个值取决于条件.

因此,可以为这16个潜在输入记忆计算结果.如果环境条件做改变速度快于预期,"最远" ADC从最近被丢弃读取(例如,如果我缓存0x210到0x21F,然后我读0x222,我把0x210结果).

这里的缺点是,如果环境条件变化很大,那么已经慢的计算运行速度会慢一些.我们已经确定这是一个不寻常的用例,但如果有人后来发现实际上,他们确实希望在异常不稳定的条件下操作它,我可以实现绕过备忘录的方法.

Answer 2

这里流行的阶乘答案是一个玩具答案.是的,memoization对于重复调用该函数很有用,但这种关系是微不足道的 - 在"print factorial(N)for 0..M"的情况下,你只是重用最后一个值.

这里的许多其他示例都只是"缓存".这很有用,但它忽略了memoization这个词给我带来的令人敬畏的算法含义.

更有趣的是,递归函数的单个调用的不同分支遇到相同的子问题,但是以非平凡的模式实际索引到某个缓存实际上是有用的.

例如,考虑整数的n维数组,其绝对值总和为k.例如,对于n = 3,k = 5 [1,-4,0],[3,-1,1],[5,0,0],[0,5,0]将是一些示例.设V(n,k)是给定n,k的可能唯一数组的数量.它的定义是:

V(n,0)=1; V(0,k)=0; V(n,k) = V(n-1,k) + V(n,k-1) + V(n-1,k-1);

对于n = 3,k = 5,该函数给出102.

如果没有记忆,即使是相当适中的数字,这也很快就会变得很慢.如果将处理可视化为树,则每个节点调用V()扩展为三个子节点,你有186,268,135,991,213,676,920,832 V(n,0)= 1叶子计算V(32,32)...天真实现此功能在可用硬件上迅速变得无法计算.

但是树中的许多子分支都是彼此完全相同的,尽管不是像平凡函数那样容易被消除的一些微不足道的方式.通过memoization,我们可以合并所有这些重复的分支.事实上,使用memoization V(32,32)只执行V()1024(n*m)次,这是10 ^ 21倍的加速(随着n,k变大,显然会变大)或者更换对于相当少量的内存.:)我发现这种对算法复杂性的根本改变远比简单缓存更令人兴奋.它可以使棘手的问题变得容易.

因为python数字自然是bignums你可以在python中实现这个公式,使用字典和元组键只有9行的memoization.试一试,没有备忘录就试一试.

Answer 3

Memoization是存储子问题的答案的技术,因此程序不需要在以后重新解决相同的子问题.

使用动态规划解决问题通常是一项重要的技术.

想象一下,枚举从网格左上角到网格右下角的所有路径.很多路径彼此重叠.您可以记住为网格上的每个点计算的解决方案,从右下角,从右上角开始构建.这使计算时间从"荒谬"变为"易处理".

另一个用途是:列出数字0到100的阶乘.你不想计算100!使用100 * 99 * ... * 1.你已经计算出99!,所以重用答案,并简单地乘以100倍的答案99!.您可以在每个步骤(从1到100)中记住答案,以节省大量的计算量.

对于数据点,我的网格解决问题(问题来自编程挑战):

Memoized:

real  0m3.128s
user  0m1.120s
sys   0m0.064s

非记忆(我杀了,因为我厌倦了等待......所以这是不完整的)

real 24m6.513s
user 23m52.478s
sys   0m6.040s

Answer 4

Memoization在可以重用子问题的解决方案的问题上闪耀.简单来说,它是一种缓存形式.我们以阶乘函数为例.

3!它本身就是一个问题,但它也是n的子问题!其中n> 3,例如4! = 4 * 3! 计算阶乘的函数可以通过memoization执行得更好,因为它只会计算3!一次并将结果存储在哈希表中.每当遇到3时!再次,它将在表中查找值而不是重新计算它.

子问题解决方案可以重复使用的任何问题(越频繁越好)是使用memoization的候选者.

Answer 5

记忆交换空间的时间.

当应用于本质上是多递归的问题时,记忆可以将指数时间(或更差)转变为线性时间(或更好).成本通常是O(n)空间.

经典的例子是计算Fibonacci序列.教科书定义是递归关系:

F(n)= F(n-1)+ F(n-2)

天真地实现,它看起来像这样:

int fib(int n) {
  if (n == 0) {
    return 0;
  }
  else if (n == 1) {
    return 1;
  }
  else {
    return fib(n-1) + fib(n-2);
  }
}

您可以看到运行时随n呈指数增长,因为每个部分和都是多次计算的.

通过memoization实现,它看起来像这样(笨拙但功能齐全):

int fib(int n) {
  static bool initialized = false;
  static std::vector<int> memo;

  if (!initialized) {
    memo.push_back(0);
    memo.push_back(1);
    initialized = true;
  }

  if (memo.size() > n) {
    return memo[n];
  }
  else {
    const int val = fib(n-1) + fib(n-2);
    memo.push_back(val);
    return val;
  }
}

在我的笔记本电脑上定时这两个实现,对于n = 42,天真版本需要6.5秒.memoized版本需要0.005秒(所有系统时间 - 也就是说,它的I/O限制).对于n = 50,memoized版本仍然需要0.005秒,并且naive版本最终在5分7秒之后完成(更不用说它们都溢出了32位整数).