Graphics Programming

메모이제이션(Memoization) 본문

Season 1/하스켈

메모이제이션(Memoization)

minseoklee 2014. 10. 11. 09:25
물론 하스켈 위키에 관련 페이지가 있는데
HaskellWiki: http://www.haskell.org/haskellwiki/Memoization

이해가 안 돼... 그래서 그냥 직접 따져봄

-- 재귀를 이용한 피보나치 수 구하기
fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n-2) + fib (n-1)


뻔하지만 똑같은 걸 여러 번 계산하는 게 문제다.

fib 3 = fib 1 + fib 2 = fib 1 + (fib 0 + fib 1)
fib 4 = fib 2 + fib 3 = (fib 0 + fib 1) + (fib 1 + fib 2) = (fib 0 + fib 1) + (fib 1 + fib 0 + fib 1)

명령형 언어에서는 배열을 하나 마련해서 계속 갱신하면 되는 쉬운 문제다.

// ActionScript 3.0
function fib(n:int):int {
  var a=1, b=1, temp
  for(var i=2; i<n; i++){
    temp = b
    b = a + b
    a = temp
  }
  return b
}


그런데 하스켈에서는 갱신이 안 돼잖아

발상: 무한 리스트 [0..]에 피보나치 함수를 매핑하고 피보나치 함수는 이 리스트를 이용한다.

map fib [0..]

fib 0 = 1
fib 1 = 1
fib n = 저 리스트를 참조해야 하는데


리스트에 이름을 붙여주자

f = (map fib [0..]) where
  fib 0 = 1
  fib 1 = 1
  fib n = f !! (n-2) + f !! (n-1)

-- 피보나치 수의 메모이제이션 버전
memo_fib n = f !! n


배열로 하면 그냥 되는데 하스켈에선 이렇게 신기해

f는 지연 평가되기 때문에 f에서 앞의 10개만 떼온다거나 하면 fib 0, fib 1, ... fib 9를 따로 계산할 필요 없이 하나의 리스트로 통째로 잘라낼 수 있다.

이제 memo 함수를 일반화해보자. 잘 살펴보면 fib는 [0..] 내의 정수들을 인자로 받아 결과값을 산출한다. 그럼 fib와 같은 종류의 모든 함수에 memo를 적용할 수 있다는 말이다.

memo :: (Int -> a) -> Int -> a
memo f n = (map f [0..]) !! n

-- 일반화한 memo를 이용한 memo_fib
memo_fib = memo fib n where
  fib 0 = 0
  fib 1 = 1
  fib n = memo fib (n-2) + memo fib (n-1)


일반화를 더 할 수 있을 것 같다. map은 리스트에만 작동하고, n은 map에서 특정 원소를 추출하기 위한 인덱스다. 그럼 map을 더 일반화된 map으로, 리스트 [0..]는 다른 자료구조로, n은 그 자료구조에 알맞은 종류의 인덱스로... 일반화하면... 여기까지. 멘붕이 온다 -_-
Comments