example of underscore.js _.memoize() in action?

coffeescript, javascript, memoization, sicp, underscore.js

Solution

One use of `memoize` here would be to reduce the number of calls to the inner `cc` function:

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"

I've also rearranged things a little bit for compactness and I moved `firstDenomination` outside of `cc` to simplify `cc` while I was there; whether my ​​​​​​​​​​​​​​​​​​​​​​​​​​`firstDenomination` is better than yours is a matter of taste, I have a bias against using a `switch` to implement a simple lookup table but YMMV.

The memoized version says "211 iterations of cc", demo: http://jsfiddle.net/ambiguous/FZsJU/

A non-memoized version says "8141 iterations of cc", demo: http://jsfiddle.net/ambiguous/Xn944/

So the non-memoized version calls `cc` ~40 times more often. The memoization may or may not be worthwhile depending on the computational overhead of the hashing function (mine is sufficient for demonstration purposes but not exactly optimized) and the overhead of the cache lookup. This is the standard question to ask when memoizing: is the caching faster than the cached computation?

If we look at the implementation of `_.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));
  };
};

then you can see how it works and how the `hasher` is used. The `memo` object is used as a cache, and the `hasher` is used to convert the arguments of the memoized function to a key in `memo`; if we find the key then we can return the cached value immediately, otherwise we compute it the (presumably) slow way, cache it, and return it.

Problem

Can anyone give me an example of underscore.js _.memoize() in action? Preferably using the hashFunction, and even more preferably in coffeescript? Here is a slightly modified version of that cute change counting function from SICP in 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) ``` How might I use underscore's _.memoize() on that for example? Many thanks in advance! ps.. also, please don't hesitate to shoot holes in the way that function was coded.. I'm very new to coffeescript and any help on making that code more idiomatic is welcome too.

Original source