Caching data, but only when accessed
This blog post will be about memoization and is inspired by this blog post by Darren Torpey about _.once. It reminded me that in Lua, I have often used memoized functions while I was participating in the Euler project. During those maths challenges, it was quite convenient to have a function remember its answer the second time it is asked the same question. This is memoization in a nutshell.
What's memoization outside a nutshell?
When citing Wikipedia, I find out that my nutshell explanation is basically the same.
In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Useful implementations
The definition of memoization basically describes the useful scenarios in which you would implement the technique. When you have an expensive function, which will always result in the same value given the same arguments, it is efficient to cache the result and return the cached value the next time it is called. This way, valuable time is not wasted on recalculating values. #perfmatters
Basic Memoization in JavaScript
Below you will find some example code implementing basic memoization in JS. This method of memoization allows now additional features and only makes sure each unique call (based on input values) caches its result. This implementation creates a 32-bits hash of a JSON-serialized form of the argument-list.
;(function(root) {
'use strict';
// A 32-bit checksum of a string.
String.prototype.checksum = function() {
var checksum = 0, i, chr, len;
if (this.length == 0) {
return checksum;
}
for (i = 0, len = this.length; i < len; i++) {
checksum = ((((checksum << 5) - checksum) + this.charCodeAt(i)) | 0);
}
return checksum;
};
var memoize = function(f) {
if(typeof(f) !== "function" || !(f instanceof Function)) {
throw new TypeError("Provided argument is not a function.");
}
/*
The cache object for the memoized function. Each function
will hold its own cache object. The object will be indexed
by 32-bit checksums of argument-lists.
*/
var cache = {};
return function MemoizedFunction() {
// Create a checksum of all the arguments, if any argument is available.
var checksum = 0;
if(arguments.length > 0) {
// if you don't expect complex argument structure, this will suffice
// checksum = Array.prototype.join.call(arguments, ",").checksum();
// serialize the arguments object to a JSON string and create a 32-bits checksum.
checksum = JSON.stringify(arguments).checksum();
}
// if the checksum is unknown in the cache, call the function and cache it.
if(typeof(cache[checksum]) === 'undefined') {
cache[checksum] = f.apply(f, arguments);
}
// return the cached value.
return cache[checksum];
};
};
root.memoize = memoize;
}('mem' in window ? window.mem : window.mem = {})); // export to mem, create mem if it doesn't exist.
Example implementation
function recursiveFib(n) {
if(n < 2) {
return 1;
} else if (n == 2) {
return 2;
} else {
return recursiveFib(n - 1) + recursiveFib(n - 2);
}
}
var memoizedFib = mem.memoize(recursiveFib);
var result1 = memoizedFib(20); // calculated and returned
var result2 = memoizedFib(20); // returned from the cache
var result3 = memoizedFib(21); // calculated and returned, unknown arguments
var result4 = memoizedFib(21); // known arguments, returned from the cache.
As you can see, when you are working with expensive calculations or algorithms, caching the output might be useful. This will consume memory, as the results have to be stored, but there will be a speed increase if the same input is provided to a function often.
Still use memoize when a function requires no input?
In some cases, a function does not require any input to calculate or test something. The above implementation of memoize can be used to wrap up those functions as well, as a checksum will only be created when arguments are provided. However, considering these functions should only be executed only once, a new function could be created. Hence Underscore.js' _.once.
If you only need memoization and not a whole library such as underscore (which actually is quite small!), you could add the memoize function from above and a new one to your code.
;(function(root) {
'use strict';
/**
Once is a function which allows a function to be called only once, regardless
of the input.
*/
var once = function once(f) {
if(typeof(f) !== "function" || !(f instanceof Function)) {
throw new TypeError("Provided argument is not a function.");
}
var cached;
return function OnceFunction() {
if(typeof(cached) === 'undefined') {
cached = f.apply(f, arguments);
}
return cached;
};
};
root.once = once;
}('mem' in window ? window.mem : window.mem = {})); // export to mem, create mem if it doesn't exist.
An example implementation of once could be feature detection. Feature detection methods usually result in a boolean value, however the results often do not change in the same session. Here's an example implementation to test for html5 canvas support:
var isCanvasSupported = mem.once(function() {
var elem = document.createElement('canvas');
return !!(elem.getContext && elem.getContext('2d'));
});
var s;
// the function is called only once, even though a different value of **i** is provided each time.
for(var i = 0; i < 1000; i++) {
s = isCanvasSupported(i);
}
That's it
I wanted to keep this blog a little bit short, I think I failed myself again. I hope you'll find it useful for some reason, I also wrote an other blog about memoization with cache timeout. To wrap it up, here's an example with all the code and test code:
Check out this pen.