Memoization

순수(pure) 함수, 다른 말로 참조 투명한(referential transparent) 함수는 수학적인 함수와 마찬가지로 같은 인자를 넣으면 언제나 같은 값을 돌려줌을 보장하는 함수입니다. 간단한 예로, OCaml로 작성된 다음 피보나치 수열 함수(fib)는 참조 투명한 함수입니다.

let rec fib = function
    0 | 1 as i -> i
    | i -> fib (i - 1) + fib (i - 2)

위 fib 함수는 비효율적으로 작성되어 있기 때문에 무척 느립니다. 이런 순수 함수를 최적화하는 방법으로 알고리즘 자체를 꼬리 호출(tail recursion)하도록 변경하거나 더 나은 알고리즘을 찾는 방법 등도 있겠지만, 함수를 그대로 두고 메모리 공간을 희생해서 속도를 향상하는 최적화 방법으로 기억(memoization)이 있습니다.

다음 memo 함수는 Developing Applications With Objective Caml에서 발췌한 예입니다.

let memo f =
        let table = ref [] in
        let rec find_or_apply entries x =
            match entries with
                (x', y) :: _ when x' = x -> y
            | _ :: entries -> find_or_apply entries x
            | [] ->
                    let y = f x in
                    table := (x, y) :: !table;
                    y
        in
        (fun x -> find_or_apply !table x)

이 함수의 타입은

val memo : ('a -> 'b) -> ('a -> 'b)

로 원래 함수와 동일한 타입의 함수를 리턴합니다. 코드를 살펴보면 table을 두고 계산 결과를 저장해서 한 번 f(e) 값이 불리면 두 번째 불리는 f(e)는 새로 계산하지 않고 저장된 값을 쓰게 됩니다. 일종의 동적 프로그래밍(dynamic programming) 기법입니다.

기억(memorization)이 가능한 이유는 함수가 참조 투명하기 때문입니다. 매번 호출할 때마다 값이 바뀌는 함수라면 이전 함수의 결과를 저장해뒀다가 재활용하는 것이 불가능하기 때문입니다.

어느 정도 속도 향상이 있었는지 측정하기 위해서 시간을 재는 함수를 다음과 같이 만들어 봅니다.

let time f x =
    let start = Sys.time () in
    let y = f x in
    let finish = Sys.time () in
    Printf.printf "Elapsed time: %f seconds\n" (finish -. start);
    y
;;

OCaml은 함수 언어고 a + b라고 해서 a를 b보다 먼저 연산(evaluation)한다는 보장이 없습니다. IO의 경우는 순서가 중요하기 때문에, IO의 순서를 정하기 위해서 위와 같이 let 구문을 연달아 늘어 놓는 방법을 많이 씁니다. 앞서 let이 새로운 스코프(lexical scope)을 만들기 때문에 순서가 보장되게 됩니다.

let memo_fib = memo fib;;

time memo_fib 35;;
time memo_fib 35;;

fib를 memo로 감싸서 memo_fib 함수를 정의한 다음에 2번 불러보면 두 번째는 이미 계산된 저장 값을 가져 오기 때문에 매우 빠르게 계산됨을 확인할 수 있습니다.

Elapsed time: 2.579000 seconds
Elapsed time: 0.000000 seconds