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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With