пример за 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
бързо проследяване Q: в hashFunction защо бихте върнали това: #{a},#{k}, вместо това: [a,k] - person James; 16.04.2012
comment
@James: Хеш функцията трябва да върне нещо, което може да се използва като ключ в обекта memo, по-добре е да бъдете изрични за преобразуването, отколкото да разчитате на това, че браузърът прави нещо разумно с [a,k].toString(). - person mu is too short; 16.04.2012