Memoization Pattern

메모이제이션(Memoization)은 동일한 계산을 반복해야 할 경우, 결괏값을 메모리에 저장해 두었다가 꺼내어 씀으로써 중복 계산을 방지하는 기법입니다. 딱 들어도 캐싱과 유사한 건가? 생각이 드는데, 메모이제이션은 넓게 말해서 캐싱의 일종으로 볼 수 있습니다. 좀 더 엄밀히 말하면, 최적화의 특정 사례라고 할 수 있습니다. 순수한 함수형 프로그래밍에서는 메모이제이션을 강력한 최적화 기법으로 소개하며, 내부적으로 자동으로 메모이제이션이 수행됩니다. 

일반적으로 함수 레벨에서 캐시하는 것을 지칭하는 경우가 많습니다. 

 

메모이제이션 vs 동적 계획법 vs 타뷸레이션
메모이제이션 : 계산이 필요한 순간 계산해서 저장하는 방식(Lazy-Evaluation)
동적 계획법 : 저장했던 값을 재활용해서 사용하는 방식
타뷸레이션 : 메모이제이션과 유사하나, 값을 미리 계산해둔다는 점에서 다름. 필요하지 않은 값도 미리 계산(Eager-Evaluation)

 

메모이제이션 패턴의 중요한 전제조건을 만족하는 함수라면 메모이제이션 사용이 가능한데, 이는 바로 점조적 투명성입니다. 참조적 투명성은 동일한 input에 대해 항상 동일한 output이 출력되어야 한다는 것을 의미합니다. 다른 말로 함수가 순수해야 한다고 표현하기도 하는데, 즉, 메모아이즈된 함수의 결과가 주어진 파라미터 이외에는 어떤 것에도 의존하지 않아야 하는 것입니다. 

 

대표적인 메모이제이션의 예시로 피보나치나 팩토리얼을 재귀 함수로 구현하는 예제를 많이 듭니다. 그 이유는 계산량이 많은 함수에서 메모이제이션을 사용할 때, 성능상 많은 이점을 얻을 수 있기 때문입니다. 

 

이 글에서도 피보나치 함수를 예제로, 자바스크립트를 이용하여 작성해 보도록 하겠습니다. 

 

먼저, 메모이제이션을 사용하지 않은 경우 피보나치는 아래와 같이 구현할 수 있습니다. 

function fibonacci(n) {
    return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
}
fibonacci(5); // result : 5

재귀 함수는 익히 알려진 것처럼 성능상 부하가 크지만, 가독성이 높습니다. 그래서 재귀 함수에 있어 메모이제이션은 성능의 향상을 위해 좋은 선택이 될 수 있습니다. 

 

위 함수를 실행한 결과는 아래와 같습니다.

console.time('no memoization');
fibonacci(40);
console.timeEnd('no memoization');
 
// result
//no memoization: 2497.051025390625ms

시간이 꽤 오래 걸리는 것을 확인할 수 있습니다. 그렇다면 여기에 메모이제이션 패턴을 적용하여 코드를 작성해 보겠습니다. 

var memoizedFibonacci = (function(n) {
    var memo = {};
     
    var fibo = function(num) {
        if(num < 2) {
            return num;
        } else {
            const f1 = memo[num -1] || fibo(num -1);
            const f2 = memo[num - 2] || fibo(num -2);
            const result = f1 + f2;
            memo[num] = result;
             
            return result;
        }
    };
 
    return fibo;
})();
 
memoizedFibonacci(5); // result : 5

마찬가지로 메모이제이션을 적용한 함수의 성능을 측정해보면 아래와 같습니다. 

console.time('no memoization');
memoizedFibonacci(100);
console.timeEnd('no memoization');
 
// result
// memoization: 0.010986328125ms

메모이제이션 없이 피보나치를 구현했을 때 성능이 2497.051025390625ms 인데 반해, 메모이제이션을 사용한 피보나치 함수의 경우 0.010986328125ms 로 성능 차이가 매우 많이 나는 것을 확인할 수 있습니다. 이런 간단한 피보나치에서도 이렇게 성능 차이가 많이 나는데, 비즈니스 로직이 들어가고, 코드가 더 복잡해진다면 이 차이는 더욱 두드러지게 날 것입니다. 

 

그렇다면 이제 메모이제이션을 조금 업그레이드해 보겠습니다. 

 

---

 

메모이즈 기능을 필요한 메서드 내에서 직접 구현하는 것이 아니라, 메서드를 입력받아 메모이즈 기능을 제공해주는 Memoizer 모듈을 만들어 보겠습니다.

 

아래에서 만들어 볼 Memoizer는 function을 입력받아 private method인 cacher를 호출하고 연산 결과를 반환합니다.

var Memoizer = (function() {
    var cache = {};
     
    function cacher(func){
        return function(){
            var key = JSON.stringify(arguments);
             
            if(cache[key]){
                return cache[key];
            }else{
                var value = func.apply(this, arguments);
                cache[key] = value;
                return value;
            }
        }
    }
 
    return {
        memo: function(func){
            return cacher(func);
        }
    }
})()

• cache 객체 : 이미 계산한 결과를 저장해 둘 객체. 메서드의 매개변수 객체를 key로, 메서드 연산 결과가 value로 저장됩니다.
• cacher 메서드 : 내부 private 메서드로, cache를 확인하여 저장된 값이 있으면 바로 return, 없으면 입력값으로 들어온 메서드를 실행하고 그 결과를 cache에 저장한 뒤 return 합니다.  
• arguments 객체 : 자바스크립트의 모든 함수가 가지는 유사 배열 객체. 함수 호출 시 담긴 파라미터 정보를 가지고 있는 객체.  
• memo 메서드 : 외부에 노출되는 메서드로, 메모이즈를 적용하고자 하는 메서드가 입력값으로 들어옵니다. 

 

Memoizer 모듈을 이용하여 피보나치 함수를 구현하면 아래와 같습니다. 

var fibonacci = Memoizer.memo(function(n){
    return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
});
 
//메서드 호출
fibonacci(5)    //result : 5

피보나치 함수 구현부를 memo의 입력으로 넣어주면 동일하게 사용이 가능합니다.

 

메서드의 동작을 조금 더 자세히 살펴보기 위해서 cacher function 내에서 cache를 콘솔에 출력해보면, 이 메서드의 호출 결과는 아래와 같습니다. 

fibonacci 메서드의 호출시마다, cache 객체에 arguments를 key로 하는 연산 결과가 저장되는 것을 확인할 수 있습니다. 피보나치의 경우 입력값이 단순 int값이기 때문에 arguments의 0번째 값을 꺼내서 key로 사용하는 것이 더 깔끔해 보일지는 모르나, 여러 메서드가 Memoizer를 사용하게 된다고 가정했을 때, 입력값으로 무엇이 들어올지 모르기 때문에 arguments 객체 자체를 key로 사용하는 것이 더 좋습니다. 동일하게 arguments를 콘솔에 출력해보면 아래와 같습니다. 

※ 위 함수의 경우 Memoization 패턴을 모듈화 하여 사용하는 방법에 대해 소개하기 위해 간단하게 작성한 코드로, 매개변수 유형이 동일한 서로 다른 메서드가 존재할 경우 정상적으로 동작하지 않습니다. 따라서 이 경우 싱글턴으로 객체를 사용하지 않고, 필요한 메서드마다 new로 생성하여야 각 메서드마다 메모리가 잡히게 됩니다. 인스턴스를 생성하는 Memoizer 모듈 코드는 아래와 같습니다. 

function Memoizer() {
    var cache = {};
     
    var cacher = function(func){
        return function(){
            var key = JSON.stringify(arguments);
              
            if(cache[key]){
                return cache[key];
            }else{
                var value = func.apply(this, arguments);
                cache[key] = value;
                return value;
            }
        }
    }
  
    this.memo = function(func){
         return cacher(func);
    }
}
 
//Memoizer에 function 넘겨주는 코드
var fibonacci = new Memoizer().memo(function(n){
    return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
});
 
//메서드 호출
fibonacci(5)    // result : 5