lru_cache

lru_cache는 Python의 functools 모듈에 있는 데코레이터로, 함수의 결과를 캐시하여 동일한 인풋에 대해 함수를 여러 번 호출하는 것을 피하는 데 사용됩니다. lru_cache는 “Least Recently Used (LRU)” 캐싱을 사용하여 메모리를 관리합니다. 이는 캐시가 가득 찼을 때 가장 오래된 항목을 삭제하는 방식입니다.

다음은 lru_cache에 대한 자세한 설명입니다:

기본 사용법

from functools import lru_cache

@lru_cache(maxsize=128)
def some_function(x):
    # 함수의 본문
    return x * x

• @lru_cache(maxsize=128): 이 데코레이터는 함수의 반환값을 캐시합니다. maxsize는 캐시할 최대 항목 수를 의미합니다. 기본값은 128입니다. maxsize=None으로 설정하면 캐시 크기에 제한이 없습니다.

작동 방식

lru_cache는 함수 호출 시 인자값을 키로 사용하고, 해당 함수의 반환값을 값으로 저장하는 사전을 유지합니다. 동일한 인자로 함수가 호출되면, 함수의 실제 실행을 건너뛰고 캐시에 저장된 값을 반환합니다. 이렇게 함으로써 함수 호출을 최적화할 수 있습니다.

예제

from functools import lru_cache

@lru_cache(maxsize=4)
def factorial(n):
    print(f"Calculating factorial({n})")
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(4))
print(factorial(5))  # 이 호출은 캐시된 값을 반환

캐시의 작동 방식

1. 첫 번째 호출: 함수가 처음 호출될 때, 결과가 계산되고 캐시에 저장됩니다.
2. 이후 동일한 인자로 호출: 캐시된 값이 반환되며, 함수는 실행되지 않습니다.
3. 캐시 크기 초과: 캐시가 가득 찼을 때 가장 오래 사용되지 않은 항목이 제거됩니다.

lru_cache의 주요 속성 및 메소드

• cache_info(): 캐시 사용 정보를 반환합니다.
• cache_clear(): 캐시를 비웁니다.

예제

@lru_cache(maxsize=4)
def compute(x):
    print(f"Computing {x}")
    return x * x

# 함수 호출
compute(2)  # 캐시되지 않음, 결과 계산
compute(3)  # 캐시되지 않음, 결과 계산
compute(4)  # 캐시되지 않음, 결과 계산
compute(2)  # 캐시됨, 결과 반환

print(compute.cache_info())  # CacheInfo(hits=1, misses=3, maxsize=4, currsize=3)

적용된 lru_cache의 코드 분석

이제 lru_cache가 적용된 원래 코드의 일부를 살펴보겠습니다:

from functools import lru_cache

def f(lim, mod):
    pat = [int(d) for d in reversed(str(lim))]
    @lru_cache(None)
    def fsb(n, rd, r, exact):
        if n == 0:
            return +(rd == 0 == r)
        if rd > n * 9: return 0
        n -= 1
        r = r * 10 % mod
        res = 0
        cd = pat[n] if exact else 10
        for d in range(min(cd, 9, rd) + 1):
            res += fsb(n, rd - d, (r + d) % mod, d >= cd)
        return res
    return fsb(len(pat), mod, 0, True)

fsb 함수에 적용된 lru_cache

• @lru_cache(None): 캐시 크기 제한 없이 모든 호출 결과를 저장합니다.
• 재귀 호출이 많은 경우 같은 인자로 여러 번 호출될 수 있기 때문에, lru_cache를 사용하면 중복 계산을 피하고 성능을 크게 향상시킬 수 있습니다.
• fsb 함수는 현재 자릿수와 나머지 값을 기준으로 계산을 수행하는데, 동일한 인자로 여러 번 호출될 가능성이 높습니다. lru_cache는 이러한 반복적인 계산을 방지합니다.

캐시가 적용되는 부분

재귀 함수 fsb는 다음과 같이 작동합니다:

1. fsb(n, rd, r, exact)가 호출될 때, 인자가 캐시에 있는지 확인합니다.
2. 캐시에 없으면, 함수가 실행되고 결과가 캐시에 저장됩니다.
3. 캐시에 있으면, 함수 실행을 건너뛰고 저장된 결과를 반환합니다.

이렇게 함으로써 재귀 호출로 인해 발생할 수 있는 중복 계산을 줄이고, 전체 함수의 실행 속도를 개선합니다.