javascript - 下划线memoize在javascript中是如何实现的

Question

我正在开发自己的函数式编程库，现在引用下划线。

memoize _.memoize(function, [hashFunction])

Memoizes a given function by caching the computed result. Useful for speeding up slow-running computations. If passed an optional hashFunction, it will be used to compute the hash key for storing the result, based on the arguments to the original function. The default hashFunction just uses the first argument to the memoized function as the key.

var fibonacci = _.memoize(function(n) {
  return n < 2 ? n: fibonacci(n - 1) + fibonacci(n - 2);
});

上面的不处理array就可以实现自动内存的代码看起来有点神奇，我看了下面的源代码，但我仍然不清楚内部设计。

 // Memoize an expensive function by storing its results.
  _.memoize = function(func, hasher) {
    var memoize = function(key) {
      var cache = memoize.cache;
      var address = hasher ? hasher.apply(this, arguments) : key;
      if (!_.has(cache, address)) cache[address] = func.apply(this, arguments);
      return cache[key];
    };
    memoize.cache = {};
    return memoize;
  };

有人可以简要介绍一下发生了什么吗？

感谢。

Answer 1

memoize 有一个缓存 (memoize.cache = {}) 用于存储函数调用的结果。当它被调用时，它通过两种方式确定一个地址来存储结果:调用hasher函数，或者key参数。

哈希函数是这样工作的(来自下划线页面):

If passed an optional hashFunction, it will be used to compute the hash key for storing the result, based on the arguments to the original function. The default hashFunction just uses the first argument to the memoized function as the key.

然后，它调用您传递给 func.apply(...) 的函数，并将结果存储在 cache[address] 中。

第二次调用内存函数时，结果已经在缓存中(!_.has(..) 将返回 false)并且计算成功' 重复。

我不明白为什么它返回 cache[key] 而不是 cache[address] 很难...在我看来 cache[address] 将是正确的选择。

更新

正如评论中所指出的，您提供的代码不是 memoize 的最新实现。这是最新的实现 (1.6.0):

_.memoize = function(func, hasher) {
    var memo = {};
    hasher || (hasher = _.identity);
    return function() {
      var key = hasher.apply(this, arguments);
      return _.has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
    };
  }; 

它的工作方式相同，除了它更优雅一点；如果未提供 hasher 函数，它使用 _.identity 作为键，这是一个简单地返回作为参数传递的值的函数:

_.identity = function(value) { return value; }

除此之外，cache 现在称为 memo 但工作方式相同。