Javascript因子函数memoization

Question

我正在尝试将因子函数与memoization一起使用。我从对象中获取了最大值，以减少所做的递归调用次数。但问题是第一个电话是我不知道这是否优化，因为第一次通话非常昂贵。对此的任何见解都会很棒。

let cache = {0: 1};
function factMemoize(key) {
    if (!cache[key]) {
        let maxVal = Object.keys(cache).reduce(function (a, b) {
            return Math.max(a, b);
        });
        console.log(maxVal);
        while (key >= maxVal) {
            cache[key] = key * factMemoize(key - 1);
            maxVal++;
        }
    }
    return cache[key];
}

Answer 1

你没有从记忆中购买太多，因为你只使用一次值。在调用该函数之后，您确实有第二次调用的缓存，但我们经常将memoizing视为在函数期间仅存在的缓存中发生的事情。对于类似的东西，计算Fibonacci数是一个典型的例子，其中memoizing是对天真递归函数的巨大改进。

话虽如此，在你的函数中，你不清楚为什么你使用一个对象缓存然后搜索它。您可以使用一个数组，其中索引将是您要查找的数字。您不需要搜索它，只需从数字开始并递归调用下一个较低的数字。如果有缓存，它将返回。例如：

let cache = [1];
function factMemoize(key) {
    if (!cache[key]) {
      cache[key] = key * factMemoize(key - 1)
    } else { // just to demo cache:
        console.log("cache hit:", key)
    }
    return cache[key]
}

// only hits cache at the end 
console.log("6! = ", factMemoize(6))

// second call benefits from cache:
console.log("8! = ", factMemoize(8))