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];
}
}();
分析: 该方法的思路是, 将计算过的结果缓存起来, 这样就可以减少很多重复计算, 从而提高执行效率.
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， 递归
， int
优化
如何避免递归、递归调用避免栈溢出、递归避免死循环、memoization、memoization技术，以便于您获取更多的相关知识。