답변.

질문 배경:

메모이제이션은 동일한 인수로 동일한 함수를 여러 번 호출할 때 함수형 프로그래밍, 재귀 계산 및 동적 프로그래밍에서 널리 적용되는 최적화 기술입니다. 파이썬에서는 functools.lru_cache 데코레이터와 계산 결과 캐싱 패턴이 등장하면서 일반화되었습니다.

문제:

캐싱 없이 피보나치 수를 계산하는 재귀 함수는 매우 느리게 작동합니다. 각 인수에 대해 많은 계산이 반복되어 호출 수가 기하급수적으로 증가합니다.

해결책:

메모이제이션은 이미 계산된 값을 저장(예: 사전에서)하여 필요할 때 다시 사용할 수 있도록 합니다:

수동 구현 예:

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib(n-1) + fib(n-2)
    memo[n] = result
    return result

파이썬 3.2부터는 데코레이터를 사용하여 간단하게 사용할 수 있습니다:

from functools import lru_cache

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

주요 특징:

함수의 로직을 변경하지 않고 재귀적이거나 계산 비용이 큰 함수를 가속화할 수 있습니다.
구현은 수동(사전을 사용)과 자동(lru_cache 사용)으로 나뉩니다.
변경 가능한 인수에 대해 주의해야 하며, lru_cache는 해시 가능(불변) 인수에서만 작동합니다.

트릭 질문.

변경 가능한 인수(예: 리스트)로 함수를 메모이제이션 할 수 있습니까?

아니요, lru_cache는 모든 인수가 해시 가능(불변)해야 하며, 그렇지 않으면 TypeError가 발생합니다.

from functools import lru_cache

@lru_cache
# def f(a): return a[0]  # TypeError: unhashable type: 'list'

메모이제이션된 값은 자동으로 삭제됩니까?

예, maxsize가 설정된 경우 한계를 초과한 값은 삭제됩니다(최소 최근 사용). 무한 캐시(maxsize=None)는 메모리 오버플로우를 초래할 수 있습니다.

메모이제이션된 함수가 새로운 인수로 자신을 호출하면 어떻게 됩니까?

메모이제이션은 여전히 작동합니다. 각 고유한 인수 집합에 대해 결과는 한 번만 계산되고 캐시됩니다.

일반적인 오류 및 안티 패턴

캐시 제한 없이 메모이제이션 사용 및 메모리 오버플로우
변경 가능한 인수로 함수를 메모이제이션하려고 시도
더 이상 필요하지 않을 때 캐시를 정리하는 것을 잊음

실생활 예

부정적 사례

크기 제한 없이 자체 캐시를 작성합니다:

cache = {}
def foo(x):
    if x not in cache:
        cache[x] = long_heavy_computation(x)
    return cache[x]

시간이 지나면서 프로그램은 기가바이트의 메모리를 사용합니다.

장점:

반복 호출에 대해 빠르게 작동합니다.

단점:

메모리 성장 무제한
Out of Memory 가능성

긍정적 사례

maxsize를 사용하여 lru_cache를 사용합니다:

from functools import lru_cache

@lru_cache(maxsize=1000)
def foo(x):
    return long_heavy_computation(x)