functools模块的lur_cache装饰器是python的一种常用、优雅的缓存工具。旨在用简洁的方式，保存函数调用结果，当使用重复的参数调用某函数时，能快速从缓存中获取结果，而不需要重复执行该函数。

1、如何使用lru_cache装饰器

以求解斐波那契数列第n位的计算为例，常规模式下，实现代码如下:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1)+fib(n-2)
fib(n=10)

使用lru_cache装饰器，实现代码如下:

from functools import lru_cache
@lru_cache()
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1)+fib(n-2)
fib(n=10)

非常的简洁,也极大的减少了程序执行时间。

2、lru_cache 的实现原理

装饰器的基本原理是函数的闭包，核心在于修饰后返回的wrapper。

def lru_cache(maxsize=128, typed=False):
  #第一步参数判断，maxsize为正整数或者none
    if isinstance(maxsize, int):
        if maxsize < 0:
            maxsize = 0
    elif maxsize is not None:
        raise TypeError('Expected maxsize to be an integer or None')
    # 核心方法，修饰函数
    def decorating_function(user_function):
        wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
        return update_wrapper(wrapper, user_function)

    return decorating_function

在lru_cache的实现函数中，除了必要的参数判断外，核心方法是_lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)，

def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
    sentinel = object()          
    make_key = _make_key         # 绑定方法，生成哈希值的
    PREV, NEXT, KEY, RESULT = 0, 1, 2, 3   # 每个节点link的数据标识，常量
    cache = {} #存储缓存的容器，这是一个key-value的dict，是无序的
    hits = misses = 0 # 统计调用次数的
    full = False # 是否达到缓存最大存储空间
    cache_get = cache.get    # 绑定方法，获取key
    cache_len = cache.__len__  # 同上，绑定len()方法
    lock = RLock()           # 线程安全锁
    root = []                # 循环双向链表
    root[:] = [root, root, None, None]     # 初始化循环双向链表
   # 如果maxsize==0,就是不用缓存，照常执行函数，只统计函数的执行次数
    if maxsize == 0:
        def wrapper(*args, **kwds):
            # No caching -- just a statistics update
            nonlocal misses
            misses += 1
            result = user_function(*args, **kwds)
            return result
   # 如果maxsize==None,那么设置缓存空间位无限大，只要内存支持，这时候循环链表是没用的。
    elif maxsize is None:
        def wrapper(*args, **kwds):
            nonlocal hits, misses
            key = make_key(args, kwds, typed) # 获取key，实际上就把参数打包，求哈希值
            result = cache_get(key, sentinel) # 直接从缓存容器中取值
            if result is not sentinel:
                hits += 1
                return result
            misses += 1
            result = user_function(*args, **kwds)
            cache[key] = result
            return result
    else:
      # 关键方法，从缓存中拿数据，并重新排序
        def wrapper(*args, **kwds):
            # Size limited caching that tracks accesses by recency
            nonlocal root, hits, misses, full
            key = make_key(args, kwds, typed)
            with lock:
                link = cache_get(key)
                if link is not None:
                    # 拿到节点后，把这个节点移动到最前面去，并把之前的节点重新链接起来
                    link_prev, link_next, _key, result = link
                    link_prev[NEXT] = link_next # 把link的上一个节点的后继指针指向link的下一个节点
                    link_next[PREV] = link_prev #  把link的下一个节点的前驱指针指向link的上一个节点
                    last = root[PREV] # 找到链表的最近的那个节点
                    last[NEXT] = root[PREV] = link  # 把那个last节点的后继指针指向link
                    link[PREV] = last # 把link的前驱指针指向当前的last
                    link[NEXT] = root # link的后继指针就执行这个链表的本身root
                    # fuck，真是绕死了。
                    hits += 1
                    return result
                misses += 1
            result = user_function(*args, **kwds)
            with lock:
                if key in cache:
                # 没啥卵用
                    pass
                elif full:
                    # 如果缓存容器满了，先把最新的加上去
                    oldroot = root
                    oldroot[KEY] = key
                    oldroot[RESULT] = result
                    root = oldroot[NEXT]
                    oldkey = root[KEY]
                    oldresult = root[RESULT]
                    root[KEY] = root[RESULT] = None
                    # 再删除最旧的那一个key对应的节点
                    del cache[oldkey]
              
                    cache[key] = oldroot
                else:
                    # 一个新的数据结果，添加到双向链表中，找到目前那个last，把他的next指向新数据
                    last = root[PREV] # 找到目前链表的最前端
                    link = [last, root, key, result] # 新建一个节点
                    last[NEXT] = root[PREV] = cache[key] = link # 把这个新节点作为last
                      # 添加后判断是否达到缓存空间最大值
                    full = (cache_len() >= maxsize) 
            
            return result

从lru_cache的源码实现来看，当执行某函数时，会先判断maxsize是什么，如果是0，那么就不使用缓存机制了。如果是none，那么就使用一个没大小限制的缓存机制。如果是某正整数，那么执行lur算法的缓存机制。在使用缓存机制的模式下，程序会把参数打包，计算它的哈希值作为key，从一个叫cache的容器中找这个key对应的value，这个cache就是dict，一个平平无奇的字典。如果cache中有这个key，那么直接拿到这个value，这个value就是源码中的link，它保存着4个数据，包括 link_prev, link_next, _key, result ,即前后节点的指针，key本身，以及缓存的函数运算结果result。拿完数据后还得把链表进行重新排序，如果使用lur算法，那么就把刚才拿到的那个节点移动到链表的最前面，作为last节点，这个节点的next就执行链表本身root。

如果缓存里面没有这个key，那么新建一个节点，作为链表的last节点插入进去，插入完成后判断缓冲区的大小，重新标识full值，下一次判断的时候就不用重新计算容器size了。如果缓存区满了，那么把最旧的那个节点删除掉。

3、为什么要用lru_cache

缓存的机制就是把函数的输入和输出保存下来，下次重复输入的时候，直接读取缓存的结果，而减少了函数的计算。而大多数情况下，缓存不可能无限大，所以在缓存区见满了的情况下，删除哪些数据是一个重要的问题。而LRU的算法思想实际上是一种缓存数据淘汰的思想，即最近最少使用的数据有限被淘汰掉，节省存储空间。反过来想，这种算法的实质是，认为最近使用的数据是以后也经常要使用的数据。所以在源码中，定义了一个循环链表来存储数据的顺序。如果没有这个算法，备忘录算法和缓存思想实际上是一样的，同样用斐波那契的计算为例，备忘录的计算方式是这样的：

def fib(n):
  # 备忘录，即缓存
    meno = dict()
    def f(n):
        value = meno.get(n)
        if value:
            return value
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            result = f(n-1)+f(n-2)
            meno[n] = result
            return result
    return f(n)
x = fib(n=100)

而加上了LRU的缓存，除了定一个dic作为缓存区间外，还增加了一个root循环双向链表作为顺序列表，因为dic在python语法里面是无序的。同时，链表的增加和删除并不是线程安全的，源码中使用了一个RLook来保证线程安全。