4장, 열심히보다는 현명하게

2022.01.23

4.1 메모이제이션

  • 메모이제이션이란 단어는 영국의 인공지능 연구학자인 도널드 미치(Donald Michie)가 연속해서 사용되는 연산 값을 함수 레벨에서 캐시하는 것을 지칭하는 것으로 처음 사용하였다.
  • 함수 캐싱은 전형적인 컴퓨터과학의 트레이드오프이다.
  • 캐싱 방법이 제대로 작동하려면 함수가 순수해야 한다.

4.1.1 캐싱

  • 캐싱은 흔한 요구사항이다. (동시에 찾기 어려운 오류의 근원이기도 하다)

합산 결과를 캐시하기

  • 이미 수행된 결과를 재사용하는 것이 코드를 효율적으로 만드는 한 방법이다.
  • 아래처럼 계산 결과를 저장할 캐시를 만들어야 한다.
class ClassifierCachedSum {
  private sumCache = [:]

  def sumOfFactors(number) {
    if (!sumCache.containsKey[number]) {
      sumCache[number] = factorsOf(number).sum()
    }
    return sumCache[number]
  }
}
버전결과(작을수록 좋음)
최적화하지 않은 예577ms
최적화하지 않은 예(두 번째 실행)280ms
합을 캐시한 예600ms
합을 캐시한 예(두 번째 실행)50ms
  • 합을 캐시한 예가 최적화하지 않은 예보다 시간이 조금 더 걸리는 것은 캐시를 만드는데 시간이 조금 더 걸렸다고 볼 수 있다.
    • 또한, 최적화하지 않은 예의 첫번째와 두번째 시도의 시간 차이는 가비지 컬렉션과 같은 환경적 요인에 의한 것이다.
  • 합을 캐시한 두번째 시도는 속도가 엄청 빨라진 것을 확인할 수 있는데, 이것이 외부 캐싱의 예이다.
  • 캐시된 결과는 호출하는 모든 코드가 사용하게 되며, 그래서 두 번째 시도는 무척 빨라진다.
  • 합을 캐시하면 성능이 엄청나게 좋아지지만 거기엔 트레이드오프가 있다.
  • 내부 캐시가 상태를 표시하기 때문에 캐시를 사용하는 모든 메서드를 인스턴스 메서드로 만들어야 한다.
  • 또한, 개발자가 캐시 변수를 제어해야 한다.

전부 다 캐시하기

  • 합을 캐싱해서 코드가 많이 빨라졌으니, 모든 중간 결과를 캐시하면 어떤 결과가 나올까?
버전결과(작을수록 좋음)
최적화하지 않은 예577ms
최적화하지 않은 예(두 번째 실행)280ms
합을 캐시한 예600ms
합을 캐시한 예(두 번째 실행)50ms
전부 다 캐시한 예411ms
전부 다 캐시한 예(두 번째 실행)38ms
  • 결과는 좋지만 이 방법은 규모를 늘리기가 어렵다.
  • Out of memory를 야기할 수 있다.
  • 캐싱 코드를 작성하는 개발자는 정확함과 실행 조건도 신경써야 한다.
    • 코드 내의 상태와 그 의미를 개발자가 항상 관리해야만 한다.
  • 수많은 언어가 이미 메모이제이션과 같은 메커니즘을 사용하여 이러한 제약을 극복해냈다.

4.1.2 메모이제이션의 첨가

  • 함수형 프로그래밍은 런타임에 재사용 가능한 메커니즘을 만들어서 움직이는 부분을 최소화하는데 주력하낟.
  • 메모이제이션은 프로그래밍 언어에 내장되어 반복되는 함수의 리턴 값을 자동으로 캐싱해주는 기능이다.
  • 함수를 메모아이즈하는 것은 메타함수를 적용하는 것이라고 할 수 있다.
    • 리턴 값이 아니라 함수에 어떤 것을 적용하는 것이다.
class ClassifierMemoizedSum {
  // ...
  def static sumFactors = { number ->
    factorsOf(number).inject(0, {i, j -> i + j})
  }
  def static sumOfFactors = sumFactors.memoize()
  // ...
}

그루비의 메모이제이션 메서드들

메서드설명
memoise()캐싱 형태의 클로저를 만든다
memoizeAtMost()최대 크기를 가지는 캐싱 형태의 클로저를 만든다
memoizeAtLeast()최소 크기를 가지고 크기를 자동 조정하는 캐싱 형태의 클로저를 만든다
memoizeBetween()캐시 크기를 최대치와 최소치 사이에서 자동 조정하는 캐싱 형태의 클로저를 만든다
  • 명령형 버전에서는 개발자가 코드를 소유하고 책임을 진다.
  • 함수형 언어는 가끔 특별한 상황을 위한 변형된 함수나 매개변수를 도입할 때도 있지만, 주로 표준에 맞는 구조에 적합한 일반적인 도구를 만든다.
  • 함수가 언어의 기초적인 요소이기 때문에, 그 레벨에서 최적화가 된 고급 기능을 공짜로 얻는 셈이다.
  • 언어가 캐싱을 더 효율적으로 지원하기도 하지만, 개발자는 그런 책임을 런타임에게 양도하고 더 높은 수준에서 추상화된 문제들에 고민해야 한다.
  • 함수형 프로그래밍은 움직이는 부분을 제거하여 개발자가 중요한 문제를 푸는데 집중할 수 있게 해준다.
  • 메모아이즈된 함수는 부수효과가 없어야 하고, 외부 정보에 절대로 의존하지 말아야 한다.

개발자가 스칼라나 클로저 같은 함수형 언어에 관심이 없다 해도, 언어가 진화하면서 함수형 프로그래밍은 자연스럽게 그들의 세계로 발을 들여놓을 것이다.

4.2 게으름

  • 표현의 평가를 가능한 최대한 늦추는 기법인 게으른 평가는 함수형 프로그래밍 언어에서 많이 볼 수 있는 기능이다.
  • 게으른 컬렉션은 요소들을 한꺼번에 미리 연산하는 것이 아니라, 필요에 따라 하나씩 전달해준다.
  • 얻는 이점은 아래와 같다.
    • 시간이 많이 걸리는 연산을 반드시 필요할 때 까지 미룰 수 있게 된다.
    • 요청이 계속되는 한 요소를 계속 전달하는 무한 컬렉션을 만들 수 있다.
    • 맵이나 필터 같은 함수형 개념을 게으르게 사용하면 효율이 높은 코드를 만들 수 있다.
print length([2+1, 3*2, 1/0. 5-4])
  • 이 코드를 실행해보면 프로그래밍 언어가 엄격한지(strict) 혹은 관대한지(nonstrict, 게으른지)에 따라 결과가 다를 것이다.
    • 엄격한 언어에서는 세번째 요소 때문에 DivByZero 예외가 나고, 관대한 언어에서는 결과가 4로 나올 것이다.

4.2.5 게으름의 이점

  • 게으른 목록은 몇가지 이점이 있다.
    • 무한수열을 만들 수 있다. 필요할 때까지 값을 평가하지 않아도 되기 때문에, 게으른 컬렉션을 사용하면 무한수열을 모델링할 수 있다.
    • 저장시 크기가 줄어든다. 컬렉션 전부를 유지하지 않고 순차적으로 다음 값을 유도할 수 있으니 저장소와 실행 속도를 맞바꿀 수 있다.
    • 런타임이 좀 더 효율적인 코드를 만들 수 있다.

4.2.6 게으른 필드 초기화

  • 비용이 큰 초기화를 게으르게 만드는 데 좋은 기능을 제공해주는 언어가 있다. ( 스칼라, 그루비 )
lazy var x = timeConsumingAndOrSizeableComputation()
class Person {
  @Lazy pets = ['Cat', 'Dog', 'Bird']
}