C/C 使用 memoization 优化递归 避免重复计算

C/C 使用 memoization 优化算法

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

<pre class="brush:cpp;toolbar:false">#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)); }</pre>

输出：

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

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

<pre class="brush:cpp;toolbar:false">#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 结果 - 计算次数 %d\n", i, fib(i), count);         count = 0;     } }</pre>

结果：

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 来优化一下：

<pre class="brush:cpp;toolbar:false">#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 结果 - 计算次数 %d\n", i, fib(i, mem), count);           count = 0; // 计算次数清零         free(mem); // 释放用来缓存的内存     } }</pre>

优化之后，可以发现时间复杂度很轻松的变成 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 获得的效果就越明显，不过实际应用中要考虑到其所消耗的内存是否值得，也就是看一个性价比吧。

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

<pre class="brush:cpp;toolbar:false">#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);     } }</pre>

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

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

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

<pre class="brush:cpp;toolbar:false">int fib ( n )  {      if ( n == 0 || n == 1 ) {          return 1;      }      else {          return fib( n - 2 )   fib ( n - 1 );      }  }</pre>

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

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

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

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

<pre class="brush:cpp;toolbar:false">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  }</pre>

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

下面是我用C 写的：

<pre class="brush:cpp;toolbar:false">#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); }</pre>

输出的结果如下：




JS用memoization优化递归调用

一. 前言

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


二. 应用

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

<pre class="brush:js;toolbar:false"> // 常规代码  function fib(n)  {       if (n < 2)  { return n; }       return fib(n-1)   fib(n-2);  }</pre>

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

<pre class="brush:js;toolbar:false">// 优化后的代码 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];      } }();</pre>

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

您可能感兴趣的文章：
C/C 使用 memoization 优化递归 避免重复计算
一文了解Python中的递归
PHP一些实用小技巧
关于python递归函数用法介绍
PHP递归算法实例解析
高性能mysql(第二版)之查询性能优化
提高php运行效率的50个实用技巧
php中优化建义与优化代码
前端性能优化（JavaScript补充篇）
php优化方法