I'm trying to implement memoization in javascript. here's the code:
function memoize(func) {
var history = {}
var inner = function(n) {
if (n in history) {
return history[n];
}
let result = func(n)
history[n] = result;
return result;
}
return inner;
}
function fib(n) {
if (n <= 1) {
return n;
}
return fib(n-1) + fib(n-2)
}
/*
fib = memoize(fib);
console.log(fib(20)) // O(n)
*/
/*
fib2 = memoize(fib);
console.log(fib2(20)) // O(2^n)
*/
it works.. I can calculated values in O(n) but I lost the original function. any way to still have the original fib function accessible? thanks
If you want to retain the original un-memoized version of fib you'll need to modify fib in some way, such as passing your recursive function as an argument. Otherwise, the recursive fib calls will remain as the un-memoized versions of your function.
eg:
function memoize(func) { // potentially update this to accept as hash function to calculate the key for `history` to make this more generic
var history = {}
var inner = function(n, ...args) {
if (n in history) {
return history[n];
}
let result = func(n, ...args);
history[n] = result;
return result;
}
return inner;
}
function fib(n, recursiveFn = fib) {
if (n <= 1) {
return n;
}
return recursiveFn(n - 1, recursiveFn) + recursiveFn(n - 2, recursiveFn)
}
const fastFib = memoize(fib);
console.log(fastFib(40, fastFib)); // O(n)
const slowFib = fib(40); // O(2^n)
console.log(slowFib);