Javascript 阶乘函数内存

Question

我正在尝试将阶乘函数与内存结合使用。我从对象中获取了最大值以减少递归调用的次数。但问题是第一次调用我不知道这是否经过优化，因为第一次调用非常昂贵。对此的任何见解都会很棒。

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

记住这个值并不会带来什么好处，因为每个值只使用一次。调用该函数后，您确实拥有用于第二次调用的缓存，但我们通常认为内存是发生在仅在函数期间存在的缓存中的事情。对于类似的事情，计算斐波那契数是一个典型的例子，其中内存是对朴素递归函数的巨大改进。

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

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