пример 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) 

Как я мог бы использовать _.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 итераций куб.см", демо: http://jsfiddle.net/ambiguous/FZsJU/

Не-memoized версии говорит "8141 итерациях куб.см", демо: http://jsfiddle.net/ambiguous/Xn944/

Так, не memoized версия вызывает 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 функции в ключ в memo; если мы найдем ключ, мы можем немедленно вернуть кешированное значение, иначе мы вычислим его (предположительно) медленный путь, кешем его и вернем.