javascript メモ化

　関数の複数回呼び出しによって発生する不要な処理を省略するために、前回までの結果をオブジェクトに記憶できるメモ化という最適化の考え方があります。
jsのオブジェクトと配列はこのメモ化を行うのに最適です。


フィボナッチ数を計算する再帰関数を作ってみる。　関数呼び出しの際に呼び出された回数も同時にカウントします。

//fibonacci.js

var fibonacciCount = 0;
 
 var fibonacci = function(n) {
     fibonacciCount++;
     return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
 };

 for (var i = 0; i<=10; i+=1) {
       print(i + ":" + fibonacci(i));
  }
 print("fibonacci Called Count = " + fibonacciCalledCount);

↑の呼び出し結果
0:0
1:1
2:1
3:2
4:3
5:5
6:8
7:13
8:21
9:34
10:55
fibonacci Called Count = 453

という感じで、0から１０までのフィボナッチ数計算できているのですが、問題があって、計算過程でfibonacciの関数が453回も呼び出されて非常に無駄になってます

0から１０までのそれぞれのフィボナッチ数は１回計算したらそれを使えばいいので、どこかに保持しておいてそれを使えばだいぶ無駄な処理が減ります。

ここで先ほどの関数の中に結果を記憶する配列memoを用意して、そこに結果が入ってた場合はmemoから値をとるようにしてみると

var fibonacci = function() {
    var memo = [0,1];
    var fibCount = 0;
    var fib = function(n) {
        fibCount++;
        //配列から結果を取得
        var result = memo[n];

        if (typeof result !== 'number') {
            result = fib(n-1) + fib(n-2);

            memo[n] = result
        }

        return result;

    };
    return fib;
}();

for (var i = 0; i<=10; i++) {
    print(i + ": " + fibonacci(i));
}

こうすると、fib関数が29回しか呼び出されないようになる



参照: javascript goodparts