[Algorithm] Advanced Fibonacci using Memoization

 

 

Memoization

 

함수형 프로그래밍 언어인 Javascript에서 계산 결과를 저장해두는 방식으로 하위 함수를 호출하는 방식이다. 값을 저장할 객체를 생성하고 하위 함수에서 계산된 값을 객체에 저장하면서 재귀 알고리즘을 최적화 할 수 있다.

 

예시

advanced fibonacci algorithm

 

function fibonacci(n) {
	// Memoization 객체
    const fibo_cache = {};

	// 하위 함수
    // 하위 함수에서는 fibo_cache를 참조하고 있기 때문에, 
    // fibo_cache는 메모리 상에서 제거되지 않고 값을 유지하게 된다.
    // subFunc() 함수의 렉시컬 환경에서는 지속적으로 fibo_cache를 참조해서
	// 로직을 구성할 수 있다.
    const subFunc = (n) =>{
        console.log(fibo_cache);
        if(n in fibo_cache) return fibo_cache[n];
        if(n < 2) return n;
        return fibo_cache[n] = subFunc(n-1)+subFunc(n-2);
    }

    return subFunc(n);
  }

 

fibonacci() 함수의 내부 함수 subFunc()는 지속적으로 외부 변수인 fibo_cache 객체를 참조한다. subFunc() 함수는 선언되는 시점에서 외부 변수를 참조하고 있기 때문에 클로저가 된다. 반복적인 함수 호출이 일어나도 fibo_cache 객체는 메모리 상에서 제거되지 않는다.

 

성능 비교

 

Memoization을 적용한 피보나치 함수에 매개변수로 30이 전달되었을 때 실행횟수는 59번이다. 

function fibonacci_advanced(n) {
    
    const fibo_cache = {};

    const subFunc = (n) =>{
        count++;
        if(n in fibo_cache) return fibo_cache[n];
        if(n < 2) return n;
        return fibo_cache[n] = subFunc(n-1)+subFunc(n-2);
    }

    return subFunc(n);
  }

 

반면 일반 피보나치 함수에 매개변수로 30이 전달되었을 때 호출횟수는 무려 2,692,537번이다.

function fibonacci(n){
    count++;
    if(n<2) return n;

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

 

➜  Javascript node test.js
fibonacci_acvanced() :  832040 59
fibonacci() :  832040 2692537

 

 

Memoization은 반복되는 계산이 많을 수록 효과가 높아진다. 피보나치 함수 처럼 재귀 함수가 반복적으로 일어나는 경우 호출 횟수는 기하급수적으로 증가하기 때문에, Memoization이 최적화 기법이 될 수 있다.