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

하스켈의 메모이제이션

하스켈의 함수는 순수함수이고, 이는 입력이 같다면 항상 같은 결과가 리턴되는 것을 보장한다. 이는 어떤 임의의 함수 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 -> a 타입의 함수라고 하자.

  1. 메모이제이션을 위해서는 Inta 타입의 값을 각각 짝지어놓을 수 있는 어떤 자료 구조가 필요하다.
  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. fisPrime과 동일한 내용으로 정의되어 있다.
  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 -> 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)  

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

"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라는 알쏭달쏭한 함수인데 지금으로서는 도무지 이해가 안된다. 좀 더 연구해볼 필요가 있을 것 같다.

WWDC의 자동 메모이제이션 코드 분석

시간이 오래 걸릴 수 있는 비싼 연산 작업이 있고, 이러한 연산을 반복해서 수행해야 하는 상황이 있을 때, 가장 손쉬운 성능 개선 방법은 연산 결과를 캐싱하는 것이다. 연산을 수행하는 함수가 입력이 같을 때 출력이 같은 것이 보장되는 순수한 함수라면, 재계산을 수행하는 것보다 캐시된 내용을 읽어와서 사용하는 것이 훨씬 빠른 것은 자명한 사실이다.

메모이제이션(Memoization)

실제로 이런 종류의 문제는 제법 흔하고 실제로도 계산 결과를 캐시해서 사용하는 것은 좋은 해결책 중 하나이다. 어떤 문제가 더 작은 부분문제들로 나뉠 수 있고, 전체 문제는 작은 부분문제들의 반복 계산에 의해 산출되는 것이라면 이 패턴을 적용하여 성능을 높일 수 있다. 이러한 패턴을 메모이제이션(memoization)이라 한다.

메모이제이션은 캐시를 위해 약간의 메모리 자원을 소모하는 대신에 수행 속도를 그만큼 높일 수 있는 테크닉이다. 실제로도 기존 함수를 간단하게 수정하는 것으로 메모이제이션을 적용할 수 있는데, 만약 기존 함수가 제 3자가 작성한 라이브러리에 있는 것이라 수정이 불가능하다면 메모이제이션이 적용된 형태로 변경하는 함수를 만들어서 사용할 수 있을 것이다. (이러한 패턴은 파이썬에서는 데코레이터 등을 사용해서 많이 쓰인다.)

이와 관련해서 14년 WWDC에서는 자동 메모이제이션(auto memoization)이라는 테크닉을 소개하였는데, 가히 그 코드가 mind-blowing 하다고 할 만큼 언뜻 봐서는 이해가 불가능해 보일 지경으로 신묘하다.

해당 세션에서 소개된 코드의 최종형태는 아래와 같다.1

func memoize<T: Hashable, U> (body: @escaping ((T) -> U, T) -> U) -> (T) -> U
{
  var memo = Dictionary<T, U>()
  var result: ((T)->U)!
  result = { x in 
    if let q = memo[x] { return q }
    let r = body(result, x)
    memo[x] = r
    return r
  return result
}

// 적용

let fib: (Int) -> Int = memoize{ fib, n in
    guard n > 1 else { return 0 }
    return fib(n-1) + fib(n-2)
}

기본적인 메모이제이션 함수

기본적으로 메모이제이션은 한 번 계산한 결과를 캐싱해두고 다시 똑같은 입력이 들어왔을 때는 계산을 수행하지 않고 그 값을 활용하는 것이다. 따라서 메모이제이션이 적용된 함수는 다음과 같은 로직으로 동작하면 된다.

  1. 캐시로 사용할 사전(Dictionary)을 하나 준비한다.[^2]
  2. 입력된 인자값 x 가 캐시의 키로 존재하는 경우, 연산 과정 없이 해당 키의 값을 꺼내어 리턴한다.
  3. 입력된 인자에 대해 계산된 캐시가 없는 경우, 실제 연산을 수행한 결과를 얻고
  4. 입력값과 계산 결과 값의 쌍을 캐시에 추가한 후
  5. 결과값을 리턴한다.

여기서 실제 연산을 처리할 함수를 일반화하면 다음과 같이 메모이제이션 함수를 만들 수 있다.

func simpleMemoization <T: Hashable, U> (_ f: @escaping (T) -> U) -> (T) -> U
{
  var memo = Dictionary<T, U>()
  return { (x: T) -> U in
    if let cachedResult = memo[x] { return x }
    let newResult = f(x)
    memo[x] = newResult
    return newResult
  }
}

이 함수는 (T) -> U 타입의 함수를 받아서 동일한 타입의 함수(클로저)를 리턴한다. 이 때 리턴되는 함수는 사전 객체 하나를 캡쳐하고 있고, 이 사전에 한 번 계산한 값들을 저장한다.

확인

그렇다면, 실제로 이 함수가 효과가 있는지를 살펴보자. 어떤 함수가 좋을까?  시간이 오래걸리면서 작성하기도 쉬운 (그리고 만만한) 소수 판별 함수가 좋겠다.  소수 판별 함수를 반복 적용하면서 계산에 드는 시간을 간이로 재어보자.

func isPrime(_ n: Int) -> Int
{
  guard n > 1 else { return false }
  for k in 2..<n {
    if n % k == 0 { return false }
  }
  return true
}

위는 정말 무책임한(?) 소수 판별함수이고, 다음은 반복과 시간 측정을 위한 함수들을 간단히 작성해본다.

import Foundation

func timeit(_ f: () -> ()){
  let begin = Date
  f()
  let elapsed = Date().timeIntervalSince(begin)
  print("time: \(elapsed * 1000)ms")
}

func repeater(_ count: Int, f: () -> ()) {
  guard count > 0 else { return }
  for _ in 0..<count { f() }
}

테스트 : 메모이제이션 없을 때

그리고 적당한 구간의 소수의 개수를 구하는 동작을 처리하도록 해보자. isPrime 이 메모아이즈 되지 않았다면 매 시행마다 거의 비슷한 시간이 소요될 것이다.

repeater(3){
  timeit{
    print(Array(1...30000).filter(isPrime).count)
  }
}

/*
3245
time: 1016.9049501419ms
3245
time: 999.333988692ms
3245
time: 1017.28498395699ms
*/

테스트: 메모이제이션 적용시

다음은 메모이제이션을 적용한 상태로 테스트하는 것이다.

let f = memoize(isPrime)
repeater(3){ timeit {
  print(Array(1...30000).filter(f).count)
}}

/*
3245
time: 1064.60899114609ms
3245
time: 42.5939559936523ms
3245
time: 44.7009801864624ms
*/

실행결과, 첫 번째 시행에서는 앞의 테스트와 거의 같은 시간이 걸리는 것이 확인된다. 그런데 2차와 3차의 테스트에서는 1차의 테스트에 비해서 1/200 정도의 시간만이 소요되었다. 왜냐면 1차의 테스트에서 30000개의 시행 결과가 모두 캐시되있고, 그 이후 시행에서는 모두 캐시된 결과를 그대로 사용하기 때문이다.

재귀 호출을 포함하는 함수의 메모이제이션

문제는 재귀호출을 하는 함수를 메모이제이션하게 되었을 때이다. 임의의 함수 f가 재귀호출을 포함한다고 가정하자. 이 함수 f는 수행중에 다시 f를 호출하는 형태의 코드를 포함하게 된다. 그리고 이 함수 f를 메모이제이션 한 함수 g를 생각해보자.

  • 함수 g가 인자 a를 가지고 호출된다.
  • 인자 a에 대한 리턴 값은 캐시된적이 없다고 하면 이 부분은 실제로 계산이 필요하다. 따라서 f(a)를 호출한다.
  • f는 가정한대로 재귀호출을 포함하며 이 때 a가 아닌 b를 인자로 사용한다.
  • 만약 b가 g에 의해서 이미 계산된 적이 있다 하더라도 한 번 f가 호출된 이후부터는 항상 f만 호출되며 g가 호출되지 않는 이상 이전에 계산된 파라미터 값이 중간부터 등장하더라도 캐시의 혜택을 받지 못한다.

이와 유사한 케이스를 만들어보자. 주어진 x 이하의 소수의 합을 구하는 함수를 재귀 형태로 만들어보겠다.

func sumOfPrimesUpto(_ n: Int) -> Int {
  guard n > 1 else { return 0 }
  return (isPrime(n) ? n : 0) + sumOfPrimeUpto(n - 1)
}

함수의 특성상 만약 여기에 3000을 대입했다고 하면, sumOfPrimeUpto(2999)가 분명히 호출되므로 그 다음 번에 다시 2999 이하의 소수의 합을 구하는 호출에는 수행시간이 매우 짧아져야 할 것이다.  하지만 여기서는 성공적으로 캐싱이 되지 않으리라는 것을 충분히 예측할 수 있고, 결과는 아래와 같다.

45675864
time: 979.550004005432ms
45675864
time: 985.236048698425ms

재귀호출에서도 메모아이징이 되도록 하기 위한 준비

그렇다면 어떻게 재귀호출하는 패턴의 함수가 메모아이징을 할 수 있을까? 바로 “캐시된 값이 없을 떄에 수행하는 계산” 자체에서 메모이제이션된 함수를 호출해야 하는 아이러니한 상황이 된다.  즉 이미 정의해버린 재귀호출 함수를, 메모이제이션 함수를 통해서 수정할 수는 없는 상황이된다. 따라서 자동 메모이제이션 함수는 클로저를 기반으로 작성되어야 한다는 결론에 다다를 수 있다. 그런데 문제가 있다.

다시 아래 코드를 보자. 만약 우리가 모종의  memoize 함수를 작성하는데 성공했다고 가정하자. 그렇다면 위에서 작성한 재귀꼴의 sumOfPrimes 를 다음과 같이 정의할 수 있게 된다.

let sumOfPrimes:(Int) -> Int = memoize{ n in 
    guard n > 1 else { return 0 }
    return (isPrime(n) ? n : 0) + sumOfPrimes(n-1)
}

그런데 이 구문은 실질적으로는 에러가 된다. 왜냐하면 세 번째 행에서 참조하고 있는 sumOfPrimes 클로저는 아직 선언되지 않은 (이 식은 현재 sumOfPrimes를 정의하기 위한 식의 우변이므로) 상태에서 참조되기 때문이다.

이 문제를 해결하기 위해서는 이 함수가 호출해야 할 실체가 사실은 메모아이즈를 적용받은 함수여야 한다는 조건이 필요하다. 그런데 지금 그 함수를 만드는 중이니 자신을 정의하는 중에 자신을 참조해야 한다는 아이러니가 발생했다….  어떻게 하면 좋을까?

그 제약 자체를 무시하자. 그러니까, 자기 자신을 정의하는 중에 호출하는 것이 아니라, 어떤 “메모아이즈된 함수를 인자로 받고, 이를 호출하는 것”이다.  뜬금없지만 -그리고 당연하지만-문법상으로는 아무런 문제가 되지 않는다. 따라서, 다음과 같이 메모아이즈된 함수를 인자로 받아서 호출하는 것으로 쓸 수는 있을 것이다.

let sumOfPrimes:(Int) -> Int = memoize{ memoizedFunc, n in 
  guard n > 1 else { return 0 }
  return (isPrime(n) ? n : 0) + memoizedFunc(n-1)
}

그리고 이 방법이 나쁘지 않은 것으로 판단된다면 그에 맞게 memoize 함수를 다시 고쳐쓰면 될 노릇이다.  memoizedFunc  라는 인자를 누가 주는가?에 대한 의문이 남아있기는 하지만(당연히 memoize 함수가 정해줘야 한다),  memoize 함수의 인자가 ((T)->U) -> (T) -> U 에서 함수 타입이 추가되어 (((T) -> U, T) -> U) -> (T) -> U가 되었다.  그럼 메모이제이션 함수는 아래와 같이 수정할 수 있을 것이다. 그리고 이 모양이 바로 WWDC의 바로 그 코드가 된다.

fun memoize <T: Hashable, U> (_ body: @escaping (((T) -> U, T) -> U)) -> (T) -> U
{
  var memo = [T:U]()
  var result: ((T) -> U)!
  result = { n in 
    if let cachedResult = memo[n] { return cachedResult }
    let newResult = body(result, n)
    memo[n] = newResult
    return newResult
  }
  return result
}

이제 마술의 안개를 걷어낼 차례이다.

  1.  memoize 함수는 어떤 클로저를 받은 후, 캐시에서 답을 찾고 답이 없는 경우만 해당 클로저를 호출하여 계산을 수행하는 함수를 리턴한다.
  2. 그런데 재귀등에 의해 중첩된 계산 내에서도 캐시를 이용하려면 원래 클로저가 캐시를 이용하도록 변형된 함수를 호출해야 한다.
  3. 그런데 원래의 클로저가 아직 만들어지지 않은 자기 자신의 메모이제이션 버전을 미리 아는 것은 말이 안된다.
  4. 따라서 원래의 재귀호출을 하던 클로저는 자신의 캐시화 버전을 인자로 받고, 자신을 재귀호출 하는 대신 인자로 받은 메모아이즈된 함수를 호출하는 식으로 변경할 수 있고,
  5. memoize 함수내에서 이 캐시되는 함수는 정의하기 전에 선언하여 (옵셔널 타입이면 가능하니까) 원래 함수의 인자로 전달될 수 있게 한다.

자 이제 최종적으로 테스트해보자. memoize 함수가 위와 같다면 올바른 메모이제이션 테스트는 아래와 같이, 이미 계산됐을 것으로 보이는 인자를 전달해주면 즉시 답을 낼 것이다.

let sumOfPrimesUpto: (Int) -> Int = memoize{ m, n in
  guard n > 1 else { return 0 }
  return (isPrime(n) ? n : 0) +  m(n-1)
}

timeit {
  print(sumOfPrimesUpto(10000)) // 이 계산 중에 sumOfPrimesUpto(9999)가 캐시될 것이다.
}
timeit {
  print(sumOfPrimesUpto(9999) // 위 계산에서 9999에 대한 계산을 마쳐서 캐시하고 있으므로, 거의 시간이 걸리지 않는 수준으로 찍힌다. 
}

 


  1. 당시 Swift 1에서는 인자로 받는 클로저는 기본적으로 탈출 가능했으나, Swift3부터는 클로저 인자의 기본 속성이 탈출 불가능하게끔 바뀌었다. 따라서 @escaping을 추가해주어야 한다. 

오일러 프로젝트 14

오일러 프로젝트 14 번 문제는 우박수에 관한 내용이다. 이 문제는 간단한 재귀함수와 메모이제이션을 통한 최적화 문제인데, 범위가 1~1백만으로 제법 크기 때문에 조금 더 깊은 고민이 필요하다. 또한 Swift에서는 단순한 메모이제이션 함수를 쓰는 경우, 재귀함수에서는 파이썬처럼 동작하지 못하기 때문에 특별한 형태의 메모이제이션 함수가 필요하다. 재귀함수를 위한 메모이제이션 함수를 어떻게 작성하는지에 대해서도 알아볼 것이다.

양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.

n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)

13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)

그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?

참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.

접근

우박수의 루트의 길이를 구하는 것은 재귀식으로 간단하게 표현할 수 있다.

Hn = \begin{cases} 1 , (\text{  if  } n = 1) \\ H_{n/2} + 1 (\text{  if  } n \mod 2 = 0) \\ H_{3 \cdot n + 1} + 1 (\text{  if  } n \mod 2 = 1) \end{cases}

따라서 다음과 같은 간단한 재귀함수로 우박수의 루트를 구할 수 있다.

def hail(n):
  if n < 2:
    return 1
  if n % 2 is 0:
    return hail(n//2) + 1
  return hail(n*3+1) + 1

하지만 백만 개의 수에 대해서 우박수 경로를 찾아야 하기 때문에 어느 정도 최적화가 필요하다. 만약 호출되는 과정에서 이전에 찾았던 값이 나온다면 재귀 체인을 따라가지 않고 즉시 끊고 나오도록 하여 속도를 높여보자. 일종의 메모이제이션이다. (그래도 100만 사이의 값을 검사하기 때문에 시간이 제법 걸리는 점은 어떨 수 없다.)

def solve():
  memo = {1:1}
  def hail(n):
    if n < 2: return 1
    if n in memo: return memo[n]
    m = n // 2 if n % 2 is 0 else n * 3 + 1
    r = hail(m) + 1
    memo[n] = r
    return r
  ## 풀이 시작
  limit = 100_0000
  ways = [(x, hail(x) for x in range(1, limit+1)]
  ans = max(ways, key=lambda x: x[1])
  print(ans[0])

%time solve()
## Wall time 3.21 s

Swift의 메모이제이션

Swift의 경우에는 최적화를 위해서 좀 이상한(?) 짓을 해야 한다.  먼저 hail 함수는 Swift에서 다음과 같이 작성가능하다.

func hail(_ n: Int) -> Int {
  if n < 2 { return 1 }
  let m = (n % 2 == 0) ? n / 2 : 3 * n + 1
  return hail(m) + 1
}

이 함수의 성능을 높이기 위해서 메모이제이션 할 수 있는 함수를 만들어보자. 이런 함수는 파이썬에서도 흔히 데코레이터로 만들었던 것이라 별로 어렵지 않다.

func memoize <T: Hashable, U> (_ f: @escaping (T) -> U) -> (T) -> U {
  var memo = [T:U]()
  return { n in
    if let r = memo[n] { return r }
    let r = f(n)
    memo[n] = r
    return r
  }
}

참쉽죠? 예를 들어서 임의의 정수의 소수 여부 판별이라든지 그런 경우는 함수를 이용해서 쉽게 메모이제이션 할 수 있다. 그런데 hail 함수는 좀 애매한 구석이 있다. 바로 함수 스스로가 재귀호출을 한다는 것이다. 따라서 다음과 같이 적용했을 때를 보자.

let memoized_hail = memoize(hail)
print(memoized_hail(13)) // 10
print(memoized_hail(10)) // 7

위 예에서 13에 대해 우박수 경로를 계산할 때, 10이 경로에 포함된다. 하지만 해당 시점에 10에 대한 값은 캐싱이 되지 않는다. memoized_hail(13)이 실행되는 경로를 추적해보자.

  1.  memoized_hail 에 인자값 13이 전달되어 호출된다.
  2. 참조된 사전 memo 에는 13에 대한 값이 없다. 그래서 hail(40) 이 호출된다. 그런데 memoized_hail 이 아닌 hail 은 메모이제이션을 적용받지 않는다. 따라서 이 함수가 최종 리턴하는 시점에는 키 ’13’에 대한 결과만 캐싱되며, 중간과정이 캐싱되지 않는다.

이를 어떻게 개선할까? 개선을 위해서는 메모이제이션을 적용받은 함수가 재귀호출을 할 때 원형이 아닌 메모이제이션을 적용받은 함수를 호출해야 한다. 이를 위해서 memoize 함수를 수정하기 전에 어떤식으로 호출되어야 할지를 먼저 생각해보자.

재귀 호출하는 함수의 메모이제이션

대략 다음과 같은 식으로 원형 내에서 메모이제이션이 적용된 함수를 호출하도록 해야 한다.

let memoized_hail: (Int) -> (Int) = memoize{  n in 
    if n < 2 { return 1 }
    let m = (n % 2 == 0) ? n / 2 : 3 * n + 1
    return memoized_hail(m)
}

그런데  이 코드는 문제가 있다. 코드의 클로저에서 memoized_hail 을 호출하는데, 이는 현재 정의하려는 클로저 선언의 좌변이며, 따라서 클로저가 생성되는 시점에서는 선언된 바가 없다. 따라서 최초 선언식의 우변에서 자신을 참조하기 때문에 에러가 된다. 어떻게 이를 해결할 수 있을까? 다음과 같이 클로저 표현을 수정해본다면?

let hail: (Int) -> Int = memoize{ memoized_hail, n in 
  ...
  return memoized_hail(m)

즉, 메모이제이션을 적용할 함수 원형이 인자로 메모이제이션이 적용된 클로저를 받아서 내부에서 참조하는 것이다. 어떻게 이걸 가능하게 할까? 이 클로저가 memoize() 함수 내부로 전달될 인자라는 점에 주목하자. 이 값 자체는 함수의 리턴값인 동시에, 리턴하기 전에 어떤식으로든 선언해두고 클로저 내부에서 참조되면 된다. 따라서 memoize() 함수는 다음과 같은 식으로 생겨야 할 것이다.  (완전한 코드가 아니라 와꾸를 보는 것이다.) 먼저 위에서 memoize 함수로 전달되는 클로저의 타입을 보면

  1.  메모이제이션이 적용된 함수 : (T: Hashable) -> U
  2. 함수의 인자가될 타입 : T

((T) -> U, T) 타입의 인자를 받고 다시 U타입의 값을 리턴하는 클로저를 인자로 받는 것이다. 그리고 이런 클로저를 인자로 받아서 (T) -> U 타입의 함수를 리턴해야 한다. 따라서 memoize() 함수의 원형은 아래와 같이 선언할 수 있다.

func memoize <T:Hashable, U> (_ body: @escaping ((T) -> U, T) -> U) -> (T) -> U
                                                  ^^^^^^^^^^ 클로저인자  ^^^^^^^^ 메모아이즈된 리턴타입
                                                ^^^^^^^^^^^^^^^^^^^ 클로저 전체 타입

그리고 그 이후를 살펴보자.

func memoize <T:Hashable, U> 
  (_ body: @escaping ((T) -> U, T) -> U)
  -> (T) -> U
{
  var memo = [T:U]()
  var result: ((T) -> U)! // IUO 타입으로 선언하여 초기값을 설정하지 않는다. 
  result = { n in 
    if let cachedResult = memo[n] { return n }
    let r = body(result, n) // body는 원형이다. 여기에 메모아이즈된 함수, 즉 리턴 결과를 넘겨준다.
    memo[n] = r
    return r
  }
  return result
}

조금의 최적화

그런데 역시 조금의 최적화가 필요하다. 만약 어떤 값 N에 대해서 우박수 경로를 구했다고 하자. 짝수인 경우는 그 절반에 해당하는 값의 우박수 경로보다 1칸 (즉 그 절반의 값으로 한 칸 더 이동한다)이 많다. 따라서 N을 2배, 4배, 8배하여 나오는 값에 대해서 +1, +2, +3 할 수 있는 것이다. 이렇게 특정 값에 대한 경로를 구했을 때, 그 수로 접근하는 2의 거듭제곱 배에 해당하는 값은 계산하지 않고 미리 만들어 둘 수 있다. 따라서 위의 함수에서 값을 캐싱하는 부분을 조금 조작하여 다음과 같이 작성해보자.

func memoize <T:Hashable, U> 
  (_ body: @escaping ((T) -> U, T) -> U)
  -> (T) -> U
{
  var memo = [T:U]()
  var result: ((T) -> U)! 
  result = { n in 
    if let cachedResult = memo[n] { return n }
    let r = body(result, n) 
    // 새로 계산된 결과를 메모하면서, 짝수상향 방향의 값도 미리 만든다.
    var (i, j) = (n, r)
    while i <= 100_0000, meme[i] == nil {
      memo[i] = j
      (i, j) = (i*2, j+1)
    }
    return r
  }
  return result
}

위 메모이제이션 함수를 이용해서 다음과 같이 계산할 수 있다.

let hail: (Int) -> Int = memoize{ memoized, n in 
  if n < 2 { return 1 }
  let m = (n % 2 == 0) ? n / 2 : n * 3 + 1
  return memoized(m) + 1
}
let ways:[(Int, Int)] = (1...100_0000).map{ ($0, hail($0)) }
let result = ways.reduce(ways[0]){ $0.1 > $1.1 ? $0 : $1 }
print(result.0)

그 외

사실 일반화한 메모이제이션 함수를 쓰지 않는다면 hail 함수 자체가 자신의 계산결과를 메모하도록 전역 사전 객체를 하나 써서 구현할 수도 있다.

var cache = [Int: Int]()
func hail(_ n: Int) -> Int {
  if n < 2 { return 1 }
  if let r = cache[n] { return r }
  let m = (n % 2 == 0) ? n / 2 : n * 3 + 1
  let r = hail(m) + 1
  var (i, j) = (n, r)
  while i <= 100_0000, cache[i] == nil {
    cache[i] = j
    (i, j) = (i*2, j+1)
  }
  return r
}

 

데코레이터를 통한 memoization

파이썬 데코레이터를 통한 memoization

피보나치 수열은 재귀 알고리듬의 대표적인 문제인데, 간단히 memoization을 통해서 성능을 개선하는 방법을 찾아보자. 테스트는 파이썬 3.4에서 진행했다.

def fib(n):
    if n in (1, 2):
        return 1
    return fib(n - 1) + fib(n - 2)

위 코드는 피보나치 수열의 정의를 그대로 따르는 코드이다. 이 코드를 사용하여 피보나치 수열의 64번째 항을 구하면… 얼마나 걸릴지는 모르겠다. 실행해놓고 이 글을 다 쓸 때까지도 결과가 나오지 않았다. fib(64)는 재귀 호출을 18,446,744,073,709,551,615 회나 해야하기 때문이다. (\( 2^{64} – 1 \)번을 계산해야 한다) 36번째 항을 계산하는데만해도 14초가 넘게 걸렸다. 이 알고리듬은 매우 간결하고 깔끔한 코드로 보이지만, 불필요한 중복 계산을 너무 많이 한다. 64번째 항을 구하기 위해서는 63번째와 62번째 항을 구하는데 그럼 62번째는 2번 계산된다. 즉 1에 가까워질수록 중복 계산횟수가 기하급수적으로 늘어나는 것이다.

데코레이터를 통한 memoization 더보기