Home » memoization

memoization

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

하스켈의 메모이제이션 하스켈의 함수는 순수함수이고, 이는 입력이 같다면 항상 같은 결과가 리턴되는 것을 보장한다. 이는 어떤 임의의 함수 f와 그 인자 x가 있을 때 최초 f(x)가 계산되고 나면 그 이후에 f(x)가 필요한 경우에 불필요한 반복 계산이 필요하지 않은 것 처럼 들린다. (왜냐면 f(x)는 이미 이전에 계산되어 값으로 축약되었고, 그 사이에 어떤 일이 있었든지 간에 같은 인자에 대해서는 하스켈의 함수는 같은 결과를 내놓을 것이기 때문이다.) 하지만 이것은 다른 문제이다. 이는 하스켈이 기본적으로 모든 함수 적용 연산에 대해 그 결과를 캐싱한다는 이야기인데,… 더 보기 »하스켈에서 메모이제이션 구현하기

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

시간이 오래 걸릴 수 있는 비싼 연산 작업이 있고, 이러한 연산을 반복해서 수행해야 하는 상황이 있을 때, 가장 손쉬운 성능 개선 방법은 연산 결과를 캐싱하는 것이다. 연산을 수행하는 함수가 입력이 같을 때 출력이 같은 것이 보장되는 순수한 함수라면, 재계산을 수행하는 것보다 캐시된 내용을 읽어와서 사용하는 것이 훨씬 빠른 것은 자명한 사실이다. 메모이제이션(Memoization) 실제로 이런 종류의 문제는 제법 흔하고 실제로도 계산 결과를 캐시해서 사용하는 것은 좋은 해결책 중 하나이다. 어떤 문제가 더 작은 부분문제들로 나뉠 수 있고, 전체 문제는 작은 부분문제들의… 더 보기 »WWDC의 자동 메모이제이션 코드 분석

오일러 프로젝트 14

오일러 프로젝트 14 번 문제는 우박수에 관한 내용이다. 이 문제는 간단한 재귀함수와 메모이제이션을 통한 최적화 문제인데, 범위가 1~1백만으로 제법 크기 때문에 조금 더 깊은 고민이 필요하다. 또한 Swift에서는 단순한 메모이제이션 함수를 쓰는 경우, 재귀함수에서는 파이썬처럼 동작하지 못하기 때문에 특별한 형태의 메모이제이션 함수가 필요하다. 재귀함수를 위한 메모이제이션 함수를 어떻게 작성하는지에 대해서도 알아볼 것이다. 양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다. n → n / 2 (n이 짝수일 때) n → 3 n + 1 (n이 홀수일 때) 13에… 더 보기 »오일러 프로젝트 14

데코레이터를 통한 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