C/C++ 使用 memoization 优化算法

以常见的斐波那契数列计算为例：

#include <stdio.h>
 
#define COUNT_TIMES 10
 
int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        return fib(n - 2) + fib(n - 1);
    }
}
 
int main()
{
    int i;
    for (i = 0; i < COUNT_TIMES; i++)
        printf("fib %d\n", fib(i));
}

输出：

fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
fib 21
fib 34
fib 55

实际上，我们来看看其中的计算次数

#include <stdio.h>
 
#define COUNT_TIMES 10
 
int count;
 
int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        count++;
        return fib(n - 2) + fib(n - 1);
    }
}
 
int main()
{
    int i, *mem;
 
    for (i = 0; i < COUNT_TIMES; i++)
    {
        printf("n %d 结果 %2d 计算次数 %d\n", i, fib(i), count);
        count = 0;
    }
}

结果：

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 4
n 5 结果  8 计算次数 7
n 6 结果 13 计算次数 12
n 7 结果 21 计算次数 20
n 8 结果 34 计算次数 33
n 9 结果 55 计算次数 54

我们发现实际上计算的次数跟其结果相当，计算 n 的斐波那契数列其计算量就是 fib(n) - 1 次了。想想也是醉了。

那么让我们使用 memoization 来优化一下：

#include <stdio.h>
#include <stdlib.h>
 
#define COUNT_TIMES 10
 
int count;
 
int fib(int n, int *mem)
{
    // 如果没有缓存结果则进行计算，并把结果加入到缓存中
    if (mem[n] == -1)
    {
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
        // 统计计算次数
        count++;
    }
    // 返回缓存结果
    return mem[n];
}
 
int main()
{
    int i, j, *mem;
    for (i = 0; i < COUNT_TIMES; i++)
    {
        // 申请一块内存来缓存结果
        mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
        // 初始化其中的结果
        mem[0] = mem[1] = 1;
        for (j = 2; j < COUNT_TIMES; j++)
            mem[j] = -1;
 
        // 调用计算
        printf("n %d 结果 %2d 计算次数 %d\n", i, fib(i, mem), count);
 
        count = 0; // 计算次数清零
        free(mem); // 释放用来缓存的内存
    }
}

优化之后，可以发现时间复杂度很轻松的变成 O(n) 了

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 3
n 5 结果  8 计算次数 4
n 6 结果 13 计算次数 5
n 7 结果 21 计算次数 6
n 8 结果 34 计算次数 7
n 9 结果 55 计算次数 8

优化之后，当 n = 15，速度大概是原版的1000倍，当 n = 27 速度大概是原来的 10000 倍了。应该说重复计算的计算量越大使用 memoization 获得的效果就越明显，不过实际应用中要考虑到其所消耗的内存是否值得，也就是看一个性价比吧。

最后去掉注释简单封装一下。

#include <stdio.h>
#include <stdlib.h>
 
#define COUNT_TIMES 10
 
int * init_mem() {
    int i, *mem;
    mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
    mem[0] = mem[1] = 1;
    for (i = 2; i < COUNT_TIMES; i++)
        mem[i] = -1;
    return mem;
}
 
int fib(int n, int *mem)
{
    if (mem[n] == -1)
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
    return mem[n];
}
 
int main()
{
    int i, *mem;
 
    for (i = 0; i < COUNT_TIMES; i++)
    {
        mem = init_mem();
        printf("fib %d\n", fib(i, mem));
        free(mem);
    }
}

使用Memoization，以避免递归重复计算

考虑Fibonacci（斐波那契）问题;

Fibonacci问题是可以通过简单的递归方法来解决：

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

注：在这里，我们考虑Fibonacci 系列从1开始，因此，该系列看起来：1，1，2，3，5，8，...

注意：从递归树，我们计算fib（3）函数2次，fib（2）函数3次。这是相同函数的重复计算。如果n非常大，fib

这个简单的技术叫做Memoization，可以被用在递归，加强计算速度。

fibonacci 函数Memoization的代码，应该是下面的这个样子：

int calc_fib ( int n )
 { 
    int val[ n ] , i;
    for ( i = 0; i <=n; i++ ) { 
        val[ i ] = -1;      // Value of the first n + 1 terms of the fibonacci terms set to -1 
    } 
    val[ 0 ] = 1;   // Value of fib ( 0 ) is set to 1 
    val[ 1 ] = 1;    // Value of fib ( 1 ) is set to 1 
    return fib( n , val ); 
}
 int fib( int n , int* value ) 
{
     if ( value[ n ] != -1 ) { 
        return value[ n ];              // Using memoization 
    } 
    else { 
        value[ n ] = fib( n - 2 , value ) + fib ( n - 1 , value );          // Computing the fibonacci term
     }
     return value[ n ];                // Returning the value 
}

上面代码的红色部分，不知道为什么可以那么声明，在标准C和C++中数组都不可以那样声明吧，可能是使用编译器进行了扩展。

下面是我用C++写的：

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int fib(int n,int val[])
{
    if(val[n]!=-1)
        return val[n];
    else
    {
        val[n]=fib(n-1,val)+fib(n-2,val);
        return val[n];
    }
}
void cal_fib(int n)
{
    int *val=new int[n+1];
    for(int i=0;i<=n;i++)
        val[i]=-1;
    val[0]=0;
    val[1]=1;
    fib(n,val);
    copy(val,val+n+1,ostream_iterator<int>(cout," "));
    cout<<endl;
    delete[] val;
}
int main()
{
    for(int i=3;i<=15;i++)
        cal_fib(i);
}

输出的结果如下：




JS用memoization优化递归调用

一. 前言

memoization, 这个词见过几次, 脑海中对它的印象, 是用来优化递归调用的(我知道, 绝不仅于此), 即便如此, 我依然认为, 它不是一种方法, 而应该是一种思路或思想, 特在此记录一点现有的理解, 以后逐步增加...


二. 应用

网上一搜, 发现大都以计算裴波拉契数为例, 咱也不搞特殊化:
     

 // 常规代码
 function fib(n)  {
      if (n < 2)  { return n; }
      return fib(n-1) + fib(n-2);
 }

 
分析: 这段代码的执行效率非常低, 原因就在于, 需要反复调用函数自生, 且每次调用都有很多重复计算,  很明显, n越大, 调用次数越多.

// 优化后的代码
var mFib = function() {
     var cache = [1, 1]; // 裴波拉契数的前两个数为1, 1
     return function(m) {
         var len = cache.length, i = len;
         // 如果m大于cache的长度, 则说明m对应的裴波拉契数不存在, 需要计算
         if (m > len)  {
               // 当i等于m的时候, 小于i之前的裴波拉契数已经计算过了, 可以直接使用
               // 有的例子用的for循环, 但while循环更快
               while (i <= m)  {
                    // 裴波拉契数的特点, 后一个数等于前两个数之和
                    // 把计算结果缓存起来, 避免再次计算
                    cache[i] = cache[i - 2] + cache[i - 1]; 
                    i++;
               }
          }
          // 当裴波拉契数存在时, 直接使用
          return cache[m - 1];
     }
}();

分析: 该方法的思路是, 将计算过的结果缓存起来, 这样就可以减少很多重复计算, 从而提高执行效率.