콘텐츠로 건너뛰기
Home » memoization

memoization

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

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

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

소수 판별이나 소인수분해와 같이 시간이 오래 소요될 수 있는 연산량이 큰 작업이 있고, 이 연산을 반복해서 수행할 일이 많을 때 성능을 개선할 수 있는 가장 손쉬운 방법으로는 연산 결과를 캐싱하는 것이 있을 수 있다. 즉 함수의 외부에 사전과 같은 캐시 저장소를 하나 준비해 두고 입력값을 키로 캐시값을 감사하여 있으면 사용, 없으면 원래 함수 코드를 실행하여 캐시값을 기록하고 리턴하는 방식을 사용하는 것이다. 이는 일일이 그러한 함수를 작성하기 보다는 클로저를 인자로 받아 클로저를 리턴하는 함수를 사용하여 조금 더 유연하게 사용할 수 있다.… 더 보기 »WWDC의 자동 메모이제이션 코드 분석

오일러 프로젝트 14

우박수 양의 정수 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이라고 하며, 이런… 더 보기 »오일러 프로젝트 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