JavaScript: クロージャーでメモ化してくれる関数を作ってみた

メモ化っていまいちよくわかっていなかったが、「クロージャを使ってメモ化」を読んで初めてピンときたので、自分でわかるようにES6で書いてみました。

まずは普通に

メモ化してないバージョンのフィボナッチ数列と階乗です。

//フィボナッチ数列
const fibo = n =>
  (n === 0)? 0
  : (n === 1)? 1
  : fibo(n-1) + fibo(n-2)

//階乗
const facto = n =>
  (n === 0)? 1
  : (n === 1)? 1
  : n * facto(n-1)

メモ化した

//フィボナッチ数列
const fibo2 = (
  () =>{
    const memo = [0,1]
    const a = n =>
      (n >= memo.length)? memo[n] = a(n-1) + a(n-2)
      : memo[n]
    return a
  }
)()

//階乗
const facto2 = (
  () =>{
    const memo = [1,1]
    const a = n =>
      (n >= memo.length)? memo[n] = n * a(n-1)
      : memo[n]
    return a
  }
)()

memoには最初初期値のみが入っていて、memo[n]がなかったら再帰的に計算してmemo[n]に代入しつつ返し、memo[n]があればそれを返す、という作戦です。

メモ化してくれる関数

上のふたつを比べると、初期値と再帰的に計算してる部分が違うだけなので、初期値を inits 、計算規則を rule として引数にくくりだしてみます。

const memoizer = inits => rule =>{
  const memo = [...inits]
  const a = n =>
    (n >= memo.length)?  memo[n] = rule(a)(n)
    : memo[n]
  return a
}

これを使うとそれぞれこうなります。

//フィボナッチ数列
const fibo3 = memoizer([0,1])( a => n => a(n-1) + a(n-2) )

//階乗
const facto3 = memoizer([1,1])( a => n => n * a(n-1) )

それぞれ,
$ a_{0}=0,a_{1}=1,a_{n}=a_{n-1}+a_{n-2} $
や
$ a_{0}=1,a_{1}=1,a_{n}=n a_{n-1} $
に、見えてきません?
こうしておくと、初期値と漸化式で表わされる数列が簡単にメモ化して使える。便利かも。

追記：非再帰版

const memoizer = inits => rule =>{
  const memo = [...inits]
  const a = n => {
    if(n >= memo.length) {
      for(let i = memo.length; i <= n; i++) {
        memo[i] = rule( a )( i )
      }
    }
    return memo[n]  
  }
  return a
}