메모이제이션: 같은 질문의 답을 한 번만 계산하기
메모이제이션은 함수가 이미 계산한 결과를 인자나 상태를 키로 저장하고, 같은 질문이 다시 오면 재사용하는 기법이다. 재귀로 문제를 표현하기 쉽지만 같은 부분문제가 반복될 때 효과가 크다. 단순히 모든 결과를 무작정 저장하는 것과는 다르다.
같은 상태로 다시 요청된 계산은 저장된 결과를 이용한다.
피보나치에서 중복이 생기는 구조
F(n)=F(n-1)+F(n-2)를 그대로 구현하면 F(5)를 구하는 여러 갈래에서 F(3),F(2)를 다시 계산한다. 캐시가 있으면 각 인자에 대한 계산은 한 번만 수행하고 이후 호출은 저장된 값을 읽는다.
def make_fibonacci():
cached_answers = {0: 0, 1: 1}
def fibonacci(index):
if index < 0:
raise ValueError("Index must be nonnegative")
if index in cached_answers:
return cached_answers[index]
computed = fibonacci(index - 1) + fibonacci(index - 2)
cached_answers[index] = computed
return computed
return fibonacci
fibonacci = make_fibonacci()
answer = fibonacci(10)
이 코드는 캐시를 함수 내부 환경에 보관한다. 답이 0일 수도 있으므로 “값이 참인가”가 아니라 키가 있는지 검사한다. 먼저 캐시 존재를 확인하지 않으면 계산을 끝낸 뒤 저장하더라도 반복 호출에서 재사용하지 못한다.
상태 키가 완전해야 한다
배낭 함수의 답이 물건 인덱스와 남은 용량에 모두 의존한다면 캐시 키에도 둘 다 있어야 한다. 남은 용량만 저장하면 서로 다른 물건 집합의 답을 섞는다. 전역 설정, 현재 시간, 외부 DB가 결과에 영향을 주는 함수는 인자만 같은 것으로 충분하지 않을 수 있다.
입력과 같은 환경에서 결과가 일정한 순수 함수는 캐싱하기 쉽다. 부수 효과가 있는 함수를 캐시하면 두 번째 실행의 효과가 생략될 수 있다. 파일 쓰기나 결제 같은 작업을 수치 계산처럼 저장해서는 안 된다.
피보나치의 서로 다른 상태는 n+1개이고 상태당 덧셈을 일정 비용으로 보면 시간 O(n), 캐시와 호출 스택 공간은 O(n)이다. 큰 정수는 자리 수가 늘어 덧셈 자체도 더 비싸므로 정확한 비트 복잡도는 별도다.
Top-down 메모이제이션은 실제 요청된 상태만 계산한다. Bottom-up 표 채우기는 의존 순서를 명시하고 재귀 스택을 없앨 수 있다. 같은 상태 전이를 표현하더라도 도달 상태의 수, 호출 비용, 메모리 재사용 가능성에 따라 장단점이 달라진다.
캐시는 메모리를 점유하고 오래된 결과를 유지할 수 있다. 상태 수가 너무 크면 제한된 캐시나 다른 알고리즘이 필요하다. 여러 스레드가 동시에 같은 상태를 계산하면 중복 실행이나 공유 상태 문제가 생길 수도 있다. 결과의 재사용이 정확한 조건과 캐시의 수명을 함께 정의해야 한다.