콘텐츠로 건너뛰기
Home » 하스켈에서 메모이제이션 구현하기

하스켈에서 메모이제이션 구현하기

하스켈의 메모이제이션

하스켈의 함수는 순수함수이고, 이는 입력이 같다면 항상 같은 결과가 리턴되는 것을 보장한다. 이는 어떤 임의의 함수 f와 그 인자 x가 있을 때 최초 f(x)가 계산되고 나면 그 이후에 f(x)가 필요한 경우에 불필요한 반복 계산이 필요하지 않은 것 처럼 들린다. (왜냐면 f(x)는 이미 이전에 계산되어 값으로 축약되었고, 그 사이에 어떤 일이 있었든지 간에 같은 인자에 대해서는 하스켈의 함수는 같은 결과를 내놓을 것이기 때문이다.)
하지만 이것은 다른 문제이다. 이는 하스켈이 기본적으로 모든 함수 적용 연산에 대해 그 결과를 캐싱한다는 이야기인데, 실제로 이런 일은 일어나지 않는다. 당연하게도 프로그램의 생애 주기가 얼마나 될지 알 수 없기 때문에 캐싱에 무한정 리소스를 소모할 수도 없기 때문이다. (그외에도 몇 가지 이유가 더 있겠지만…)
따라서 메모이제이션이 필요하다면 이는 프로그래머가 직접 수행하도록 코드를 작성해야 한다. 다른 언어에서 메모이제이션은 키-값 쌍으로 이루어지는 맵 구조를 이용해서 한 번 계산된 결과를 이 맵내에서 업데이트하는 식으로 처리한다. 예를 들어 파이썬의 메모이제이션은 다음과 같이 이루어진다.

memo = {}
def memoized_func(n):
  if n in memo:
    return memo[n]
  result = .....
  memo[n] = result
  return result

그런데 하스켈에서는 어떨까? 하스켈에서는 이러한 방식을 사용할 수 없다. 이 동작은 함수가 호출되었을 때 함수 외부의 값을 변경하는 부수효과를 동반하는데, 순수함수형 언어에서는 이런 동작이 허용되지 않는다.
그렇다고 방법이 없는 것은 아니다. 메모이제이션의 기본적인 아이디어는 이미 계산된 값을 어딘가 저장하고 있는 것이다. 따라서 “함수를 값으로 변환한다”는 대담한 발상을 기반으로 다음과 같이 처리할 수 있다. 대신에 우리가 염두에 두는 메모이제이션을 적용할 함수는 Int <span style="font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif;">-</span>> a 타입의 함수라고 하자.

  1. 메모이제이션을 위해서는 Int와 a 타입의 값을 각각 짝지어놓을 수 있는 어떤 자료 구조가 필요하다.
  2. List 타입을 생각해보면 (!!)를 이용해서 인덱스(Int)로 값(a)을 액세스할 수 있다.
  3. 따라서 함수호출은 함수를 사상한 리스트에 대한 원소 접근으로 환원해볼 수 있다.

실제로 이 아이디어가 가능한지 시험해보자.

테스트 1

기본적으로 적당히 오래 걸리는 함수 하나를 생각해보자. 소수 판별 검사가 좋겠다. 하스켈에서의 소수 판별 검사 함수는 적당히 느리게 작성하면 아래와 같이 쓸 수 있다.

isPrime :: Int -> Bool
isPrime n | n < 2     = False
          | n < 4     = True
          | otherwise = all ((/= 0).(n `mod`)) [2..(n-1)]

엄청 간단하다. 2보다 작은 경우 그리고 2와 3인 경우를 제외하면 임의의 자연수 N에 대해서 2…N-1 까지 자연수로 N을 나눠서 나누어 떨어지는 경우가 한 번도 없으면 소수가 되는 것이다.
그러면 이 함수의 메모이제이션 버전은 어떨까? 하스켈의 느긋한 연산을 활용할 수 있다.

isPrimeMemo :: Int -> Bool
isPrimeMemo = ((map f [0..]) !!) where
            --  ~~~~~~~~~~~ 소수판별결과를 리스트로 만들어서 N 번째 값을 구한다.
      f n | n < 2     = False
          | n < 4     = True
          | otherwise = all ((/= 0).(n `mod`)) [2..(n-1)]

무척이나 이상하게 생겼다. 만약 isPrimeMemo 173을 호출하면 어떤 일이 생길까?

  1. isPrimeMemo 173은 기본적으로 (!!) 173 . map f $[0..]이다. 따라서 0부터 시작하는 무한리스트를 f로 맵핑한 결과에서 173번째 원소를 찾는다.
  2. f는 isPrime과 동일한 내용으로 정의되어 있다.
  3. 다시 isPrimeMemo 173이 호출되었다. 이때 문제의 리스트 (함수 f의 적용 결과가 모여있는)에서 최소한 173번째 원소까지는 맵핑이 완료된 상황이기 때문에 계산을 거치지 않고 그 값을 찾아서 리턴하게 된다.

실제로 두 번 이후의 호출부터는 빨라지는지 확인해보자. 이를 위해 함수 호출의 시간을 계산하는 timeIt 함수를 사용한다. 이 함수는 timeit이라는 패키지에 포함되어 있는데, 기본적으로 설치되어 있지 않으니 cabal을 이용해서 설치해야 한다.
테스트는 1에서 1만까지의 소수를 찾아서 그 합을 계산해서 출력하는 것을 4회 시행해본다.

import Control.Monad
import System.TimeIt
isPrimeMemo :: Int -> Bool
isPrimeMemo = ((map f [0..]) !!) where
      f n | n < 2     = False
          | n < 4     = True
          | otherwise = all ((/= 0).(n `mod`)) [2..(n-1)]
main = do
    print "START"
    forM_ [1..4] $ \_ -> timeIt . print . sum . filter isPrimeMemo $ [1..10000]

결과는 다음과 같다.

"START"
5736396
CPU time:   2.42s        # 최초 실행시
5736396
CPU time:   0.27s        # 이후부터는 매우 빠르게 실행된다.
5736396
CPU time:   0.28s
5736396
CPU time:   0.28s

근데 가만보면 메모아이즈된 함수의 꼴이 원래 외부에 정의한 함수 모양과 완전히 똑같다. 따라서 일반적인 Int <span style="font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif;">-</span>> a 타입의 함수를 메모아이즈 할 수 있는 형태로 함수를 만들어 볼 수 있을 것이다.

memoize :: (Int -> a) -> Int -> a
memoize fBody = ((map fBody [0..]) !!)
isPrimeMemo = memoize isPrime

이렇게 정의한 뒤 테스트해보아도 같은 결과를 얻을 수 있다.

테스트 2

메모이제이션이나 수행속도 최적화에 관련해서 소수 판별 검사보다도 더 유명한 문제가 있으니 바로 피보나치 수열의 일반항을 구하는 것이다. 사실 피보나치 수열의 일반항은 하스켈에서는 메모이제이션 보다는 무한 리스트를 느긋한 방식으로 다루는 식으로 매우 우아하고 효율적으로 계산할 수 있는데, 여기서는 그게 목적이 아니므로 교과서의 정의를 충실히 따라 보도록 하자.

fibo :: Int -> Integer
fibo n | n < 3     = toInteger $ n - 1
       | otherwise = fibo (n-1) + fibo (n-2)
fiboMemo = memoize fibo
-- 35정도면 적당히 느릴 것으로 보여진다.
main = do
    print "START"
    forM_ [1..4] $ \_ -> timeIt . print . fiboMemo $ 35

결과는 다음과 같다. 뭔가 예상했던 것과는 다르다.

"START"
5702887
CPU time:  17.95s
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s

2차 이후의 시행은 매우 빠르게 캐싱된 값을 성공적으로 사용했다는 것을 알겠다. 그런데 첫 시행이 너무 오래 걸렸다. 왜 이런 문제가 생길까? 그것은 fibo 함수가 isPrime과는 달리 재귀적으로 자신을 호출하기 때문이다. fiboMemo의 호출과정을 따라가보면

  1. fiboMemo 35가 호출되면 (map fibo [0..]) !! 35가 호출된다.
  2. 이 때 fibo 35를 평가하게되고, 이는 fibo 34 + fibo 33 이런식으로 계산해야 하는 양이 폭발하기 시작한다. 그런데 메모아이즈 된 함수는 fiboMemo이지 fibo가 아니다. 최종적으로 fiboMemo 35의 값은 캐싱이 되지만, 그 중간과정에 쓰인 fib는 그렇지 못하기 때문에 반복 계산을 엄청나게 많이 한다.

이와 비슷한 문제가 Swift에서도 있었다. WWDC에 소개된 예제에서는 그야말로 mind-blowing한 방법을 동원해서[^1] 이 문제를 해결했다. 하스켈에서의 해법도 이와 거의 유사하다.

fibo2 :: Int -> Integer
fibo2 n | n < 3     = toInteger $ n - 1
        | otherwise = fiboMemo2 (n-1) + fiboMemo2 (n-2)
fiboMemo2 = memoize fibo2
main = do
  print "START"
  forM_ [1..4] $ \_ -> timeIt . print . fiboMemo2 $ 35

절차형 언어에 익숙한 사람이라면 이해가 가지 않을 수 있다. 저 두 함수는 뭔가 정의의 순서 자체가 꼬인게 아닌가? 싶은데, 하스켈은 “느긋하게” 계산하고, 또 “순수함수”이기 때문에 정의의 순서나 계산의 순서가 별로 중요하지 않다. 코드 앞쪽에 언급된 함수 정의나 표현식은 필요할 때가 되어서야 평가되며, 순수함수는 지금 계산하나 나중에 계산하나 그 값이 다를리가 없기 때문에 문제가 되지 않는다.
약간의 트릭을 활용하면 조금 더 와닿는 형태로 정의할 수 있을지 모르겠다.

fastFibo = memoize body
           where
           body n
             | n < 3     = n - 1
             | otherwise = fastFibo (n-1) + fastFibo (n-2)

어쨌거나 fiboMemo2나 fastFibo를 이용해서 계산하면 우리가 기대했던 대로 올바른 동작을 하는 것을 확인할 수 있다.

"START"
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s

그외 논의 사항

피보나치 수열의 경우, 지수적 시간 복잡도를 가지는 문제를 리니어한 시간대로 끌어내렸다. 하지만 리스트를 탐색해야 하는 한계가 있기 때문에 이러한 메모이제이션이 만능 탄환으로 작동하지는 못할 것이다. (당장 소수 검사의 문제만 해도 숫자가 커지면 되려 느려질 수도 있다.) 따라서 이진 탐색 트리와 같이 보다 빠르게 요소를 찾을 수 있는 자료구조의 도입이 필요하다.
또한 함수를 리스트로 변환하는 과정의 한계 때문에 Int 타입 인자 함수에만 유효하다. 이는 다른 타입을 정수로 해시할 수 있다면 극복가능할 것으로 보인다.
fix 함수(참고: Data.Function)에 대한 논의가 있다. fix 함수는 fix x = lef x = f x in x라는 알쏭달쏭한 함수인데 지금으로서는 도무지 이해가 안된다. 좀 더 연구해볼 필요가 있을 것 같다.

태그: