자바스크립트 메모이제이션(memoization) 사용하기

자바스크립트에서는 반복적으로 계산되는 함수는 메모이제이션 패턴을 사용하여 구현합니다.
계산 결과를 저장해 놓아 이후에 다시 계산할 필요없이 사용가능하도록 저장해놓은 캐싱과 같은 기능 메모이제이션이라고 합니다.

아래에서 피보나치수열로 예를들어보도록 하겠습니다.

피보나치수열은 

0, 1, 1, 2, 3, 5, 8, 13, 21, ... 으로 나타나는 수열입니다.

일반코드 #1

function fibonacci(n) {

    if (n < 2) {
          return n;

    }

    else {

          return fibonacci(n-1) + fibonacci(n-2);

    }

}

fib(5); //실행코드 -> 결과: 

일반코드 #2
: 삼항연산자를 사용하여 코드 정리

function fibonacci(n) {

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

}

memoization을 사용한 코드 #3
: memo 배열에 계산한 값을 저장해 놓은 후, 다시 계산하지 않고 사용하도록 개선

let memo = [0,1];

function fibMemoization(n) {
    if(typeof memo[n] !== 'number') {
        memo[n] = fibMemoization(n-1) + fibMemoization(n-2);
    }
    return memo[n];
}
fibMemoization(5);

연산할 값이 크면 클수록 memoization을 사용했을 때와 하지 않았을때의 성능은 크게 차이가 납니다.

재귀적으로 fibonacci함수를 몇번 호출하는지 비교를 통해서 알아볼 수 있습니다.

let count = 0;

function fib(n) {
    count++;
    console.log('called fib: ', count); //총 177번 호출
    return n<2 ? n : fib(n-1) + fib(n-2);
}

fib(10); 


let memo = [0,1];
let count = 0;

function fibMemoization(n) {
    count++;
    console.log('called fibMemoization: ', count); //총 19번 호출
    if(typeof memo[n] !== 'number') {
        memo[n] = fibMemoization(n-1) + fibMemoization(n-2);
    }
    return memo[n];
}
fibMemoization(10); 

모두 즐거운 코딩하세요~