안녕하세요. 송기석입니다.

오늘 날씨를 보면서 아~ 봄이구나 했습니다. 지금 입고 있는 겨울 옷을 봄 옷으로 바꿔 입어야겠습니다.

메모이제이션(memorization)

함수의 불필요한 작업을 피하기 위해서 이전에 연산한 결과를 저장하고 있는 객체를 사용할 수 있습니다. 이러한 최적화 기법을 메모이제이션(memoization)이라고 합니다. 자바스크립트의 객체와 배열은 메모이제이션이 매우 유용합니다.

다음 코드를 실행 해 보겠습니다.

var fibonacci = function (n) {

  // console.log("호출 되었다. !!!");

  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);

};

for (var i = 0; i <= 10; i += 1) {

  console.log('// ' + i + ': ' + fibonacci(i));

}

"// 0: 0"

"// 1: 1"

"// 2: 1"

"// 3: 2"

"// 4: 3"

"// 5: 5"

"// 6: 8"

"// 7: 13"

"// 8: 21"

"// 9: 34"

"// 10: 55"

이런 결과가 나옵니다. 이 때 Fibonacci()는 얼마나 호출 되었을까요? 453번입니다. 이중 직접 호출한 것은 11번이고 나머지는 계산을 위해 했던 계산을 또 하는 호출 입니다.

앞에서 실행한 것과 같은 결과를 보여주는 코드 입니다. 차이가 있다면 앞에서는 함수호출이 453번이었다면 이것은 계산하기 위해 29번만 호출합니다.

var fibonacci2 = function () {

  var memo = [0, 1];

  var fib = function (n) {

    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 += 1) {

  console.log('// ' + i + ': ' + fibonacci2(i));

}

이 함수를 일반화할 수 있습니다.

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 fibonacci = memoizer([1, 1], function (shell, n) {

return n + shell(n – 1);

};

오늘 한 메모이제이션은 다시 사용하게 될 부분을 배열로 저장하여 필요에 따라 직접 불러다 사용하여 최적화 할 수 있는 좋은 방법입니다.