JavaScript Memoization allows functions to have memory functions_javascript skills

Let's say we want a recursive function to compute the Fibonacci sequence. A Fibonacci number is the sum of the two previous Fibonacci numbers. The first two numbers are 0 and 1.

Copy code The code is as follows:

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

This works, but it does a lot of unnecessary work. The Fibonacci function was called 453 times. We called it 11 times, and it called itself 442 times to calculate a value that might have just been calculated. If we make this function memory-capable, we can significantly reduce its computational complexity.

We save our stored results in an array called memo. The stored results can be hidden in closures. When our function is called, the function first checks to see if the calculated result is already known. If so, it immediately returns the stored result.

Copy code The code is as follows:

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;
}();

This function returns the same result, but it is only called 29 times. We called it 11 times, and it called itself 18 times to get previously stored results.
The above content comes from: http://demon.tw/programming/javascript-memoization.html

realazy gave an implementation of JavaScript Memoization on the blog. Memoization is the cache of function return values, such as A hash list that corresponds one-to-one between function parameters and return results. There is actually a detailed explanation on the wiki. I will not go into details. I will only discuss the specific implementation issues. The code in the realazy article has some problems, such as the characters that are directly spliced ​​with parameters. String is used as the key for query cache results. If the parameters include objects or arrays, it is difficult to ensure a unique key. There are also parameters such as [221,3] and [22,13] mentioned in the comment on the first floor. Indistinguishable.
Let’s rewrite it. First, use a hash table to store the cached data:

Copy the code The code is as follows:

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];
};
}

Well, the difference is to use the array directly as a key, but pay attention to the function The arguments in are a special object implemented by the js interpreter, not a real array, so you need to convert it...
ps: The original parameters include method names and context references: fib.fib_memo = Memoize('fib_memo', fib), but in fact you can use this to directly refer to the upper-level object in the function generated by currying. For more complex examples, please refer to John Resig's makeClass, so I changed to directly passing the function reference: fib.fib_memo = Memoize(fib.fib_memo)
Writing like this seems very reliable. Isn’t the array composed of parameters unique? But in fact, the reason why an array can be used as an attribute name of a js object is because it is treated as a string. That is to say, if the parameters you pass to the function are like this: (1,2,3), cache The object will look like this: { “1,2,3″: somedata }. If there is an object in your parameters, such as: (1,2,{i:”yy”}), the actual key value will be: "1,2,[object Object]", so this is actually no different from the method of splicing arrays into strings...
Example:

Copy code The code is as follows:

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] ); //Only "1,2,[object Object] = 222" will pop up, obj[a] = "111" is overwritten

The method of directly using parameters as key names is unreliable... Try another method:

Copy code The code is as follows:

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];
};
}

can be completely To avoid the above problems, instead of using hash key-value pair index, the parameters and results of the function are cached in two lists respectively. Each time, the entire parameter list is first traversed for comparison, and the corresponding key name/ID number is found. Then get the data from the results list. The following is the equal method for comparing arrays:

Copy code The code is as follows:

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; iif( !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;
}

thousand Never use == directly to compare the arrays in arguments and args, as that will compare the memory references, not the contents of the parameters.
This method is very slow, and the equal method actually has little impact. However, when the number of cached results increases, it is very inefficient to traverse the parameter list every time (finding the fibonacci sequence above 80, in firefox3 It takes about 40ms compared to Safari3)
If the parameters do not change much or do not accept parameters in actual applications, you can refer to this article "One-Line JavaScript Memoization" by Oliver Steel to solve the problem in a short functional style. :

Copy code The code is as follows:

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); //This has been modified to allow parameters to be accepted
}).reset = s)();
}

Example:

Copy code The code is as follows:

var fib = {
temp: function(n){
for(var i=0;i<10000;i )
n=n 2;
return n;
}
}
Memoize(fib,"temp"); //Let fib.temp cache the return value
fib.temp(16); //Execution result: 20006, was Cache
fib.temp(20); //Execution result: 20006
fib.temp(10); //Execution result: 20006
fib.temp.reset(); //Reset cache
fib.temp(10); //Execution result: 20010