데코레이터 + @lru_cache 데코레이터를 활용한 DP 캐싱

데코레이터 개념

Decorators provide a simple syntax for calling higher-order functions.
By definition, a decorator is a function that takes another function and extends the behavior of the latter function without explicitly modifying it.
출저 : https://realpython.com/primer-on-python-decorators/

함수 A를 실행하기 전, 앞 뒤로 time.time()을 실행해서 실행 시간을 재고 싶을 때가 있다.
이때, A를 인자로 받아서 앞 뒤로 time.time() 처리를 해주는 다른 wrapper 함수 B를 만들 수 있지 않을까? 

* 함수를 인자로 받거나 함수를 리턴하는 함수 - higher-order function 

 

파이썬은 B를 '데코레이터'라는 이름의 기능으로 지원한다!

 

https://bluese05.tistory.com/30 

python decorator (데코레이터) 어렵지 않아요.mhtml

4.45MB

 

---

Python에서 함수의 반환값을 알아서 캐싱해주는 데코레이터가 있다는 사실을 새로 알게 됨.

바로 @lru_cache !!

 

https://leetcode.com/problems/minimum-skips-to-arrive-at-meeting-on-time/discuss/1239980/Python-7-lines-dp-%2B-2liner-explained

 

Top-down DP에 @Iru_cache 데코레이터를 써서 캐싱을 적용하였고,

generator 식에 next 함수를 써서 조건을 만족하는 가장 작은 k값을 뽑아낸 모습이다. 

정말 아름답다.

class Solution:
    def minSkips(self, dist, S, H):
        @lru_cache(None)
        def dp(i, k):
            if k < 0: return float("inf")
            if i < 0: return 0
            return dist[i] + min(dp(i-1, k-1), (dp(i-1, k) + S - 1)//S*S)
        
        if sum(dist) > S*H: return -1
        n = len(dist)
        return next(k for k in range(n+1) if dp(n - 1, k) <= H*S)

 

@Iru_cache는 간단한 DP에 충분히 써먹을 수 있을 것 같다. 

Memo 체크하는 코드를 줄여서 훨씬 깔끔해질 것 같고.

 

공식 reference도 있다.

https://docs.python.org/ko/3/library/functools.html

 

 

---

단점 : 캐시 사이즈가 좀 커지면 속도가 매우매우 느려지는 듯 하다 (Cache hit? miss? 원리를 한번 봐야할 것 같은데)

N = 1000, O(N^2) 수준의 memoization도 엄청 오래 걸리는 듯. 참고하기

(LeetCode 26 M-1690. Stone Game VII)