2012-04-16 6 views
4

誰でも私にunderscore.js _.memoize()の動作例を教えてもらえますか?underscore.js _.memoize()の実際の動作の例ですか?

好ましくはhashFunctionを使用し、さらに好ましくは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を使用する場合があります。ここでは

はCoffeeScriptの中SICPからそのキュートな変更カウント機能を少し変更したバージョンですか?

事前に感謝します。

ps ..また、機能がコード化されている方法で穴を開けることを躊躇しないでください。私はcoffeescriptに非常に新しいですし、そのコードをもっと慣用的にすることについての助けも歓迎です。

答えて

17

一つ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" 

私はまた、物事にコンパクトさのために少しを並び替えていると私は簡単にするためにccfirstDenomination外を移動私がそこにいる間にcc;私のfirstDenominationがあなたよりも優れているかどうかは味わいの問題ですが、私はswitchを使ってシンプルなルックアップテーブルだがYMMV。 http://jsfiddle.net/ambiguous/Xn944/

だから、非メモ化バージョンはccを呼び出す:デモ、非メモ化バージョンは「CCの8141回の繰り返し」を言うhttp://jsfiddle.net/ambiguous/FZsJU/

メモ化バージョンは、「CCの211回の繰り返し」、デモを言います〜40回以上頻繁に。 memoizationは、ハッシュ関数の計算上のオーバーヘッド(鉱山はデモ目的では十分ですが、正確には最適化されていません)とキャッシュルックアップのオーバーヘッドに応じて、価値があるかもしれません。これはメモをとるときに尋ねる標準の質問です:キャッシュされた計算よりも速いキャッシングですか?

我々は_.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のキーに変換するために使用されます。キーを見つけると、キャッシュされた値をすぐに返すことができます。それ以外の場合は、おそらく遅い方法で計算し、キャッシュして返します。

+0

うわー!全面的に素晴らしい答えです。すべての詳細とリストラに感謝します。すべての非常に洞察力のある。 – James

+0

クイックフォローアップQ:hashFunctionで、なぜこれを返すのですか?:[a、k] – James

+0

@James:ハッシュ関数は何かを返す必要があります'memo'オブジェクトのキーとして、' [a、k] .toString() 'で賢明なやり方をブラウザーに頼るよりも変換を明示する方が良いでしょう。 –

関連する問題