Estaba tratando de implementar la función memoize en JS. He escrito una función por mí mismo.
Pero no funciona, no sé la razón por la cual la variable de cache se borra en cada llamada.
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(); Cuando muevo let cache={} fuera de la función, entonces el programa funciona bien.
Si alguien puede explicarme lo que me falta aquí, será de gran ayuda.
Porque cada llamada a fib llama a memoize(calcF) nuevamente, lo que crea un nuevo caché. Cada función memorizada se llama una sola vez en la línea m(n) .
Deberías escribir solo
const fib = memoize(calcF);o (innecesariamente)
const m = memoize(calcF); function fib(n) { return m(n); }Así que finalmente descubrí el problema con mi código. Hay otras muchas buenas opciones disponibles por ahí. Pero quería probarlo por mi cuenta. Así que comparto los problemas y la solución final aquí:
Hubo tres problemas en el código anterior:
fib dentro de calcF en lugar de llamar a calcF en sí.memoize .cache en calcF .función calcF(n, caché) {
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();