반응형

여러분들께 질문 두 가지 하겠습니다.

 

1. 37 + 19 는 얼마일까요?

답을 구하셨나요? 네. 답은 56 입니다. 아마 다들 암산으로 계산 후에 결과를 도출해 냈을 겁니다.

그럼 다음 질문입니다.

 

2. 37 + 19 는 얼마일까요?

2번의 질문은 1번과 동일합니다. 1번을 계산하신 분들이라면 2번 질문을 듣고 아마 곧바로 56을 대답할 수 있으실 겁니다. 하지만 2번의 답을 말할 때는 1번처럼 암산으로 계산하지 않으셨을 거예요. 왜냐하면 바로 직전에 이미 계산해둔 값을 기억하고 있었기 때문이죠.

 

이번 포스팅에서 살펴볼 메모이제이션 기법이란 바로 이러한 방식을 뜻합니다.

즉, 과거에 계산한 식을 불필요하게 다시 계산할 필요 없이 기억하고 있다가 필요할 때 재활용하는 것이지요.

사이드 이펙트가 없는 함수(또는 연산)는 입력이 같다면 몇 번을 호출하고 계산하여도 동일한 결과가 나옵니다. 우리는 저장된 값을 사용함으로써 다시 계산하는 것을 피하고 실행을 빠르게 만들 수 있습니다.

주의사항으로는, 메모이제이션은 부작용(Side Effect) 없는 순수함수에서만 사용되어야 한다는 것입니다.

 

알고리즘 기법인 다이나믹 프로그래밍(DP, Dynamic Programming)에서는 하위 문제를 해결하는 솔루션을 재귀적으로 사용해서 전체 문제를 해결합니다. 하지만 일반적인 재귀와 다르게 다이나믹 프로그래밍은 재귀를 사용할 때 하위 문제의 결과를 저장해 다시 사용합니다. 이 기법은 문제의 계산 복잡도를 지수형 복잡형에서 선형 복잡성으로 가지고 오기 때문에 코드를 이해하기 쉽게 유지하면서도 결과의 퍼포먼스를 크게 향상합니다.

 

아쉽게도 코틀린은 메모이제이션을 직접 지원해주지는 않습니다. 하지만 우리가 직접 만들 수는 있습니다.

우리는 메모이제이션을 2가지 방법으로 구현해볼 예정입니다. 하나는 Groovy 언어의 라이브러리가 제공해주는 솔루션과 유사하게 만들고, 다른 하나는 코틀린 델리게이션을 이용합니다.

 

본격적인 설명에 앞서 문제를 설정하겠습니다.

첫 번째 문제는 "피보나치 수열" 입니다. 피보나치 수열은 프로그래밍 예제에서 매우 많이 사용됩니다. 그 이유 중 하나는 이 문제가 매우 단순하면서 이해하기 좋고, 문제의 솔루션에만 집중할 수 있기 때문입니다. 이번에 예제로 사용한 이유도 동일합니다.

 

먼저 코틀린으로 피보나치 수를 찾는 단순한 재귀 함수를 구현해보겠습니다.

import kotlin.system.measureTimeMillis

fun fibonacci(n: Int): Long = when (n) {
  0, 1 -> 1L
  else -> fibonacci(n - 1) + fibonacci(n - 2)
}

fun main() {
  println(measureTimeMillis { fibonacci(40) }) // 약 500 밀리초
  println(measureTimeMillis { fibonacci(45) }) // 약 5.5 초
}

 

fibonacci() 함수는 주어진 값이 2보다 작을 경우 1을 리턴하고, 나머지 경우 2개의 재귀 함수 호출의 결과를 연산해서 결과를 리턴합니다.

위 코드에서 fibonacci(4) 를 호출하면 fibonacci(3) 과 fibonacci(2) 가 실행됩니다. 그리고 fibonacci(3) 이 실행될 때 다시 fibonacci(2) 를 호출하게 됩니다. n 이 작을 경우에는 실행이 빠르지만, n 이 증가함에 따라 실행 시간이 기하급수적으로 증가합니다.

 

위 예제에서도 보시다시피 n 이 40인 경우에 제 PC 기준으로 약 0.5초가 소요된 것에 비해 n 이 45 인 경우에는 약 11배 정도인 5.5 초가 걸렸습니다.

 

우리는 이전에 호출이 리턴한 결과를 기억해두도록 하면 연산 시간을 현저하게 줄일 수 있습니다. 메모이제이션 기법은 후속 호출에서 값이 이미 존재한다면 재귀 호출을 하지 않고 존재하는 값을 리턴하도록 하면 되는데요.

 

관련하여 먼저 Groovy 방식의 메모이제이션 기법을 살펴보겠습니다.

 

Groovy 방식의 메모이제이션

우리에겐 연산 결과를 저장할 수 있는 방법이 몇 가지 있습니다.

클래스를 만들고 필드나 프로퍼티에 데이터를 캐시하여 클래스의 함수가 그 캐시를 사용하도록 만들 수 있습니다.

하지만 이 방법을 사용하려면 클래스를 만들어야 하므로 이미 클래스를 만들고 있는 경우라면 선택해도 좋지만, 우리는 지금 단독 함수를 다루고 있기 때문에 클래스를 만들지 않는 방법으로 살펴보겠습니다.

 

메모이제이션을 다루기 위해서는 함수가 호출됐을 때 캐시를 체크해 데이터가 존재하는지 확인하고 데이터가 없을 경우 함수를 호출하도록 해야 합니다. 보통 이런 것은 단독 함수로는 구현할 수 없습니다. 이럴 땐 람다 표현식을 이용해 이런 한계를 해결할 수 있습니다.

 

Groovy 언어에서 메모이제이션은 라이브러리 내부에 구현되어 있습니다. Groovy 에서는 아무 람다 표현 식에서나 memoize() 함수를 호출할 수 있고, memoize() 함수는 저장된 람다를 리턴합니다. 코틀린에서 이와 유사한 접근으로 적용해보겠습니다.

 

fun <T, R> ((T) -> R).memoize(): ((T) -> R) {
  val original = this
  val cache = mutableMapOf<T, R>()
  return { n: T -> cache.getOrPut(n) { original(n) } }
}

위 코드는 코틀린에 익숙하지 않은 분들께는 다소 어렵게 느껴질 수 있습니다. 코틀린적인 요소가 많이 가미되었기 때문인데요. 위 코드를 이해하기 위해서는 함수가 일급 객체라는 점과 제네릭, 확장 함수에 대한 선행 지식이 필요합니다.

 

다시 본론으로 와서, 첫 번째 라인에서 우리는 memoize() 메소드를 제네릭 람다 표현식에 주입(Inject) 했습니다. 제네릭 람다 표현식은 T 타입의 파라미터를 받고, R 타입을 리턴합니다. memoize() 함수의 리턴 타입은 memoize() 가 주입된 메소드의 타입과 같은 타입의 람다 표현식입니다. 다시 말하자면 함수에서 memoize() 를 호출한 결과는 함수의 동일한 시그니처를 가진 함수입니다.

 

memoize() 함수에서 우리는 this 를 로컬 변수 original 에 할당해서 오리지날 함수의 레퍼런스를 저장할 수 있습니다. 그리고 비어있는 cache 를 초기화합니다. 마지막으로 T 타입의 파라미터를 받고, R 타입의 결과를 리턴하는 람다를 리턴합니다. 그리고 리턴된 함수는 결과가 존재하는지 보기 위해 캐시를 확인하고 캐시에 결과가 없다면 연산을 해서 결과를 만들고 리턴하기 전에 저장합니다. 이미 결과가 존재한다면 연산을 건너뛰고 저장된 값을 리턴합니다.

 

memoize() 함수를 사용해서 피보나치수의 연산을 수행해보겠습니다.

lateinit var fib: (Int) -> (Long)
fun main() {
  fib = { n: Int ->
    when (n) {
      0, 1 -> 1L
      else -> fib(n - 1) + fib(n - 2)
    }
  }.memoize()

  println(measureTimeMillis { fib(40) })  // 약 0 밀리초
  println(measureTimeMillis { fib(45) })  // 약 0 밀리초
  println(measureTimeMillis { fib(500) })  // 약 1 밀리초
}

결과는 충격적입니다. 앞서 메모이제이션을 적용하지 않았던 방식에서는 4초 이상 걸리던 연산이 1 밀리초 미만에서 끝나버리고, 입력이 500인 실행은 1 밀리초 밖에 안 걸렸습니다.

 

여기 작성한 memoize() 함수는 파라미터 하나만 사용하는 모든 함수에서 사용이 가능합니다.

하지만 이 방식에는 단점이 하나 있는데요.

이 방식을 사용하기 위해서는 fib 를 먼저 정의하고, 그 후에 fib 에 람다 표현식을 할당해야 합니다.

그렇기 때문에 lateinit var 으로 지연 초기화를 할 수밖에 없었습니다. 만약 var 로 선언하면서 동시에 초기화를 하려 한다면 fib(n - 1), fib(n - 2) 부분에서 컴파일 에러가 발생할 것입니다.

 

그렇다면 선언과 동시에 초기화를 할 수는 없을까요? 이를 해결하기 위한 방법으로 코틀린은 델리게이트를 가지고 있습니다. 델리게이션을 사용하면 솔루션이 어떻게 바뀔지 살펴보도록 하겠습니다.

 

코틀린 델리게이션을 잘 모르시는 분들은 예전에 제가 작성한 델리게이션 포스트를 먼저 읽고 오실 것을 권장합니다.

[Kotlin] Kotlin Delegation 이해하기① - 왜 상속보다 추천되는 걸까?

 

델리게이트를 이용한 메모이제이션

이전 섹션에서 fib = { ... }.memoize() 코드는 변수 fib 를 메모이즈된 람다 표현식으로 변경했습니다. 하지만 코틀린에는 프로퍼티와 지역변수의 접근을 인터셉트할 수 있는 기능이 있습니다. 우리는 델리게이트를 이용해서 프로퍼티와 지역변수에 접근할 수 있습니다.

 

이제는 fib 에 var 대신 val 을 사용할 예정입니다. 우리는 fib 에 할당을 단 한 번만 할 것입니다. 그렇기 때문에 델리게이트에 setValue() 는 필요 없고, getValue() 메소드만 있으면 됩니다.

 

이제 델리게이트를 만들어보겠습니다.

import kotlin.reflect.*

class Memoize<T, R>(val func: (T) -> R) {
  private val cache = mutableMapOf<T, R>()
  operator fun getValue(thisRef: Any?, property: KProperty<*>) = { n: T ->
    cache.getOrPut(n) { func(n) }
  }
}

위 코드에서 델리게이트는 내부적으로 캐시를 가지고 있고, 오리지날 함수는 func 프로퍼티로 가지고 있습니다. 그리고 getValue() 함수가 값이 캐시에 없을 경우 오리지날 함수를 실행시키는 람다 표현식을 리턴합니다.

 

델리게이션을 활용한 솔루션과 Groovy 방식의 솔루션은 유사한 컨셉을 사용합니다. 하지만 이번 솔루션엔 이전 솔루션에 비해서 fib 함수가 아주 다르게 적용되었습니다. fib 함수를 만들 때 델리게이션을 적용해보겠습니다.

 

val fib: (Int) -> Long by Memoize {n: Int ->
  when (n) {
    0, 1 -> 1L
    else -> fib(n - 1) + fib(n - 2)
  }
}

 

메모이제이션은 델리게이트를 사용할 때 훨씬 깔끔합니다. 이제는 Groovy 방식과는 다르게, 선언과 초기화를 동시에 할 수 있게 됩니다. 그 이유는 내부적으로 우리가 fib 변수에 직접 접근하는 게 아니고 위임을 통해서 접근하기 때문입니다.

 

이전 버전만큼의 성능이 좋은지 확인하기 위해서 이번 버전의 fib() 도 실행해보겠습니다.

fun main() {
    println(measureTimeMillis { fib(40) })  // 약 0 밀리초
    println(measureTimeMillis { fib(45) })  // 약 0 밀리초
    println(measureTimeMillis { fib(500) })  // 약 1 밀리초
}

실행 결과. Groovy 방식의 메모이제이션 솔루션과 비슷한 결과를 얻는 것을 확인했습니다.

 

지금까지 메모이제이션을 생성하는 두 가지 방법을 보았습니다. 둘 다 비슷한 방식으로 구현이 가능하지만, Groovy 방식의 함수 호출 솔루션에 비해서 델리게이션 솔루션이 더 깔끔하고 적은 노력으로 메모이제이션을 적용할 수 있었습니다.

 

정리

아쉽게도 크기가 큰 문제에서는 재귀를 사용할 수 없습니다. 스택 오버플로우 에러가 발생할 가능성이 있기 때문입니다. 코틀린은 tailrec 을 제공해서 재귀 호출을 사용하는 코드에 꼬리 재귀 최적화를 제공해줍니다. 코틀린이 내부적으로 재귀를 반복으로 바꿔주어 개발자는 스택 오버플로우를 걱정할 필요 없이 재귀의 힘을 사용할 수 있습니다.

 

그리고 코틀린이 메모이제이션 함수를 직접 제공해주진 않지만, 연산 결과를 기억하거나 캐싱하는 기능을 만들 수 있습니다. 이런 접근방법을 사용해 다이나믹 프로그래밍이라고 불리는 알고리즘 기법으로 프로그램의 연산 시간을 크게 줄일 수 있습니다. Groovy 방식으로 함수 레벨에서 메모이제이션을 구하는 방법과 델리게이트 기반으로 메모이제이션을 구현하는 방법도 확인했습니다.

반응형
반응형