I was trying to implement memoize function in JS. I have written a function by myself.
But it is not working, I don't know the reason why cache variable is getting cleared on every call.
function calcF(n) {
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
function memoize(cb) {
let cache = {};
return function () {
const arg = arguments[0];
console.log(cache); // getting empty object always
if (cache[arg]) {
return cache[arg];
} else {
const res = cb(arg);
cache[arg] = res;
return res;
}
};
}
function fib(n) {
const m = memoize(calcF);
return m(n);
}
console.time();
console.log(fib(10));
console.timeEnd();
When I move let cache={} outside of the function, then program is working fine.
If any can explain me what I am missing here, the it will be a really great help.
Because every call to fib calls memoize(calcF) again, which creates a new cache. Each memoised function is called only a single time in the line m(n).
You should write just
const fib = memoize(calcF);
or (unnecessarily)
const m = memoize(calcF);
function fib(n) {
return m(n);
}
So finally I found out the issue with my code. There are other plenty of good options available out there. But I wanted to try it from my own. So sharing the issues and the final solution here:
There were three issues in above code:
fib inside calcF instead for calling calcF itself.memoize.cache in calcF.function calcF(n, cache) {
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
let l, r;
if (cache[n - 1]) {
l = cache[n - 1];
} else {
const res = calcF(n - 1, cache);
cache[n - 1] = res;
l = res;
}
if (cache[n - 2]) {
r = cache[n - 2];
} else {
const res = calcF(n - 2, cache);
cache[n - 2] = res;
r = res;
}
return l + r;
}
function memoize(cb) {
let cache = {};
return function () {
const arg = arguments[0];
// getting empty object always
if (cache[arg]) {
return cache[arg];
} else {
const res = cb(arg, cache);
cache[arg] = res;
return res;
}
};
}
const m = memoize(calcF);
function fib(n) {
return m(n);
}
console.time();
console.log(fib(6));
console.timeEnd();
console.time();
console.log(fib(61));
console.timeEnd();
console.time();
console.log(fib(100));
console.timeEnd();
console.time();
console.log(fib(102));
console.timeEnd();