javascript - Memoize 没有按预期工作？

Question

我目前正在学习记忆化。作为一个简单的练习，我用斐波那契数列实现了内存。但是，我遇到的问题是，为什么当我不重命名内存函数时，它的完成速度比重命名时要慢。看一下代码。

这无法正常工作，也无法正确缓存。

function memoize(func) {
  const cache = {};

  return function(args) {
    const cacheKeys = Object.keys(cache).map(el => +el);
    if (cacheKeys.includes(args)) {
      return cache[args];
    }
    cache[args] = func(args);
    return cache[args];
  };
}

function wrapped_fibonacci(n) {
  if (n <= 2) {
    return 1;
  }
  return wrapped_fibonacci(n - 1) + wrapped_fibonacci(n - 2);
}

const fibonacci = memoize(wrapped_fibonacci); // <== I do not rename the function.

for (let i = 1; i <= 40; i++) {
  console.log(fibonacci(i));
}

但是，当我这样编写代码时。它工作正常并且性能良好

function memoize(func) {
  const cache = {};

  return function(args) {
    const cacheKeys = Object.keys(cache).map(el => +el);
    if (cacheKeys.includes(args)) {
      return cache[args];
    }
    cache[args] = func(args);
    return cache[args];
  };
}

function fibonacci(n) {
  if (n <= 2) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci = memoize(fibonacci); //<== I rename the function

for (let i = 1; i <= 40; i++) {
  console.log(fibonacci(i));
}

正如你所看到的。我刚刚重新分配了函数名称。我正在 node.js v8.3.0 上进行这些测试

第一个结果就是这样。

time node fib.js

real    0m2.413s                                                                                                       │~                                                                                                                     
user    0m2.400s                                                                                                       │~                                                                                                                     
sys     0m0.008s 

第二个的结果是这样的

time node fib.js

real    0m0.263s                                                                                                       │~                                                                                                                     
user    0m0.252s                                                                                                       │~                                                                                                                     
sys     0m0.008s  

相差 1.8 秒

有谁能解释一下吗？

Answer 1

在工作示例中，您将使用也称为 fibonacci 的内存函数替换 fibonacci。递归调用正在使用此记忆化函数，因为 fibonacci-the-original 已被 fibonacci-the-memoized 替换。

在非工作示例中，您从 wrapped_fibonacci 创建一个内存函数 fibonacci，但该函数仍然递归调用 wrapped_fibonacci，即未内存的原始函数。

如果您还替换了 wrapped_fibonacci，它会再次加速:

const fibonacci = wrapped_fibonacci = memoize(wrapped_fibonacci)