Memoization is a programming technique which attempts to increase a function’s performance by caching its previously computed results. Because JavaScript objects behave like associative arrays, they are ideal candidates to act as caches. Each time a memoized function is called, its parameters are used to index the cache. If the data is present, then it can be returned, without executing the entire function. However, if the data is not cached, then the function is executed, and the result is added to the cache.
- Memoization can potentially increase performance by caching the results of previous function calls.
- Memoized functions store a cache which is indexed by their input arguments. If the arguments exist in the cache, then the - cached value is returned. Otherwise, the function is executed and the newly computed value is added to the cache.
- Object arguments should be stringified before using as an index.
- Memoization can be automatically applied to referentially transparent functions.
- Memoization may not be ideal for infrequently called or fast executing functions.
function memoize(func) {
var memo = {};
var slice = Array.prototype.slice;
return function() {
var args = slice.call(arguments);
if (args in memo)
return memo[args];
else
return (memo[args] = func.apply(this, args));
}
}The classic example case is fibonacci, where each result can be broken down into a series of smaller results.
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}Running fibonacci(10) returns quite quickly but running fibonacci(40) takes considerably longer. The fibonacci function can be memoized using:
f = memoize(fibonacci)You can then run the function like this:
> f(10)
55
> f(30)
832040
> f(40)
102334155
> f(40)
102334155
> f(38)
39088169
> f(50)
12586269025
> f(50)
12586269025In this case when we call f(50) the first time it takes a considerable time to compute the result but when we call it a second time it responds instantly.