Last active
May 19, 2016 02:32
-
-
Save skilbjo/1849e88cecc5e3d2130ee02fc4ef2cd1 to your computer and use it in GitHub Desktop.
Programming paradigms implementing the fibonacci sequence
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Recursive => Funcational, yay! But dat runtime doe.. :( | |
var recursive_fib = function(n){ | |
if(n<=1) return n; | |
return recursive_fib(n-2) + recursive_fib(n-1); | |
}; | |
// Recursive w/ memoization (caching) => Funcational + performant! | |
var recursive_memo_fib = function(n){ | |
var f = function(n,cache){ | |
if( cache[n] ) { | |
return cache[n]; | |
} else { | |
if(n<=2) return cache[n]; | |
cache[n] = ( (n-1>=3 ? f(n-1,cache)[n-1] : f(n-1,cache) ) + | |
f(n-2,cache) | |
); | |
return cache; | |
} | |
}; | |
return f(n,{0:0,1:1,2:1})[n]; | |
}; | |
// Iterative => Boring ! | |
var iterative_fib = function(n){ | |
var fib = 1, current = 0, prev = 1; | |
for(var i=2; i<=n;i++){ | |
fib = prev + current; | |
current = prev; | |
prev = fib; | |
} | |
return fib; | |
}; | |
var n = 34; | |
var hrstart_recursive_fib = process.hrtime(); | |
recursive_fib(n); | |
var hrend_recursive_fib = process.hrtime(hrstart_recursive_fib); | |
var hrstart_recursive_memo_fib = process.hrtime(); | |
recursive_memo_fib(n); | |
var hrend_recursive_memo_fib = process.hrtime(hrstart_recursive_memo_fib); | |
var hrstart_iterative_fib = process.hrtime(); | |
iterative_fib(n); | |
var hrend_iterative_fib = process.hrtime(hrstart_iterative_fib); | |
console.info('Recursive: %d ms', hrend_recursive_fib[1]/1000000); | |
console.info('Memoization: %d ms', hrend_recursive_memo_fib[1]/1000000); | |
console.info('Iterative: %d ms', hrend_iterative_fib[1]/1000000); | |
// Results => | |
// Recursive: 82.507861 ms | |
// Memoization: 0.32665 ms | |
// Iterative: 0.067584 ms |
Author
skilbjo
commented
May 19, 2016
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment