首页 > 代码库 > 记忆函数

记忆函数

很久没写随笔了呀,因为看到记忆函数,确实搞懵逼了啊,实在是太菜了。

书本上给出的例子:

var fibonacci = function (n) {             return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);             };             for (var i = 0; i <= 10; i += 1) {               document.writeln(‘// ‘ + i + ‘: ‘ + fibonacci(i));             }             // 0: 0             // 1: 1             // 2: 1             // 3: 2             // 4: 3             // 5: 5             // 6: 8             // 7: 13             // 8: 21             // 9: 34             // 10: 55 

这样是可以工作的,但是它做了很多无谓的工作。 Fibonacci 函数被调用了 453 次。我们调用了 11 次,而它自身调用了 442 次去计算可能已经被刚计算过的值。如果我们让该函数具备记忆功能,就可以显著地减少它的运算量。 

我们在一个名为 memo 的数组里保存我们的储存结果,储存结果可以隐藏在闭包中。当我们的函数被调用时,这个函数首先看是否已经知道计算的结果,如果已经知道,就立即返回这个储存结果。 

var fibonacci = function() {        var memo = [0, 1];        var fib = function(n) { //10 9            //存储结果隐藏在闭包中,当函数被调用时,这个函数首先检查结果是否存在,如果存在立即返回这个结果            var result = memo[n]; //            if (typeof result !== ‘number‘) {                                result = fib(n - 1) + fib(n - 2);                                 memo[n] = result;             }            return result;        };        return fib;    }();    //这个函数返回同样的结果,但是它只被调用了 29 次。我们调用了它 11 次,它自身调用了 18 次去取得之前储存的结果。        for (var i = 10; i > 0; i--) {         document.writeln(‘// ‘ + i + ‘: ‘ + fibonacci(i));     }
  //for (var i = 0; i <= 10; i++) {     //    document.writeln(‘// ‘ + i + ‘: ‘ + fibonacci(i));     //} 

其实就是维护一个数组,让这个数组在这个函数中始终存在;然后  1 1  2  3  5  8  的扩展下去

直接看 i = 2

这个时候 resvar result = memo[n];
if (typeof result !== ‘number‘) {
result = fib(n - 1) + fib(n - 2);
memo[n] = result;
}

memo[2]  不存在

result = fib(1)+fib(0);

然后得到 memo[2] = 2

下一步  , i= 3 /////    result = fib (2) + fib(1)

直接运行 i = 10 也是可以的  ,运行i=10,  他就会调用 fib(9)+ fib(8)......fib(2) d调用 fib(1) + fib(0);

假如直接调用 fib (4),之后会  调用  fib3   fib2,首先运行 fib3    fib3会调用fib2  fib1,fib3  中的 fib2  会继续调用  fib1  fib0,fib2 得到结果,并且保存到memo = 0 1 1,然后返回 ,继续调用 fib3 = fib2 +fib1 中的 fib1。相当于一个断点  运行到 fib3 = fib2 + fib1  ,, 深入了函数fib2进行计算,  fib2计算结束后, 是不是该计算fib1了?fib3 也得到值,更新memo=[0,1,1,2]。之前 fib4 = fib3 + fib2 ,,  刚才  详细计算了FIb3的值,接下去计算fib2的值,,fib2可以直接从memo中获取

但是假如你直接调用 FIB10,那你之后再调用 FIB 1 - 9 ,,,都只需要调用1次就用了,因为之前已经存储在全局变量了。总体效果是一样的。

fibonacci(3)调用子函数的次数:

FIB3  = FIB2  + FIB1 3次 然后  FIB2会再调用  FIB1   和 FIB0  又两次。总共五次

对于这种多个函数值相加,, 你要有种 断点 的感觉,,
比如var result = FIB2 + FIB1 ,,
由于FIB2是一个函数,  var result = FIB2 + FIB1 会在FIB2 上断开,,
先计算FIB2的值,然后再回来继续 做加法

技术分享

不是很理解的函数执行过程,,多在函数的各个地方写上输出。。。。。。。未完待续。。。。。。。。。。。。

记忆函数