4

underscore.js _.memoize() の動作例を教えてもらえますか?

できれば hashFunction を使用し、さらに好ましくは coffeescript を使用しますか?

これは、coffeescript の SICP からのかわいい変更カウント関数のわずかに変更されたバージョンです。

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に非常に慣れていないので、そのコードをより慣用的にするための助けも大歓迎です.

4

1 に答える 1

17

ここでの使用の 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外に移動しました。私の<code> firstdenominationがあなたのものよりも優れているかどうかは味の問題であるかどうか、私はAを使用することに対してバイアスがあります単純なルックアップ テーブルを YMMV で実装します。ccccswitch

メモ化されたバージョンでは、「cc の 211 回の繰り返し」と表示されます。デモ: http://jsfiddle.net/ambiguous/FZsJU/

メモ化されていないバージョンでは、「cc の 8141 回の繰り返し」と表示されます。デモ: http://jsfiddle.net/ambiguous/Xn944/

したがって、メモ化されていないバージョンでは、呼び出しの頻度が最大cc40 倍になります。メモ化は、ハッシュ関数の計算オーバーヘッド (私のものはデモンストレーション目的には十分ですが、正確には最適化されていません) とキャッシュ ルックアップのオーバーヘッドに応じて、価値がある場合とない場合があります。これは、メモ化するときに尋ねる標準的な質問です。キャッシュはキャッシュされた計算よりも高速ですか?

の実装を見ると_.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ます。キーが見つかった場合は、キャッシュされた値をすぐに返すことができます。それ以外の場合は、(おそらく) 遅い方法で計算し、キャッシュしてから返します。

于 2012-04-16T03:31:26.280 に答える