пример underscore.js _.memoize() в действии?

Может ли кто-нибудь привести пример 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, и любая помощь в том, чтобы сделать этот код более идиоматичным, тоже приветствуется.


javascript coffeescript memoization sicp underscore.js
person James    schedule 16.04.2012    source источник

Ответы (1)


arrow_upward
17
arrow_downward

Одним из вариантов использования 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.

В запомненной версии написано «211 итераций cc», демо: http://jsfiddle.net/ambiguous/FZsJU/< /а>

Версия без запоминания говорит «8141 итерация cc», демо: 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 используется для преобразования аргументов мемоизированной функции в ключ в memo; если мы находим ключ, то мы можем немедленно вернуть кэшированное значение, в противном случае мы вычисляем его (предположительно) медленным способом, кэшируем его и возвращаем.

person mu is too short    schedule 16.04.2012
comment
Ух ты! фантастический ответ по всем направлениям. Большое спасибо за все подробности и реструктуризацию. Все очень проникновенно. - person James; 16.04.2012
comment
быстрое продолжение Вопрос: почему в хэш-функции вы возвращаете это: #{a},#{k} вместо этого: [a,k] - person James; 16.04.2012
comment
@James: хэш-функция должна возвращать что-то, что можно использовать в качестве ключа в объекте memo, лучше явно указать преобразование, чем полагаться на то, что браузер сделает что-то разумное с [a,k].toString(). - person mu is too short; 16.04.2012