Certain operations are computationally expensive, but because their results might change over time or due to outside influences, they don't lend themselves to typical memoization — take for example getElementsByClassName. Here's a JavaScript timed memoization decorator / higher-order-function I made to help with these cases, which accepts an optional expiration argument in milliseconds.
function memoize (functor, expiration) {
var memo = {};
return function () {
var key = Array.prototype.join.call(arguments, "§");
if (key in memo)
return memo[key];
if (expiration)
setTimeout(function () {delete memo[key];}, expiration);
return memo[key] = functor.apply(this, arguments);
};
}
This approach allows you to turn any function into a memoizing function. Note that return values are memoized for each set of arguments. However, due to technical constraints it's only reliable when the arguments are arrays or scalar values, but you could easily use e.g. a toJSON method rather than join to serialize objects as part of the cache key (at some additional overhead cost).
You can use the above code like this:
// Make a function which memoizes for 1000 milliseconds at a time var fn = memoize(function () { Array(500000).join("."); // slow return true; }, 1000);
…Or leave out the expiration argument to permanently memoize.
Here are a couple more posts on JavaScript memoization:
- One-Line JavaScript Memoization by Oliver Steele
- Memoization in JavaScript by Keith Gaughan
We’ve got one of these memoize decorators in Chiron: https://cixar.com/tracs/javascript/browser/trunk/src/cache.js#L90
It depends on base.js (using Dict, which uses eq and hash) and thus provides a stronger guarantee of idempotence, even with complex objects for parameters.
@Kris, Chiron modules are generally quite robust and awesome — I should have expected that you would’ve included a memoize decorator somewhere. But even though I hadn’t seen that one, I had seen the one by Keith Gaughan linked to above, so I tried to focus this post on the timed expiration aspect of it which I haven’t yet seen in other JavaScript libraries. Granted, that feature might only be useful in edge cases, but where it is I can envision significant performance savings that otherwise might be passed up.
@Steve – I like your implementation although I’m struggling though to see how this could improve getElementsByClassName() functions except in limited circumstances. Care to provide an example?
@Kris – I’d never heard of Chiron until recently. It looks very impressive. What do you plan to do with it? Is it being used anywhere?
Dean, I agree that it could only improve
getElementsByClassNamefunctions in limited circumstances. The case I was specifically thinking of when I wrote that was code that invokesgetElementsByClassNameand runsonmouseoverfor a DOM node, thereby potentially being triggered thousands of times over a short amount of time. Memoization (timed or otherwise) would probably never be a good idea as a general purpose alteration for such functions, but depending on the nature of one’s application they might decide the benefits outweigh the risks. That said, the real reason I used that example was that I couldn’t think of a better one. 😉 I didn’t originally write this implementation for the ability to garbage collect cached values after a while, but that seemed like a potentially interesting extension that was easy to add.@Steve – Fair enough. I thought you had some clever implementation of getElementsByClassName() in mind.
It’s still a cool function though. I might steal it and include it in base2. 😉
Dean, you’re of course very welcome to do so.
@Dean sorry for the delay. Steve just let me know I missed your message. I’m using Chiron for a variety of projects including a browser-based MUD-like game, a remote Python shell, a log aggregation service, and some other data-visualization stuff. I’ve been promoting it as much as I can (the http://modulesjs.com website, presented at Barcamp LA a couple weeks ago http://cixar.com/barcamp for slides); it’s designed to be a platform for a “batteries included” JavaScript library. If it looks awesome, it’s partially because I read your base2 code to help inform its design, although I would still like to integrate more of your code.
In recent news, I’m using memoize, and my Dict-like Cookie type in tandem to do cookie-based caching on a function.
include(‘cookie.js’);
include(‘cache.js’);
this.fib = memoize(cookie, fib);
great function . took it to my website