[TIL] 재귀 함수 결과 캐시 : functools.cache - 리트코드 338

https://leetcode.com/problems/counting-bits/

Counting Bits - LeetCode

해당 문제에 대한 풀이로

https://daelkdev.tistory.com/48

리트코드 - 338. Counting Bits

다음과 같은 풀이를 제시했다. 

 

functools.cache 데코레이터를 사용하여 재귀 함수의 결과를 캐시하는 방식으로 문제를 풀 수 있다.

이 방법은 특히 탑다운 접근법에서 유용하며, 함수의 결과를 캐시하여 재사용할 수 있다.

functools.cache는 Python 3.9 이상에서 사용할 수 있으며, functools.lru_cache(maxsize=None)의 간소화된 버전으로, 최대 크기 제한 없이 사용된다.

 

functools.cache의 동작 방식:

1. 캐시 초기화: 함수가 처음 호출될 때, functools.cache 데코레이터는 내부적으로 함수 인자와 반환값을 저장할 캐시를 초기화한다. 이 캐시는 파이썬의 dictionary와 유사한 구조를 가지고 있어서 빠른 검색과 삽입이 가능하다.
2. 인자 검사: 함수가 호출될 때마다, 데코레이터는 제공된 인자를 캐시에서 검색한다.
3. 캐시 활용: 제공된 인자에 대한 결과가 캐시에 이미 있으면, 데코레이터는 함수를 실행하지 않고 즉시 캐시된 값을 반환한다.
4. 캐시 업데이트: 제공된 인자에 대한 결과가 캐시에 없으면, 함수는 정상적으로 실행되고 반환값은 캐시에 저장된다. 이 값은 나중에 동일한 인자로 함수가 호출될 때 재사용된다.

from functools import cache

class Solution:
    def countBits(self, n: int) -> List[int]:
        @cache  # 결과를 캐시하는 데코레이터
        def count_bits_top_down(num):
            if num == 0:
                return 0
            return count_bits_top_down(num >> 1) + (num & 1)

        return [count_bits_top_down(i) for i in range(n + 1)]

 

@cache 데코레이터는 count_bits_top_down 함수의 호출 결과를 자동으로 저장하고, 동일한 입력에 대해 재호출 시 저장된 결과를 반환함으로써 함수의 중복 호출을 줄이고, 전체 계산 효율을 향상시킨다.