// Recursive function fib(n){ if (n < 2) return n; return fib(n-1) + fib(n-2); } // Memoized function memFib(n){ return memFib[n] || (memFib[n] = fib(n)); } // Mathematical function mathFib(n){ return Math.floor(Math.pow(Phi, n)/Math.sqrt(5) +.5); }How do they compare in speed?
[fib, memFib, mathFib].map(function(fn){ var t0 = +new Date fn(30); return +new Date - t0 });Don't get your panties in a bunch just yet. This is an unfair fight:
fib
is simply horrible, performance-wise. It's the easiest to understand and best for demonstrating recursive functions, but that's it.
memFib
is a great example for memoization, as it executes almost linearly, except for those numbers which have not been used yet. If you try runningmemFib
withn=40
, you will start feeling the pain, but only the first time.
An important point to make here about memoization is, if your function will be called many times and always returns the same result given the same arguments, memoizing is your friend.
// Y-combinator var Yfib = Y(function(fn){ return (function(n){ if (n < 2) return n; return fn(n-1) + fn(n-2); }); }); // Memoized Y-combinator var YmemFib = Ymem(function(fn){ return (function(n){ if (n < 2) return n; return fn(n-1) + fn(n-2); }); });This is a whole different game, with n=1000:
[mathFib, YmemFib].map(function(fn){ var t0 = +new Date fn(1000); return +new Date - t0 });Firefox 3.6.10 cries somewhere between
n=1000
and n=2000
about too much recursion, and the difference is less than 10 milliseconds in favor of the mathematical formula.Chrome 6.0.472.63 can handle at least
n=6000
before exhausting its stack and has a difference of about 2 milliseconds. BOOM.
The Much Anticipated Morale Of The Leonardo Of Pisa Thingamajigs
- Go for the mathematical solution first. If you are not smart enough, ask Google. If Google is not smart enough, ask Tyler. Seriously.
- Memoize. Remember this. Get it?
- Use a Y-combinator. You don't have to understand how to use it, and good luck trying. Seriously. Here you go:
function Y(fn) { return function(x) { return (fn(function(n){ return (Y(fn))(n); }))(x); }; }
To help you understand, try: matt.might.net, fixed point combinator on Wikipedia, Electronics and Computing Systems at the University of Cincinnati, the book To Mock a Mockingbird, and/or some entheogens.
/** * Memoizing Y-combinator (aka triptonomikon). */ function Ymem(fn) { var mem = this; return function(x) { return mem[x] || (mem[x] = (fn(function(n){ return (Ymem.call(mem, fn))(n); }))(x)); }; }
This should keep you busy until the next post.
To Mock a Mockingbird is awesome, but you can't mention Javascript Y-combinators without mentioning Crock's Little Javascripter:
ReplyDeletehttp://www.crockford.com/javascript/little.html
How does iterative compare with recursive? Also, how does the "miss" case for memoization compare to the recursive? I would guess that it would still be faster, since it converts double recursion to single recursion. You would save stack space to do it iteratively.
My guess is that you'll have a non-toy example for combinators, though, which is exciting.
Ah yes, I did forget Crockford's Little Javascripter.
ReplyDeleteIn an attempt to answer your iterative vs. recursive question, I found this page
Indeed, iteratively is much, much faster than recursively. What you mention about stack space is also what I suspect the reason for why Yfib is much faster.
Given that browsers are implementing optimization on their side, it's a bit more difficult to analyze the algorithms on javascript. For example, Chrome would handle n=8000 if I first run n=6000 on a cold start, non-memoized run
You guess correctly, I am working on an application for combinators, as part of a tiny, asynchronous framework.
Do you have any applications in mind?
Well, function calls are just way more expensive in JS with current JITs, so it might not be the stack per se, but the correlation between large stacks and recursive calls. Actually, TraceMonkey probably could handle this case the best if it traced recurisve calls (I'd guess it doesn't for now).
ReplyDeleteI don't really do much in JS-land anymore, so I don't really have any ideas for such aync frameworks. Actually, I don't think I really like much of either async or frameworks since I dislike the hollywood protocol (don't call us, we'll call you). I know I'm in the minority in the JS world, especially with JS-based server frameworks gaining some popularity.
I wonder what could be done with WebWorkers, as an alternative.
The implementation of Y-Combinator in your post is not in "closed form" because it remains recursive itself.
ReplyDelete@Anonymous, could you explain a bit the issue with "closed form"?
ReplyDeleteIt recursively calls itself while trying to avoid recursion of the Fibonacci function. For instance, non recursive example would be:
ReplyDeletevar Y = function(f) {
return function(g){
return g(g);
}(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
};