在行动中使用underscore.js _.memoize()的例子？

Question

任何人都可以给我一个下划线.js _.memoize()的例子吗？

优选使用hashFunction,甚至更优选使用coffeescript？

以下是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很新,任何帮助使代码更加惯用也是受欢迎的.

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,以实现一个简单的查找表但是YMMV.

memoized版本说"211迭代的cc",演示:http://jsfiddle.net/ambiguous/FZsJU/

一个非memoized版本说"8141次cc的迭代",演示:http://jsfiddle.net/ambiguous/Xn944/

因此,非记忆版本的调用频率要高出cc约40倍.记忆可能是值得的,也可能不值得,这取决于散列函数的计算开销(我的充分用于演示目的但未完全优化)和高速缓存查找的开销.这是memoizing时要问的标准问题:缓存是否比缓存计算更快？

如果我们看一下执行情况_.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 memo; 如果我们找到密钥,那么我们可以立即返回缓存的值,否则我们计算它(可能)缓慢的方式,缓存它,并返回它.