오일러 프로젝트 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
}

 

꼬리와 꼬리재귀는 다르다. (Swift)

꼬리재귀

Natasha ElementTypehe Robot에 꼬리재귀에 대한 글이 올라오고 Digg에서 많은 digg을 얻었는데, 좀 이상해서 내용을 정리해본다. 링크한 글의 저자는 꼬리재귀와, 함수형 언어의 자료 구조인 리스트의 head, tail을 혼동하고 있는 듯 하다. 우선 꼬리재귀에 대해서 먼저 이야기하겠다. 꼬리 재귀는 재귀의 특별한 한 형태이다. 꼬리 재귀를 설명하기 전에 먼저 재귀(recursion)에 대해 알아보자.

재귀는 어떤 함수의 내부에서 스스로를 다시 호출하는 것을 말한다. 예를 들어서 1에서 10 까지의 자연수의 합을 구하는 과정을 재귀적인 처리를 통해서 구한다고 생각해보자.

  1. 계산은 1 + 2 + 3 + 4 + … + 10 으로 이루어지고, 편의상 이걸 +(1~10) 이라고 표현하기로 약속한다.
  2. 이 때 10까지의 합과 9까지의 합은 10만큼 차이난다, 즉 +(1~10)+(1~9) + 10 인 셈이다.
  3. +(1~n)+(1~(n-1)) + n 이 된다.

이 관계를 이용하면 1에서 n 까지의 자연수의 합을 구하는 함수를 다음과 같이 작성할 수 있다.

func sumUpto(n: Int) -> Int {
  guard n > 0 else { return 0 }
  return n + sumUpto(n: n - 1)
}

재귀함수의 기술적 한계

재귀함수는 1) 어디까지 계산할 것인가와 2) 한 단계의 계산과 다음 단계의 계산의 관계만을 생각하는 것으로 전체 계산 알고리듬을 매우 간결하게 정리할 수 있는 장점이 있다. 문제는 기술적인 한계때문에 재귀의 단계는 일정한 범위 이상으로 커질 수가 없다는 점이다. 그것은 재귀함수가 자신을 호출하는 것에 대해서 시스템은 부가적인 리소스를 더 많이 소모해야 한다는 것이다.

프로그램 흐름에서 함수의 호출은 메인 루틴에서 별도의 서브 루틴으로 흐름이 이행되는 것을 의미한다. 함수 내부로 실행 흐름이 들어가게 되면 함수 내부에는 전달된 인자와 함수 내부에서 선언된 지역 변수, 상수들이 존재하며 이것은 메인 루틴의 스코프와는 개별적인 값들이 된다. 또한 함수의 실행이 끝나면 실행 흐름은 메인 루틴에서 함수를 호출했던 위치로 돌아가야 하고, 이 때 실행 흐름이 액세스할 수 있는 변수들은 원래의 스코프의 값들이 되어야 한다. 이러한 리소스 제어를 위해서 함수가 호출되면 시스템은 메모리 영역의 끝단에 별도의 스택을 만들고 여기에 인자값과 함수의 지역 변수들을 복사한다. 그리고 함수의 실행이 끝나면 스택 영역을 파괴하여 리소스를 회수하는 식으로 동작한다.

함수의 재귀 호출은 함수는 하나지만, 함수가 매번 재귀 호출 될 때마다 별도의 독립적인 컨텍스트가 요구되기 때문에 재귀 호출을 반복하면 반복할 수록 스택영역을 계속해서 추가적으로 사용해 나가야 한다. 하지만 당연하게도 시스템의 메모리 자원은 한정되어 있기 때문에 스택 영역의 크기는 제한된다. 통상 몇 천~몇 만 단위의 횟수 내에서 스택이 중첩될 수 있고 (이것은 언어나 컴파일러마다 다르다.) 따라서 재귀의 깊이 역시 제한된다.

그런 이유에서 위의 sumUpto(n:) 함수는 몇 만 단위의 n 값에 대해서는 값을 계산하지 못하고 프로그램이 터지게 된다. 또한 시스템 입장에서 스택 영역을 할당하고 파괴하는 작업은 상당히 비싼 작업이다. 따라서 그만큼 성능 측면에서도 불리하다.

꼬리재귀 최적화

그런데 재귀 함수의 특정한 패턴 중에는 꼬리재귀(tail recursion)라는 것이 있다. 꼬리 재귀는 함수가 자신을 재귀호출한 결과를 바로 리턴하는 것을 의미한다. 꼬리 재귀가 특별한 이유는 다음과 같다.

  1. 꼬리 재귀에서 재귀의 결과는 그대로 리턴되므로 재귀의 결과에 대한 추가적인 연산이 불필요하다.
  2. 재귀 결과에 추가적인 연산이 불필요하다는 점은, 재귀 결과를 받은 시점에 해당 함수 내의 다른 컨텍스트를 더 이상 참조하지 않는다는 의미이다.
  3. 그렇다면 재귀 호출을 하려는 시점이 되면, 해당 레벨의 컨텍스트가 필요하지 않다는 것을 의미한다.
  4. 그런데 재귀 호출이 될 때 필요한 컨텍스트는 사실상 현재 컨텍스트와 동일하다.

즉 이 말은 꼬리 재귀 형태의 코드는 스택을 계속 생성할 필요 없이 함수의 첫 부분으로 되돌아 가는 것으로 실행 흐름을 대체할 수 있다는 뜻이 된다. 컴파일러 입장에서는 꼬리 재귀를 판단하는 것도 간단하다. 따라서 컴파일러는 이러한 꼬리 재귀 패턴을 간단하게 루프로 치환할 수 있고, 그렇게해서 재귀호출에 따르는 비용을 최소화하고 수행 속도도 높일 수 있다. 이것을 꼬리재귀 최적화라 한다. (현대의 대부분의 언어 구현체들은 꼬리재귀 최적화를 지원하고 있다.)

앞서 sumUpto(n:)은 재귀 호출 결과에 n을 더한 후에 리턴하기 때문에, 재귀 호출한 결과를 다시 가공하여 호출하고 있기에 꼬리 재귀가 아니라 하였다. 왜냐하면 재귀의 결과에 다른 값을 누적해서 더해야하기 때문이다. 이런 경우에는 주로 누적된 결과를 추가적인 파라미터로 넘기면 꼬리 재귀로 변경할 수 있다.

func sumUptoByTailRecursion(n: Int, _ acc: Int = 0) -> Int {
  guard n > 0 else { return acc }
  return sumUptoByTailRecursion(n: n - 1, acc + n) // 위로부터 누적하여 아래로 내려보낸다.
}

이렇게 변경된 형태는 꼬리 재귀이고, 이제 동일한 연산에 대해서 컴파일러가 최적화 할 수 있게 되었다.

Swift의 꼬리재귀 최적화

Swift 컴파일러는 꼬리 재귀 최적화를 수행하는 것으로 보이지만, 실제로는 최적화가 적용되지 않는 경우가 있다. 그것은 ARC때문에, 컴파일러가 최적화를 수행하는 이전 단계에서 메모리 관리 코드를 여기 저기에 삽입할 수 있기 때문이다. 따라서 소스 코드 원안에서 꼬리 재귀 형태였던 것이 ARC에 의해서 모양이 바뀌면서 꼬리 재귀 최적화의 혜택을 받지 못하는 경우가 발생한다.

이러한 문제를 피하기 위해서 트램폴린이라는 기법을 사용할 수 있다. (트램폴린 기법은 명시적으로 재귀를 루프로 바꿀 수 있기 때문에 최적화가 훨씬 쉬우며, 심지어 꼬리 재귀 최적화를 지원하는 다른 언어에서도 문법적으로 구현이 가능하다면 실제 꼬리 재귀보다 좋은 성능을 보인다.)

리스트의 꼬리에 관하여

나타샤가 헷갈려한 tail은 무엇일까? 그것은 리스트라는 함수형 언어에서의 주력 데이터 타입에서 사용되는 용어이다. 그러려면 “리스트”라는 타입에 대해서 살펴보아야겠다. 리스트는 배열처럼 여러 개의 개별 원소값이 일렬로 나열된 순서가 정해진 집합을 나타낼 때 사용한다. 그럼 “연결리스트(linked list)”하고 비슷한 것인가라고 생각할 수 있는데, 연결리스트와는 다르다. 연결리스트는 원소값을 감싸는 노드가 자신의 다음 노드에 대한 참조를 가지고 있는 것인데, 리스트는 다음 원소와의 연결이 “연산자”에 의해 고정된다.

하스켈에서 리스트를 만드는 빌딩 블럭으로는 두 개의 표현이 사용되는데,

  1. [ ] 은 빈 리스트를 의미한다.
  2.  : 연산자는 원소:리스트 의 형태로 어떤 리스트의 앞에 하나의 원소를 결합하는 작용을 한다.

위 표현을 활용하면 얼마든지 긴 리스트를 만들 수 있다. 예를 들어 [1] 이라는 1개 원소를 가지는 리스트는 빈 리스트에 1이라는 원소를 붙인 것이므로 1:[ ] 로 표현할 수 있다. 그럼 [1, 2]는? 1:(2:[])가 된다. 이런 식으로 1:(2:(3:(4:(5:[]))))와 같이 표현되는 것을 (으아 괄호지옥이다!!!) 문법적으로 쓰기 편하게 [1,2,3,4,5]라고 표현하는 것이다.

리스트는 결국 맨 앞의 원소 하나와 그걸 제외한 나머지 리스트가 붙어있는 재귀적인 꼴로 정의된다. 여기서 맨 앞의 원소를 head, 나머지를 tail이라고 한다. 그렇다면 tail에 대한 재귀적인 처리를 tail recursion이라고 할까? 아니다. 리스트의 본질은 그 자체가 재귀적인 데이터 타입이기 때문에 리스트에 대한 거의 대부분의 연산은 재귀적으로 이루어질 수 밖에 없다. (애초에 하스켈은 반복문이라는 제어구조가 없어서 반복 자체가 모두 재귀로 수행되어야 한다.) 리스트의 합을 구하는 sum 이라는 함수를 정의한다고 하면 하스켈에서는 다음과 같이 정의할 수 있다.

sum :: Integral a => [a] -> a
sum [] = 0
sum (x:xs) = x + (sum xs)

하스켈은 선언적인 함수이기 때문에 변수라는 개념이 없다. x = 1 과 같은 식으로 값에 이름을 붙일 수 있지만 이것은 엄밀하게 1 이라는 항등함수 x를 의미하는 것이다. 따라서 각 원소의 누적값을 더해나갈 임시 변수같은 것이 존재하지 않기 때문에 리스트에 대해서 루프를 통한 연속적인 연산은 불가능하며, 리스트의 재귀적인 성질에 의존하는 재귀적인 처리만이 가능하다. 그리고 (x + sum xs라는 표현 자체는 꼬리 재귀의 모양도 아니다.)

참고로 하스켈의 리스트는 Swift에서도 구현할 수 있다. 열거체는 indirect 변경자를 사용해서 재귀적으로 정의가능하기에 다음과 비슷하게 구성할 수 있다.

enum List<T> {
  case empty
  case list(T, List<T>)
}

// 빈 리스트
let anEmptyList: List<Int> = .empty
// [1]
let one: List<Int> = .list(1, .empty)
// [1,2,3,4,5]
let oneToFive: List<Int> = .list(1, .list(2, .list(3, .list(4, .list(5, .empty)))))

// 그리고 합계를 구하는 함수
func sum(list: List<Int>) -> Int {
  switch list {
  case .empty: return 0
  case .list(let x, let xs): x + sum(list:xs)
  }
}