Estoy tratando de implementar la memorización en javascript. aquí está el código:
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) */funciona... Puedo calcular valores en O(n) pero perdí la función original. ¿Alguna forma de tener accesible la función fib original? Gracias
Si desea conservar la versión original no memorizada de fib , deberá modificar fib de alguna manera, como pasar su función recursiva como argumento. De lo contrario, las llamadas fib recursivas permanecerán como las versiones no memorizadas de su función.
p.ej:
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);