クロージャを使ってメモ化

tech


「4.15メモ化」からのメモ。


この本によるとメモ化とは

関数は、不要な処理を省略するために、前回の操作結果をオブジェクトに記憶しておくことができる。この最適化はメモ化と呼ばれる

クロージャの説明と同じく、これも言葉だけじゃわかりづらいと思うので、プログラマーならコードで説明ですよね。
（クロージャについてはこれでクロージャも怖くない - maru sourceを参照）

フィボナッチ数列

例としてフィボナッチ数列を計算する関数を実装します。
フィボナッチ数とは以下のように定義されています。

  • n番目のフィボナッチ数をF(n)とします
  • F(0) = 1 , F(1) = 1とします
  • F(n) = F(n-1) + F(n-2)で求められます
普通に実装

では普通に実装してみます。

var count = 0;

var fibonacci = function(n)
{
  count++; //実行された回数をカウント
  return (n < 2 ? n : fibonacci(n -1) + fibonacci(n - 2));
};

for(var i = 0 ; i < 20 ; i++)
{
  document.write(i + " : " + fibonacci(i) + "<br/>");
};

alert(count); //35400

fibonacci()は全部で35400回実行されます。

メモ化を使って実装

では次にメモ化を使って実装します。そもそもメモ化とはどういうことかというのを、フィボナッチ数を例に挙げて説明します。
n番目のフィボナッチ数F(n)を求めるときに、すでにF(n-1)とF(n-2)がわかっていてどこかに記憶されていると、F(n)はすぐにわかります。この「既に求めてある値をどこかに記憶しておく」というのがメモ化です。
では実際にメモ化を使ってフィボナッチ関数を実装してみます。

var count = 0;

var fibonacci = function()
{
  var memo = [0, 1]; //n番目のフィボナッチ数を記憶しておく配列

  var fib = function(n)
  {
    count++; //実行された回数をカウント

    var result = memo[n];
    if(typeof result !== "number")
    {
      result = fib(n - 1) + fib(n - 2);
      memo[n] = result; //n番目のフィボナッチ数をメモしていく
    }
    return result;
  };

  return fib;
}();

for(var i = 0 ; i < 20 ; i++)
{
  document.write(i + " : " + fibonacci(i) + "<br/>");
};

alert(count); //56

fibonacci()は全部で56しか実行されません。メモ化を使わない普通の実装に比べて圧倒的に少ない回数で済みます。
(メモ化の威力がわかりやすい実行例になっているからというのもありますけどね）

メモ化のモジュール化

このようにメモ化をうまく使うと非常に効率化することができます。しかしいちいちメモ化の処理を書いていたのでは、面倒なので、メモ化部分を切り出してモジュール化してみます。

var memoizer = function(memo , fundamental)
{
  var shell = function(n)
  {
    var result = memo[n];
    if(typeof result !== "number")
    {
      result = fundamental(shell , n);
      memo[n] = result;
    }
    return result;
  };
  return shell;
};

//フィボナッチ関数
var fibonacci = memoizer([0, 1] , function(shell , n)
{
  return shell(n - 1) + shell(n - 2);
});


//階乗関数
var factorial = memoizer([1 , 1] , function(shell , n)
{
  return n * shell(n - 1);
});



いやー、メモ化ってすごいですね。