addyosmani / memoize.js Goto Github PK

A faster JavaScript memoizer

JavaScript 97.30% CSS 2.70%

memoize.js's Introduction

Memoize.js

A faster JavaScript memoizer

Whilst not new by any means, memoization is a useful optimization technique for caching the results of function calls such that lengthy lookups or expensive recursive computations can be minimized where possible.

The basic idea is that if you can detect an operation has already been previously completed for a specific set of input values, the stored result can instead be returned instead of repeating the operation again.

Some of the problems memoization can help optimize include: recursive mathematics, algorithmic caching of canvas animation and more generally, any problems which can be expressed as a set of calls to the same function with a combination of argument values that repeat.

Usage

Imagine having a function you want to memoize, like running the Fibbonacci sequence:

var fib, fiborg;

fiborg = fib = function (x) {
  if(x < 2) return 1; else return fib(x-1) + fib(x-2);
}

We can then memoize it as follows:

fib = memoize(fiborg);
fib(20);

License

Released under an MIT license.

memoize.js's People

Contributors

Stargazers

Watchers

Forkers

mrexroad dineshkummarc jiahut anilkk lgsunnyvale alloyking bblokar alessioalex lagden evanhahn ashumeow mtco georapbox gustaff-weldon kr-js-plugin zhg-645479206 techdove

memoize.js's Issues

currentArg is implicitly global

You didn't lint your code. While you're fixing this issue, add some comments.

Add try/catch around JSON.stringify?

As @DmitryBaranovskiy commented;
"Should we add try/catch around JSON.stringify? There is a case when somebody passes cyclic structure to the function. It could not be able to cache it, but at least it should return the value."

var a = { b: null },
    b = { a: a };

a.b = b;

JSON.stringify(a); // >> TypeError: circular_structure

Trade-off is working code in 100% of cases vs performant code for majority of cases, with some broken edge cases.

Resolve issues for Underscore.js pull

I've taken the work we've done so far and put it into a pull request for inclusion in Underscore.js as a viable replacement to their _.memoize() method: jashkenas/underscore#330 (all tests pass).

Performance tests comparing the most recent version of memoize.js to underscore's implem are here from today: http://jsperf.com/comparison-of-memoization-implementations/12

If you take a look at the comments from Jeremy, his main concerns at the moment are that we've dropped the second argument in the memoize signature they use (the hasher function). He's also concerned about the dependency on the JSON object being present, and our reliance on it for stringification.

We do have an open issue attempting to solve this with an alternative, but as you might know, a reliable stringification method needs to cover lots of use cases and can't (as far as I know) be distilled down to something which they might consider including. With this in mind, I've got some questions:

Do you guys think we should pursue trying to get this into Underscore?.
What are your thoughts on a replacement to the JSON stringification we're doing at the moment? (I would look at the comments from Jeremy on the pull).
If we do factor in an optional hasher function, do you think we should apply this to just the pull request or this repo too?. I mentioned in the request, but I haven't really seen too many people need the second argument.

//cc @JamieMason @DmitryBaranovskiy

Cheers!
Addy

Multiple args aren't memoized properly

This is broken:

function test(a, b) {
  return a * 10 + b;
}

test(11, 1); // 111
test(1, 11); // 21

var memo = memoize(test);
memo(11, 1); // 111
memo(1, 11); // 111

Suggestion: build an array of args-to-be-memoized and then use JSON.stringify to convert that into a cache key. It's still not perfect, but it will reduce the number of edge cases.