_.memoizeを読んだ。
読んだ。
普段からコードリーディングする方じゃないけど、メモ化の実装が気になったのでunderscore.jsの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)); }; };
やってることは凄く簡単でクロージャでハッシュテーブル*1memoを用意する。
ハッシュ関数hasher*2はデフォルトがf(x) = x*3なので、気にしないとりあえずok。
apply呼び出しによってこの関数に渡される引数の配列arguments*4をhasherに渡す。渡した結果がkeyに渡され、最後にハッシュテーブルmemoの中に、keyが存在するかを確認し存在すればmemoから取り出し、そうでなければ被メモ化関数funcをapply呼び出ししハッシュテーブルへと計算結果を保存する。(てか、最後(memo[key] = func.apply(this, arguments))って書いてあるけど分かり難いからこの書き方好きじゃない。式なので結果が返るようになっているんだけど、単純に代入しているだけに見えるので嫌)
JavaScriptを知っていれば、比較的読みやすいし意味も分かりやすい。にしても、underscore.jsの中でunderscore.jsが使われているのマジでイカス。_.hasとか_.identityね。hasに至ってはhasOwnPropertyのシンタックスシュガーだし、そういう地味な工夫で読みやすくなるんだから嬉しい。
書いた。
どうせなので、coffeeで書きなおしてみた。hasherは良く分からないので省略した。
has = (obj, key) -> hasOwnProperty.call(obj, key) identity = (value) -> value memoize = (func) -> memo = {} return () -> key = identity.apply(@, arguments) return if has(memo, key) then memo[key] else memo[key] = func.apply(@, arguments)
使った。
fib = memoize (n) -> if n < 2 then n else fib(n-1) + fib(n-2) # => 354224848179262000000
