메모이제이션

메모이제이션()은 컴퓨터 프로그램이 복잡한 함수 호출의 결과값을 함수에 저장해놓고, 같은 입력이 반복될 때 저장한 값을 반환하도록 하여 속도를 높이는 최적화 기술이다. 동적 계획법의 핵심이 되는 기술이다.

 어원 
메모이제이션이라는 용어는 1968년 영국의 인공지능학자인 도널드 미키가 사용하였다. 영어 메모()로 흔히 축약되는 라틴어 단어 메모랜덤(, '기억되어야 할 것')에서 유래하였다. 같은 유래를 지닌 메모라이제이션(, 기억화)과 비슷하지만 구분되는 용어이다.

예제
피보나치 수열을 계산하는 간단한 방법은 다음과 같습니다.

 fib(n) {
    if n is 1 or 2, return 1;
    return fib(n-1) + fib(n-2);
 }

이때 fib 함수가 재귀적으로 실행되면서 같은 인자값에 대해서 계속해서 반복되므로, 전체 실행시간은 Ω(1.6n)이다. 그러나 fib(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 Θ(n)으로 줄일 수 있다.

 allocate array for memo, setting all entries to zero;
 initialize memo[1] and memo[2] to 1;

 fib(n) {
    if memo[n] is zero:
        memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
 }

적용
 검색
 HTML등과 같은소스 코드 생성
 암호화, 데이터 압축 영상변환과 같은 반복 계산
 음성 인식과 같은 패턴 인식
Game tree evaluation

 같이 보기 
 계산 복잡도 이론
 플라이웨이트 패턴
 느긋한 계산법
 구체화 뷰

 각주 

 외부 링크 
 Memoize.pm - memoize 서브루틴을 구현한 펄 모듈
 Java memoization - memoization 패턴을 만들기 위해 자바에서 dynamic proxy class를 이용한 예제.
 memoize - memoize 패턴을 구현한 루비 모듈
 Python memoization - memoization의 파이썬 구현 예제.

분류:소프트웨어 최적화
분류:컴퓨터 성능