javascript函数的自动记忆

Question

我正在尝试用javascript实现内存化。这是代码：

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)
*/

它有效。。我可以计算O(n(中的值，但我失去了原来的函数。有什么方法可以访问原始的fib函数吗？感谢

Answer 1

如果要保留fib的原始非内存版本，则需要以某种方式修改fib，例如将递归函数作为参数传递。否则，递归fib调用将保留为函数的未存储版本。

例如：

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);