JavaScript学习笔记之函数记忆,让函数也有记忆功能

如果我们使用函数记忆呢?

嗯,区别是直接把数组当作键来用,不过要注意函数里的arguments是js解释器实现的一个特殊对象,并不是真正的数组,所以要转换一下……
ps: 原来的参数包括方法名称和上下文引用:fib.fib_memo =
Memoize(‘fib_memo’,
fib),但实际上currying生成的函数里可以用this直接引用上层对象,更复杂的例子可以参考John
Resig的makeClass,所以我改成直接传函数引用:fib.fib_memo =
Memoize(fib.fib_memo)
这样写看上去似乎很靠谱,由参数组成的数组不是唯一的么。但实际上,数组之所以能作为js对象的属性名称来使用,是因为它被当作字符串处理了,也就是说如果你给函数传的参数是这样:(1,2,3),
cache对象就会是这个样子:{ “1,2,3″: somedata
},如果你的参数里有对象,比如:(1,2,{i:”yy”}),实际的键值会是:”1,2,[object
Object]“,所以这跟把数组拼接成字符串的方法其实没有区别……
示例:

var fibonacci = function() {
var memo = [0, 1];
var fib = function (n) {
var result = memo[n];
if (typeof result !== ‘number’) {
result = fib(n – 1) + fib(n – 2);
memo[n] = result;
}
return result;
};
return fib;
}();

var count = 0;
var fibonacci = function(n){
  count++;
  return n < 2? n : fibonacci(n-1) + fibonacci(n-2);
};
for (var i = 0; i <= 10; i++){
  fibonacci(i)
}

console.log(count) // 453

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

比如说,我们想要一个递归函数来计算 Fibonacci 数列。一个 Fibonacci
数字是之前两个 Fibonacci 数字之和。最前面的两个数字是 0 和 1。

var count = 0;
var fibonacci = function(n) {
  count++;
  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

fibonacci = memorize(fibonacci)

for (var i = 0; i <= 10; i++) {
  fibonacci(i)
}

console.log(count) // 12

复制代码 代码如下:

复制代码 代码如下:

兴奋的同时不要忘记思考:为什么会是 12 次呢?

function Memoize(o, p) {
var f = o[p], mf, value;
var s = function(v) {return o[p]=v||mf};
((mf = function() {
(s(function(){return value})).reset = mf.reset;
return value = f.apply(this,arguments); //此处修改过,允许接受参数
}).reset = s)();
}

var a = [1,2,{yy:’0′}];
var b = [1,2,{xx:’1′}];
var obj = {};
obj[a] = “111”;
obj[b] = “222”;
for( var i in obj )
alert( i + ” = ” + obj[i] ); //只会弹出”1,2,[object Object] =
222″,obj[a] = “111”被覆盖了

如果使用
JSON.stringify,参数是对象的问题也可以得到解决,因为存储的是对象序列化后的字符串。

复制代码 代码如下:

复制代码 代码如下:

本文讲解函数记忆与菲波那切数列的实现,分享给大家,具体如下

千万不要直接用==来比较arguments和args里的数组,那样比较的是内存引用,而不是参数的内容。
这种方法的速度很慢,equal方法其实影响不大,但是缓存的结果数量多了以后,每次都要遍历参数列表却是很没效率的(求80以上的fibonacci数列,在firefox3和safari3上都要40ms左右)
如果在实际应用中参数变动不多或者不接受参数的话,可以参考Oliver
Steel的这篇《One-Line JavaScript
Memoization》,用很短的函数式风格解决问题:

复制代码 代码如下:

注意

可以完全避免上述问题,没有使用hash的键值对索引,而是把函数的参数和结果分别缓存在两个列表里,每次都先遍历整个参数列表作比较,找出对应的键名/ID号之后再从结果列表里取数据。以下是比较数组的equal方法:

function Memoize(o, p) {
var f = o[p], mf, value;
var s = function(v) {return o[p]=v||mf};
((mf = function() {
(s(function(){return value})).reset = mf.reset;
return value = f.apply(this,arguments); //此处修改过,允许接受参数
}).reset = s)();
}

当执行 fib(6) 时,相当于 fib(5) + fib(4) 加上 fib(6) 本身这一次,共 15 +
9 + 1 = 25 次

复制代码 代码如下:

这个函数返回同样的结果,但是它只被调用了 29 次。我们调用了它 11
次,它自身调用了 18 次去取得之前储存的结果。
以上内容来自:

当执行 fib(7) 时,相当于 fib(6) + fib(5) 加上 fib(7) 本身这一次,共 25 +
15 + 1 = 41 次

realazy在blog上给出了一个JavaScript
Memoization的实现,Memoization就是函数返回值的缓存,比如一个函数参数与返回结果一一对应的hash列表,wiki上其实也有详细解释,我不细说了,只讨论一下具体实现的问题,realazy文中的代码有一些问题,比如直接用参数拼接成的字符串作为查询缓存结果的key,如果参数里包括对象或数组的话,就很难保证唯一的key,还有1楼评论里提到的:[221,3]和[22,13]这样的参数也无法区分。
那么来改写一下,首先还是用hash表来存放缓存数据:

function equal( first, second ){
if( !first || !second || first.constructor != second.constructor )
return false;
if( first.length && typeof first != “string” )
for(var i=0, l = ( first.length > second.length ) ? first.length :
second.length; i<l; i++){
if( !equal( first[i], second[i] ) ) return false;
}
else if( typeof first == ‘object’ )
for(var n in first){
if( !equal( first[n], second[n] ) ) return false;
}
else
return ( first === second );
return true;
}

需要注意的是,函数记忆只是一种编程技巧,本质上是牺牲算法的空间复杂度以换取更优的时间复杂度,在客户端
JavaScript
中代码的执行时间复杂度往往成为瓶颈,因此在大多数场景下,这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。

var fibonacci = function() {
var memo = [0, 1];
var fib = function (n) {
var result = memo[n];
if (typeof result !== ‘number’) {
result = fib(n – 1) + fib(n – 2);
memo[n] = result;
}
return result;
};
return fib;
}();

Fibonacci
数列。一个 Fibonacci 数字是之前两个 Fibonacci
数字之和。最前面的两个数字是 0 和 1。 复制代…

多说一句

function equal( first, second ){
if( !first || !second || first.constructor != second.constructor )
return false;
if( first.length && typeof first != “string” )
for(var i=0, l = ( first.length > second.length ) ? first.length :
second.length; i<l; i++){
if( !equal( first[i], second[i] ) ) return false;
}
else if( typeof first == ‘object’ )
for(var n in first){
if( !equal( first[n], second[n] ) ) return false;
}
else
return ( first === second );
return true;
}

realazy在blog上给出了一个JavaScript
Memoization的实现,Memoization就是函数返回值的缓存,比如一个函数参数与返回结果一一对应的hash列表,wiki上其实也有详细解释,我不细说了,只讨论一下具体实现的问题,realazy文中的代码有一些问题,比如直接用参数拼接成的字符串作为查询缓存结果的key,如果参数里包括对象或数组的话,就很难保证唯一的key,还有1楼评论里提到的:[221,3]和[22,13]这样的参数也无法区分。
那么来改写一下,首先还是用hash表来存放缓存数据:

// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
  var cache = {};
  return function(){
    var key = arguments.length + Array.prototype.join.call(arguments, ",");
    if (key in cache) {
      return cache[key]
    }
    else return cache[key] = f.apply(this, arguments)
  }
}

复制代码 代码如下:

function Memoize(fn){
var cache = {};
return function(){
var key = [];
for( var i=0, l = arguments.length; i < l; i++ )
key.push(arguments[i]);
if( !(key in cache) )
cache[key] = fn.apply(this, arguments);
return cache[key];
};
}

我们会发现最后的 count 数为 453,也就是说 fibonacci 函数被调用了 453
次!也许你会想,我只是循环到了
10,为什么就被调用了这么多次,所以我们来具体分析下:

复制代码 代码如下:

示例:

当执行 fib(8) 时,相当于 fib(7) + fib(6) 加上 fib(8) 本身这一次,共 41 +
25 + 1 = 67 次

function Memoize(fn){
var cache = {}, args = [];
return function(){
for( var i=0, key = args.length; i < key; i++ ) {
if( equal( args[i], arguments ) )
return cache[i];
}
args[key] = arguments;
cache[key] = fn.apply(this, arguments);
return cache[key];
};
}

for (var i = 0; i <= 10; i += 1) {
document.writeln(‘// ‘ + i + ‘: ‘ + fibonacci(i));
}

// 第二版 (来自 underscore 的实现)
var memorize = function(func, hasher) {
  var memoize = function(key) {
    var cache = memoize.cache;
    var address = '' + (hasher ? hasher.apply(this, arguments) : key);
    if (!cache[address]) {
      cache[address] = func.apply(this, arguments);
    }
    return cache[address];
  };
  memoize.cache = {};
  return memoize;
};

这个函数返回同样的结果,但是它只被调用了 29 次。我们调用了它 11
次,它自身调用了 18 次去取得之前储存的结果。
以上内容来自:

var fib = {
temp: function(n){
for(var i=0;i<10000;i++)
n=n+2;
return n;
}
}
Memoize(fib,”temp”); //让fib.temp缓存返回值
fib.temp(16); //执行结果:20006,被缓存
fib.temp(20); //执行结果:20006
fib.temp(10); //执行结果:20006
fib.temp.reset(); //重置缓存
fib.temp(10); //执行结果:20010

也许你会觉得在日常开发中又用不到
fibonacci,这个例子感觉实用价值不高呐,其实,这个例子是用来表明一种使用的场景,也就是如果需要大量重复的计算,或者大量计算又依赖于之前的结果,便可以考虑使用函数记忆。而这种场景,当你遇到的时候,你就会知道的。

var a = [1,2,{yy:’0′}];
var b = [1,2,{xx:’1′}];
var obj = {};
obj[a] = “111”;
obj[b] = “222”;
for( var i in obj )
alert( i + ” = ” + obj[i] ); //只会弹出”1,2,[object Object] =
222″,obj[a] = “111”被覆盖了

复制代码 代码如下:

function add(a, b) {
  return a + b;
}

// 假设 memorize 可以实现函数记忆
var memoizedAdd = memorize(add);

memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数,第二次调用时,从缓存中取出数据,而非重新计算一次

var fib = {
temp: function(n){
for(var i=0;i<10000;i++)
n=n+2;
return n;
}
}
Memoize(fib,”temp”); //让fib.temp缓存返回值
fib.temp(16); //执行结果:20006,被缓存
fib.temp(20); //执行结果:20006
fib.temp(10); //执行结果:20006
fib.temp.reset(); //重置缓存
fib.temp(10); //执行结果:20010

可以完全避免上述问题,没有使用hash的键值对索引,而是把函数的参数和结果分别缓存在两个列表里,每次都先遍历整个参数列表作比较,找出对应的键名/ID号之后再从结果列表里取数据。以下是比较数组的equal方法:

当执行 fib(3) 时,相当于 fib(2) + fib(1) 加上 fib(3) 本身这一次,共 3 +
1 + 1 = 5 次

// 0: 0
// 1: 1
// 2: 1
// 3: 2
// 4: 3
// 5: 5
// 6: 8
// 7: 13
// 8: 21
// 9: 34
// 10: 55

直接用参数作为键名的方法不靠谱了…………换一种方法试试:

函数记忆是指将上次的计算结果缓存起来,当下次调用时,如果遇到相同的参数,就直接返回缓存中的数据。

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

复制代码 代码如下:

当执行 fib(9) 时,相当于 fib(8) + fib(7) 加上 fib(9) 本身这一次,共 67 +
41 + 1 = 109 次

复制代码 代码如下:

嗯,区别是直接把数组当作键来用,不过要注意函数里的arguments是js解释器实现的一个特殊对象,并不是真正的数组,所以要转换一下……
ps: 原来的参数包括方法名称和上下文引用:fib.fib_memo =
Memoize(‘fib_memo’,
fib),但实际上currying生成的函数里可以用this直接引用上层对象,更复杂的例子可以参考John
Resig的makeClass,所以我改成直接传函数引用:fib.fib_memo =
Memoize(fib.fib_memo)
这样写看上去似乎很靠谱,由参数组成的数组不是唯一的么。但实际上,数组之所以能作为js对象的属性名称来使用,是因为它被当作字符串处理了,也就是说如果你给函数传的参数是这样:(1,2,3),
cache对象就会是这个样子:{ “1,2,3″: somedata
},如果你的参数里有对象,比如:(1,2,{i:”yy”}),实际的键值会是:”1,2,[object
Object]“,所以这跟把数组拼接成字符串的方法其实没有区别……
示例:

var add = function(a, b, c) {
 return a + b + c
}

var memoizedAdd = memorize(add)

console.time('use memorize')
for(var i = 0; i < 100000; i++) {
  memoizedAdd(1, 2, 3)
}
console.timeEnd('use memorize')

console.time('not use memorize')
for(var i = 0; i < 100000; i++) {
  add(1, 2, 3)
}
console.timeEnd('not use memorize')

复制代码 代码如下:

复制代码 代码如下:

从这个实现可以看出,underscore 默认使用 function 的第一个参数作为
key,所以如果直接使用

示例:

function Memoize(fn){
var cache = {}, args = [];
return function(){
for( var i=0, key = args.length; i < key; i++ ) {
if( equal( args[i], arguments ) )
return cache[i];
}
args[key] = arguments;
cache[key] = fn.apply(this, arguments);
return cache[key];
};
}

我们以斐波那契数列为例:

直接用参数作为键名的方法不靠谱了…………换一种方法试试:

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

我们会发现最后的总次数为 12 次,因为使用了函数记忆,调用次数从 453
次降低为了 12 次!

复制代码 代码如下:

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

在 Chrome 中,使用 memorize 大约耗时
60ms,如果我们不使用函数记忆,大约耗时 1.3 ms 左右。

var fibonacci = function (n) {
return n < 2 ? n : fibonacci(n – 1) + fibonacci(n – 2);
};

千万不要直接用==来比较arguments和args里的数组,那样比较的是内存引用,而不是参数的内容。
这种方法的速度很慢,equal方法其实影响不大,但是缓存的结果数量多了以后,每次都要遍历参数列表却是很没效率的(求80以上的fibonacci数列,在firefox3和safari3上都要40ms左右)
如果在实际应用中参数变动不多或者不接受参数的话,可以参考Oliver
Steel的这篇《One-Line JavaScript
Memoization》,用很短的函数式风格解决问题:

您可能感兴趣的文章:

  • JavaScript Memoization
    让函数也有记忆功能
  • javascript
    用记忆函数快速计算递归函数

function Memoize(fn){
var cache = {};
return function(){
var key = [];
for( var i=0, l = arguments.length; i < l; i++ )
key.push(arguments[i]);
if( !(key in cache) )
cache[key] = fn.apply(this, arguments);
return cache[key];
};
}

// 0: 0
// 1: 1
// 2: 1
// 3: 2
// 4: 3
// 5: 5
// 6: 8
// 7: 13
// 8: 21
// 9: 34
// 10: 55

实现这样一个 memorize
函数很简单,原理上只用把参数和对应的结果数据存到一个对象中,调用时,判断参数对应的数据是否存在,存在就返回对应的结果数据。

您可能感兴趣的文章:

  • javascript
    用记忆函数快速计算递归函数
  • JavaScript学习笔记之函数记忆

复制代码 代码如下:

肯定是有问题的,如果要支持多参数,我们就需要传入 hasher
函数,自定义存储的 key 值。所以我们考虑使用 JSON.stringify:

比如说,我们想要一个递归函数来计算 Fibonacci 数列。一个 Fibonacci
数字是之前两个 Fibonacci 数字之和。最前面的两个数字是 0 和 1。

var fibonacci = function (n) {
return n < 2 ? n : fibonacci(n – 1) + fibonacci(n – 2);
};

当执行 fib(1) 时,调用 1 次

for (var i = 0; i <= 10; i += 1) {
document.writeln(‘// ‘ + i + ‘: ‘ + fibonacci(i));
}

复制代码 代码如下:

所以我们还需要认真看下我们的写法,在我们的写法中,其实我们用生成的
fibonacci 函数覆盖了原本了 fibonacci 函数,当我们执行 fibonacci(0)
时,执行一次函数,cache 为 {0: 0},但是当我们执行 fibonacci(2)
的时候,执行 fibonacci(1) + fibonacci(0),因为 fibonacci(0) 的值为
0,!cache[address]的结果为 true,又会执行一次 fibonacci
函数。原来,多出来的那一次是在这里!

从 0 到 10 的结果各储存一遍,应该是 11
次呐?咦,那多出来的一次是从哪里来的?

var add = function(a, b, c) {
 return a + b + c
}

var memoizedAdd = memorize(add)

memoizedAdd(1, 2, 3) // 6
memoizedAdd(1, 2, 4) // 6

当执行 fib(5) 时,相当于 fib(4) + fib(3) 加上 fib(5) 本身这一次,共 9 +
5 + 1 = 15 次

当执行 fib(10) 时,相当于 fib(9) + fib(8) 加上 fib(10) 本身这一次,共
109 + 67 + 1 = 177 次
所以执行的总次数为:177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 =
453 次!

第一版

所以,函数记忆也并不是万能的,你看这个简单的场景,其实并不适合用函数记忆。

什么,我们使用了看似高大上的函数记忆,结果却更加耗时,这个例子近乎有 60
倍呢!

var memoizedAdd = memorize(add, function(){
  var args = Array.prototype.slice.call(arguments)
  return JSON.stringify(args)
})

console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 4)) // 7

两者都返回了 1,显然是有问题的,所以我们看看 underscore 的 memoize
函数是如何实现的:

第二版

我们来测试一下:

当执行 fib(4) 时,相当于 fib(3) + fib(2) 加上 fib(4) 本身这一次,共 5 +
3 + 1 = 9 次

举个例子:

我们来写一版:

因为第一版使用了 join
方法,我们很容易想到当参数是对象的时候,就会自动调用 toString 方法转换成
[Object object],再拼接字符串作为 key 值。我们写个 demo
验证一下这个问题:

当执行 fib(0) 时,调用 1 次

适用场景

定义

原理

当执行 fib(2) 时,相当于 fib(1) + fib(0) 加上 fib(2) 本身这一次,共 1 +
1 + 1 = 3 次

var propValue = function(obj){
  return obj.value
}

var memoizedAdd = memorize(propValue)

console.log(memoizedAdd({value: 1})) // 1
console.log(memoizedAdd({value: 2})) // 1