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

你不会从记忆中得到太多，因为你只使用一次每个值。调用该函数后，您确实拥有第二次调用的缓存，但我们通常认为记忆是发生在仅在函数运行期间存在的缓存中的事情。对于类似的事情，计算斐波那契数是一个经典的例子，其中记忆是对朴素递归函数的巨大改进。

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

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

Answer 2

正如@mark-meyer 在此线程中提到的，记忆结果没有任何优势，因为每个值在计算过程中只会计算一次。 Mark 提供的解决方案非常适合以后通过重新调用具有相同或不同值的阶乘来重用该函数。在这种情况下，您可以通过重用现有结果来加快流程并降低时间复杂度。

这是它在闭包中的样子：

function factorialFn() {
  const cache = [];

  return function _factorial() {
    if (n < 2) {
      return 1;
    }
    if (cache[n]) {
      return cache[n];
    }
    return cache[n] = n * _factorial(n - 1);
  }
}

然后，你可以这样使用它：

const factorial = factorialFn();

factorial(5); // 120
factorial(7); // 5040

在第一次调用时，它会计算factorial(5)并将其保存在缓存中以备将来参考。

在第二次调用时，factorial(7) 将执行 7 * factorial(6)、
，其中 factorial(6) 基本上是 6 * the cached value of factorial(5)

Javascript 阶乘函数记忆

Javascript factorial function memoization

javascript

performance

memoization

factorial