underscore.js的_.memoize()函数的实际应用示例是什么？

Question

有人能给我一个underscore.js _.memoize()的实例吗？

最好使用hashFunction，更好的是用coffeescript编写。

这里是一个稍微修改过的SICP中可爱的计数函数的coffeescript版本：

countChange = (amount)->

  cc = (amount, kindsOfCoins)->

    firstDenomination = (kindsOfCoins)->
      switch kindsOfCoins
        when 1 then 1
        when 2 then 5
        when 3 then 10
        when 4 then 25

    if amount is 0 then 1
    else if amount < 0 or kindsOfCoins is 0 then 0
    else 
      (cc amount, (kindsOfCoins - 1)) + 
      (cc (amount - firstDenomination(kindsOfCoins)), kindsOfCoins)

  cc amount*100, 4


console.log "Ways to make change for $0.85: " + countChange(.85)

如何在示例中使用underscore的_.memoize()函数呢？非常感谢您提前的帮助！另外，请不要犹豫地指出函数编写方式中的问题，因为我对coffeescript非常陌生，希望能得到更多关于代码风格的建议。

- James

Answer 1

在这里使用memoize的一个用途是减少对内部函数cc的调用次数：

n = 0
countChange = (amount)->
  firstDenomination = (kindsOfCoins) ->
    [1, 5, 10, 25][kindsOfCoins - 1]

  cc = (amount, kindsOfCoins)->
    ++n # This is just a simple counter for demonstration purposes
    return 1 if amount is 0
    return 0 if amount < 0 or kindsOfCoins is 0
    (cc amount, (kindsOfCoins - 1)) +
      (cc (amount - firstDenomination(kindsOfCoins)), kindsOfCoins)

  cc = _.memoize cc, (a,k) -> "#{a},#{k}"

  cc amount*100, 4

console.log "Ways to make change for $0.85: #{countChange(.85)}"
​console.log "#{n} iterations of cc"

我还稍微调整了一下内容以便紧凑，并将firstDenomination移出cc以简化cc，至于我的firstDenomination是否比你的更好，这是一个品味问题，我偏向于不使用switch来实现简单的查找表，但你的看法可能不同。

记忆化版本显示"211次cc迭代"，演示：http://jsfiddle.net/ambiguous/FZsJU/

非记忆化版本显示"8141次cc迭代"，演示：http://jsfiddle.net/ambiguous/Xn944/

因此，非记忆化版本调用cc的次数大约多了40倍。记忆化可能值得，也可能不值得，这取决于哈希函数的计算开销（我的足以进行演示，但并不是完全优化的），以及缓存查找的开销。这是记忆化时需要考虑的标准问题：缓存是否比被缓存的计算更快？

如果我们看一下_.memoize的实现：

// Memoize an expensive function by storing its results.
_.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。 memo对象被用作缓存，hasher被用来将记忆函数的参数转换为memo中的键；如果我们找到了该键，则可以立即返回缓存的值，否则我们按照（可能）较慢的方式计算它，将其缓存并返回。

- mu is too short

---

哇！全面的答案真是太棒了。非常感谢您提供的所有细节和重组。都非常有见地。 - James

快速跟进问题：在哈希函数中，为什么要返回这个："#{a},#{k}"，而不是这个：[a,k]？ - James

@James：哈希函数必须返回可用作memo对象中键的内容，最好明确转换而不是依赖浏览器对[a,k].toString()做出合理处理。 - mu is too short