Functools

lru_cache

• 做LRU cache的裝飾器
• 寫Dynamic Programming的利器
• 被裝飾的function，在輸入相同的params時它的return value會被cache起來
  • 使用dict作為cache，所以parameter用的value需要能被hash
  • 例如5跟5.0的hash值在python內是一樣的，如果被裝飾的function在這兩者輸入會有不同的輸出，那就不能用lru_cache獲得改善
• 可選用的兩個參數
  • maxsize：預設是128，只會cache最後出現的128個結果。設為None會讓cache的size不作限制

Example: Fibonacci數列

不使用lru_cache的DP版本，cache要自己實作

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

使用lru_cache的版本，cache的實作被隱藏起來了

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