사전 메모이제이션
패턴

메모이제이션

gabury1

메모이제이션은 함수가 한 번 계산한 답을 기억해 두는 일입니다. 두 번째부터는 계산을 다시 하지 않습니다. 기억해 둔 답을 그대로 돌려줍니다.

상세

메모이제이션은 함수 하나를 감싸기로 한 결정입니다. 감싼 쪽이 표를 하나 들고 있습니다. 표에는 이미 계산한 입력과 결과가 쌍으로 쌓입니다. 호출이 들어오면 인자로 표를 먼저 찾아봅니다. 표에 있으면 그 값을 돌려줍니다. 원래 함수는 부르지 않습니다. 없을 때만 원래 함수를 부릅니다. 나온 결과는 표에 넣은 뒤 돌려줍니다.

flowchart TD
    A[호출] --> B{인자가 표에 있나}
    B -->|있다| C[저장해 둔 결과를 돌려준다]
    B -->|없다| D[원래 함수를 부른다]
    D --> E[결과를 표에 넣는다]
    E --> C

Peter Norvig 의 1991년 논문은 이 말을 함수가 이전 계산의 결과를 자동으로 기억하게 만드는 과정이라고 풀어 적습니다. 같은 글이 기본 착상을 한 줄로 줄여 둡니다. 이전에 계산한 입력과 결과의 쌍을 표로 들고 있는 것뿐이라는 것입니다.

표를 무엇으로 만드느냐가 이 결정의 성질을 정합니다. Python 표준 라이브러리의 functools 문서는 @cache 를 함수 인자에 대한 딕셔너리 조회를 감싼 얇은 래퍼라고 적습니다. 딕셔너리를 쓰니 인자가 그대로 키가 됩니다. 같은 문서는 이것을 memoize 라고 부르기도 한다고 적고, lru_cache(maxsize=None) 과 같은 것을 돌려준다고 적습니다.

@lru_cache 는 함수를 memoizing callable 로 감싸는 데코레이터입니다. 가장 최근 호출을 maxsize 개까지 저장합니다. 여기 붙은 LRU(Least Recently Used, 가장 오래 안 쓰인 것부터 버리는 규칙)는 메모이제이션 자신의 일부가 아닙니다. 표가 꽉 찼을 때 무엇을 버릴지를 정하려고 그 자리에 끼워 둔 축출 규칙입니다.

언제 값이 있는지도 같은 문서가 적어 둡니다. 값이 비싸거나 입출력에 묶인 함수가 같은 인자로 주기적으로 불릴 때 시간을 아낄 수 있다고 적습니다. 감쌀 대상 함수가 먼저 있어야 성립하는 결정이라 같은 인자가 다시 오지 않으면 표는 쌓이기만 합니다.

대가

계산을 저장으로 바꾸는 거래입니다. 내주는 쪽은 메모리와 대상 함수의 자유입니다.

저장한 값이 쌓입니다. functools 문서는 maxsize 를 None 으로 두면 LRU 기능이 꺼지고 캐시가 한도 없이 자랄 수 있다고 적습니다. 상한을 걸면 이번에는 그 숫자를 정해야 합니다. 호출 조합이 몇 가지인지, 그중 몇 개를 들고 있을지는 아무도 정해 주지 않습니다.

캐시가 인자와 반환값을 붙잡습니다. 같은 문서는 캐시가 인자와 반환값에 대한 참조를 항목이 밀려나거나 캐시가 비워질 때까지 들고 있다고 적습니다. 메서드를 캐시하면 self 인스턴스 인자도 캐시에 들어갑니다. 그 객체는 캐시가 놓아줄 때까지 살아 있습니다.

인자에 제약이 붙습니다. 결과를 담는 데 딕셔너리를 쓰므로 함수에 넘기는 위치 인자와 키워드 인자가 전부 해시 가능해야 합니다. 같은 문서는 서로 다른 인자 패턴이 각자 캐시 항목을 가진 별개의 호출로 취급될 수 있다고 적습니다.

대상 함수도 값을 치릅니다. functools 문서는 LRU 캐시를 대체로 이전에 계산한 값을 다시 쓰고 싶을 때만 써야 한다고 적습니다. 이어서 부작용이 있는 함수, 호출마다 서로 다른 가변 객체를 만들어야 하는 함수, time() 이나 random() 같은 비순수 함수를 캐시하는 것은 말이 안 된다고 적습니다. 제너레이터와 비동기 함수가 그 가변 객체 쪽 예로 적혀 있습니다. 메모이제이션을 걸기로 한 순간 그 함수는 그런 일을 하지 않는 함수여야 합니다.

이름의 출처

Donald Michie 가 1968년에 이 이름의 뿌리를 놓았습니다. Nature 218권 19–22쪽에 실린 「Memo functions and machine learning」이 memo function 을 제안했고, memoization 이라는 말이 거기서 나왔습니다. 글은 https://www.nature.com/articles/218019a0 에 있습니다. 본문과 초록은 인증 페이지 뒤에 있습니다. 서지 사항은 Norvig 의 1991년 논문 참고문헌에서 확인됩니다.

귀속을 문장으로 못 박아 둔 것은 Peter Norvig 의 1991년 논문입니다. Computational Linguistics 17권 1호 91–98쪽에 실린 「Techniques for Automatic Memoization with Applications to Context-Free Parsing」의 첫 절이 memoization 이라는 말은 Donald Michie 가 1968년에 만들었다고 적습니다. 같은 논문의 참고문헌이 Michie 의 1968년 Nature 글을 서지 그대로 답니다. 공개본은 https://aclanthology.org/J91-1004.pdf 에 있습니다. 위키피디아의 Memoization 문서도 같은 귀속을 답니다.

Norvig 의 논문은 이 착상이 함수형 언어가 떠오르면서 근래에 더 널리 쓰이게 됐다고 적고, Field 와 Harrison 의 1988년 책이 한 장을 통째로 이 주제에 쓴다고 덧붙입니다.

예시

functools.lru_cache 로 감싼 PEP(Python Enhancement Proposal, 파이썬 개선 제안) 조회

Python
@lru_cache(maxsize=32)
def get_pep(num):
    'Retrieve text of a Python Enhancement Proposal'
    resource = f'https://peps.python.org/pep-{num:04d}'
    try:
        with urllib.request.urlopen(resource) as s:
            return s.read()
    except urllib.error.HTTPError:
        return 'Not Found'

maxsize=32 는 가장 최근 호출 32개까지 표에 담아 둔다는 뜻입니다. 데코레이터 한 줄 말고는 함수 본문에 캐시가 보이지 않습니다. 부르는 쪽 코드도 그대로입니다.

>>> for n in 8, 290, 308, 320, 8, 218, 320, 279, 289, 320, 9991:
...     pep = get_pep(n)
...     print(n, len(pep))

>>> get_pep.cache_info()
CacheInfo(hits=3, misses=8, maxsize=32, currsize=8)

열한 번 불렀습니다. misses 는 8입니다. 8과 320이 목록에 다시 나옵니다. 세 번은 표에서 바로 답이 나왔습니다. currsize 가 8이라 상한 32에는 닿지 않았습니다. 이 숫자들을 돌려주는 cache_info() 가 표가 실제로 얼마나 맞았는지 보는 자리입니다.

functools.lru_cache 로 감싼 피보나치

Python
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

>>> [fib(n) for n in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

>>> fib.cache_info()
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)

maxsize=None 이라 상한이 없습니다. 16개 값을 훑는 동안 misses 는 16이고 hits 가 28입니다. fib(n-1) 과 fib(n-2) 는 같은 인자를 거듭 부릅니다. 그중 계산이 실제로 돌아간 것은 인자마다 한 번뿐입니다. Python 공식 문서는 이 예제를 캐시로 다이나믹 프로그래밍 기법을 구현해 피보나치 수를 효율적으로 계산하는 예라고 적습니다.

경계

겹치는 하위 문제의 해를 표에 저장하는 구현은 다 메모이제이션인가. 아닙니다. 두 갈래가 겹쳐 보이는 자리부터 봅니다. Python 공식 문서는 lru_cache 를 씌운 재귀 피보나치를 캐시로 다이나믹 프로그래밍 기법을 구현한 것이라고 직접 적습니다. 위키피디아의 Dynamic programming 문서도 같은 자리를 짚습니다. 어떤 문제의 해를 하위 문제의 해로 재귀 정식화할 수 있고 그 하위 문제들이 겹치면, 하위 문제의 해를 표에 memoize 하거나 저장할 수 있다는 것입니다.

가르는 선은 방향입니다. 같은 문서는 재귀로 정식화한 다음 문제를 상향식으로 다시 정식화해 볼 수 있다고 적습니다. 하위 문제를 먼저 풀고 그 해로 더 큰 하위 문제의 해를 쌓아 올리는 쪽입니다. 그쪽은 함수 호출을 가로채지 않습니다. 표를 아래에서부터 채웁니다. 메모이제이션은 하향식 재귀를 그대로 두고 호출 앞에 표를 놓는 쪽입니다. 그래서 겹치는 하위 문제가 있는 문제를 메모이제이션으로 풀 수는 있지만, 상향식으로 표를 채우는 구현은 메모이제이션이 아닙니다.

관련 항목

이것과 헷갈리는 이웃

캐싱 · cache-aside · read-through · 다이나믹 프로그래밍

표를 이루는 자료구조

해시테이블 · 딕셔너리 · 인메모리 캐시 · 캐시 키

이것이 구현되거나 자주 쓰이는 언어

Python · 함수형 언어

캐시가 꽉 찼을 때 적용하는 축출 규칙

LRU · LFU · TTL · 축출 · 무효화

함수를 감싸는 데 쓰는 도구

데코레이터 · 클로저 · 고차 함수

감싸일 함수가 지켜야 하는 성질

순수 함수 · 부작용 · 참조 투명성 · 해시 가능

표 조회에서 나는 결과와 대응 기법

캐시 히트 · 캐시 미스 · 낡은 데이터 · 캐시 스탬피드 · request collapsing

이것이 감싸는 함수에 흔히 있는 재귀 성질

재귀 · 꼬리 재귀 · 겹치는 하위 문제

다른 이름: memoization · memoize · memo function