메모이제이션 (Memoization)

메모이제이션 (Memoization)

메모이제이션 (Memoization) 이란 이름대로 메모 를 하는 것이 특징인데,
프로그래밍에서 반복되는 결과를 메모리에 저장 해놓고 다음에 같은 결과가 나올 때 다시 계산할 필요없이 빨리 실행 하는 기법이다. 마치 캐싱 과 같은 기능이라고 할 수 있다.

JavaScript에서는 클로저 를 통해 계속 유지되는 저장공간을 만들 수 있기 때문에, 이것을 이용하면 메모이제이션 패턴을 구현할 수 있다.

메모이제이션 예시

만약 일반적인 재귀함수로 피보나치 수열 을 계산하는 함수를 구현하려고 한다면 다음과 같을 것이다.

피보나치 수열은 바로 앞 두 항의 합으로 이루어진 수열이다. 다음과 같이 진행된다.
0, 1, 1, 2, 3, 5, 8, 13, 21, ......

// 피보나치 수열을 재귀 함수로 계산하는 함수
var count = 0;
var fibonacci = function(number) {
    count ++;
    return number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2);
}

for(var i = 0; i <= 10; i++) {
    console.log(fibonacci(i)); // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
}
console.log("count : " + count) // count : 453

위 처럼 반복문으로 구현은 가능하지만 파라미터로 10이라는 비교적 작은 수를 주었는데도 fibonacci 함수는 453번이나 실행된다. 여기서 11번은 직접 호출한 것이지만, 나머지 442번은 이미 계산한 값들을 다시 계산하기 위해 호출한 것이다.

예를 들어, number가 4일 때만 예상해봐도 전에 계산한 값을 매번 다시 계산하는 패턴을 확인할 수 있다.

fibonacci(0) = fibonacci(0)
fibonacci(1) = fibonacci(1)
fibonacci(2) = fibonacci(0) + fibonacci(1) = fibonacci(0) + fibonacci(1)
fibonacci(3) = fibonacci(1) + fibonacci(2) = fibonacci(1) + (fibonacci(0) + fibonacci(1))
fibonacci(4) = fibonacci(2) + fibonacci(3) = (fibonacci(0) + fibonacci(1)) + (fibonacci(1) + (fibonacci(0) + fibonacci(1)))

이때, 메모이제이션 패턴을 이용하면 반복되는 연산을 줄일 수 있다.
이미 계산한 내용들을 저장해두고, 다시 연산할 필요없이 저장된 데이터를 불러오는 방식이다.

var count = 0;
var fibonacci = function() {
    var memo = [0, 1];
    var fib = function(number) {
        count++;
        var result = memo[number];
        if(typeof result !== 'number') {
            result = fib(number - 1) + fib(number - 2);
            memo[number] = result;
        }
        return result;
    };
    return fib;
}();

for(var i = 0; i <= 10; i++) {
    console.log(fibonacci(i)); // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
}
console.log("count : " + count) // count : 29

우선 눈에 띄게 fibonacci 함수 실행 횟수가 줄어든 것을 확인할 수 있다. 이전에 453번 실행되던 것이 29번만 실행되는데 이것은 불필요한 연산을 줄였기 때문이다. 29번 중 11번은 이전과 똑같이 직접 호출한 것이고 18번은 메모이제이션 결과를 얻기 위해 호출한 것이다.

전자의 경우에는 1에서 10까지의 모든 수를 비교하기 위해 fibonacci 함수가 호출이 되었지만, 메모이제이션 패턴에서는 memo라는 배열을 만들어 계산한 값을 저장해두고 그 배열을 클로저를 통해 접근한다. 로직을 처리하는 클로저가 반복하며 수행하기 때문에 더 빠르게 처리할 수 있는 것이다. 연산해야할 값이 크면 클수록 메모이제이션을 사용했을 때 성능은 크게 차이가 난다.

마무리

예제로는 메모이제이션에서 메모 하는 대상을 변수로 들었지만, JavaScript에서는 변수가 될 수도 있고 함수가 될 수도 있다. 또한 메모이제이션은 속도면에서 큰 이점이 있지만 속도를 위해 많은 메모리 사용량이 소비되기 때문에, 많은 RAM을 사용하는 함수를 처리해야 할 경우 영향을 준다고 한다.
아직까지 연산이 많이 필요한 코드를 작성해볼 일이 없어서 사용해보지 못했지만, 복잡한 연산이 있는 경우에 유용하게 쓰일 것 같다.

Reference

• 메모이제이션(memoization)
• 자바스크립트에서 메모이제이션(Memoization) 패턴
• 성능 향상을 위한 자바스크립트 메모이제이션 이해하기