Memoization

Posted 2008.04.30 01:51
순수(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


  1. Favicon of http://shurain.egloos.com BlogIcon 슈레인

    | 2008.04.30 03:17 | PERMALINK | EDIT | REPLY |

    memorization이 아니라 memoization입니다. 기억하다의 memorize가 아니라 to be remembered의 memorandum에서 온 말입니다.

  2. Favicon of https://skyul.tistory.com BlogIcon 서광열 lambda

    | 2008.04.30 03:23 신고 | PERMALINK | EDIT |

    수정했습니다. 계속 memoization이란 단어로 읽어왔는데, 별 생각없이 memorization으로 기억하고 있었군요^^;

  3. Favicon of http://www.grayger.com/pw/ BlogIcon grayger

    | 2008.05.01 00:29 | PERMALINK | EDIT | REPLY |

    배경지식이 부족해서 잘 이해가 안가는데요^^; 이 방법이 python이나 다른 언어에도 적용될 수 있나요?

  4. Favicon of http://skyul.tistory.com BlogIcon 서광열

    | 2008.05.01 11:54 | PERMALINK | EDIT |

    네. 함수를 인자로 받아서 리턴할 수 있는 파이썬에서는 쉽게 되고, 자바에서도 커맨드 패턴 등으로 해볼 수 있을 겁니다.

  5. Favicon of http://dejavus.tistory.com BlogIcon Dejavus

    | 2008.05.14 17:33 | PERMALINK | EDIT | REPLY |

    앗 이것은 알고리즘 시간에 배운 그것!
    다이나믹 알고리즘 돌릴때 이렇게 하면
    속도가 상당히 빨라졌던 걸로 기억합니다.

  6. Favicon of http://azurespace.tistory.com BlogIcon Azurespace

    | 2008.12.20 13:44 | PERMALINK | EDIT |

    반복문을 이용한 일반적인 상향식 다이나믹 프로그래밍이 가능한 경우, memoization은 성능면에서 약간 떨어지는 편입니다.

Write your message and submit
« PREV : 1 : ··· : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 27 : ··· : 244 : NEXT »