4

谁能给我一个 underscore.js _.memoize() 的例子吗？

最好使用hashFunction，甚至更喜欢在coffeescript中？

这是来自咖啡脚本中 SICP 的可爱变化计数函数的略微修改版本：

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)

例如，我如何使用下划线的 _.memoize() ？

提前谢谢了！

ps ..另外，请不要犹豫，在该函数的编码方式上留下漏洞。我对coffeescript很陌生，也欢迎任何关于使该代码更惯用的帮助。

4

1 回答 1

17

这里的一种用途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我的​​​​​​​​​​​​​​​​​​​​<code>firstDenomination是否比你的更好是一个品味问题，我对使用a switchto有偏见实现一个简单的查找表，但 YMMV。

记忆的版本说“cc的211次迭代”，演示：http: //jsfiddle.net/ambiguous/FZsJU/

非记忆版本说“cc 的 8141 次迭代”，演示：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用于将 memoized 函数的参数转换为 key in memo；如果我们找到键，那么我们可以立即返回缓存的值，否则我们会以（可能）慢的方式计算它，缓存它，然后返回它。

于 2012-04-16T03:31:26.280 回答