众所周知，Python语言灵活、简洁、对程序员友好，但其性能却有点差强人意。这可以通过一个递归斐波那契函数来解决可以这样解释：deffib(n):ifn<=1:returnnreturnfib(n-1)+fib(n-2)计算fib(40)花了33秒我的MBP：importtimedefmain():start=time.time()result=fib(40)end=time.time()cost=end-startprint(f"{result=}{cost=:.4f}")if__name__=='__main__':main()但是，如果在标准库中使用This装饰器，结果完全不同于functoolsimportlru_cache@lru_cachedeffib(n):ifn<=1:returnnreturnfib(n-1)+fib(n-2)这次结果是0秒，你没看错，我保留4位小数，后面的忽略。改进了多少次？我想不通。为什么lru_cache装饰器如此强大，它有什么作用？今天就来说说这个最有用的装饰器。如果你看过计算机操作系统，你一定对LRU很熟悉，它是著名的缓存淘汰算法，但使用时间最长。而lru_cache就是这个算法的具体实现。（面试中经常测试这个算法，有的面试官要求现场手写代码。）下面我们来看一段lru_cache的源码。英文注释我已经帮你翻译成中文了：deflru_cache(maxsize=128,typed=False):"""LRUcachedecorator如果*maxsize*为None，则不会淘汰缓存，不限制缓存大小.如果*typed*为True，不同类型的参数会被独立缓存，比如f(3.0)和f(3)会被认为是不同的函数调用，缓存在两个缓存节点上。函数的参数必须能够被散列才能查看缓存信息。使用命名元组（hits、misses、maxsize、currsize）查看缓存信息：user_func.cache_info()。清除缓存信息：user_func.cache_clear()。LRU算法：http://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)"""#lru_cache的内部实现是线程安全的ifisinstance(maxsize,int):#负数转换为0ifmaxsize<0:maxsize=0elifcallable(maxsize)andisinstance(typed,bool):#如果修饰函数（user_function）直接通过maxsize参数传给user_function，maxsize=maxsize,128wrapper=_lru_cache_wrapper(user_function,maxsize,typed,_CacheInfo)returnupdate_wrapper(wrapper,user_function)elifmaxsizeisnotNone('raiseTypeErrorExpectedfirstrargumenttobeaninteger,acallable,orNone')defdecorating_function(user_function):wrapper=_lru_cache_wrapper(user_function,maxsize,typed,_CacheInfo)returnupdate_wrapper(wrapper,user_function)returnupdate_wrapper(wrapper,user_function)returnupdate_,decoratingfunction(包装)当传入一个缓存大小时，里面有两个参数，当数字为负数时，自动设置为0。我fmaxsize没有传入，或者设置为None，表示缓存没有大小限制，此时不进行缓存淘汰。还有类型。当type传入True时，不同的参数类型会作为不同的key存入缓存。接下来lru_cache的核心就在_lru_cache_wrapper这个函数上了，建议感慨默读背诵。我们看一下它的源码def_lru_cache_wrapper(user_function,maxsize,typed,_CacheInfo):#所有lrucache实例共享的常量：sentinel=object()#唯一用来表示缓存未命中的对象make_key=_make_key#buildakeyfromthefunctionargumentsPREV,NEXT,KEY,RESULT=0,1,2,3#namesforthelinkfieldscache={}hits=misses=0full=Falsecache_get=cache.get#绑定函数获取缓存中key的值cache_len=cache.__len__#绑定函数获取thecachesizelock=RLock()#因为链表上的更新是线程不安全的root=[]#循环双向链表的根节点root[:]=[root,root,None,None]#初始化根节点的前后指针指向自己ifmaxsize==0:defwrapper(*args,**kwds):#没有缓存，只更新统计信息nonlocalmissesmisses+=1result=user_function(*args,**kwds)returnresultelifmaxsizeisNone:defwrapper(*args,**kwds):#只排序，不考虑排序和缓存大小限制nonlocalhits,misseskey=make_key(args,kwds,typed)result=cache_get(key,sentinel)ifresultisnotsentinel:hits+=1returnresultmisses+=1result=user_function(*args,**kwds)cache[key]=resultreturnresultelse:defwrapper(*args,**kwds):#Thesize有限，并跟踪最近使用的缓存nonlocalroot,hits,misses,fullkey=make_key(args,kwds,typed)withlock:link=cache_get(key)iflinkisnotNone:#cachehit，将命中缓存移动到循环双向链表headlink_prev,link_next,_key,result=linklink_prev[NEXT]=link_nextlink_next[PREV]=link_prevlast=root[PREV]last[NEXT]=root[PREV]=linklink[PREV]=lastlink[NEXT]=roothits+=1returnresultmisses+=1result=user_function(*args,**kwds)withlock:ifkeyincache:#走到这里表示key已经放入缓存，释放锁，更新链表。这里什么都不用做，最后只需要返回计算结果passeliffull:#如果缓存满了，就用最老的根节点存放新节点，不需要删除链表（是不是很smart)oldroot=rootoldroot[KEY]=keyoldroot[RESULT]=resultroot=oldroot[NEXT]oldkey=root[KEY]oldresult=root[RESULT]root[KEY]=root[RESULT]=None#最后我们要清除从缓存中删除此密钥，因为它不再有效。delcache[oldkey]#将新值放入缓存cache[key]=oldrootelse:#如果未满则将新结果放入循环双向链表的头部last=root[PREV]link=[last,root,key,result]last[NEXT]=root[PREV]=cache[key]=link#使用cache_len绑定方式，而不是len()函数，可能会包裹在lru_cache本身full=(cache_len()>=maxsize)returnresultdefcache_info():"""报告缓存统计信息"""withlock:return_CacheInfo(hits,misses,maxsize,cache_len())defcache_clear():"""清除缓存信息"""nonlocalhits,misses,fullwithlock:cache.clear()root[:]=[root,root,None,None]hits=misses=0full=Falsewrapper.cache_info=cache_infowrapper.cache_clear=cache_clearreturnwrapper如果你看懂了我写的所有评论，那就不要看我下面的废话是的，如果你还有一点不明白，我再说几句，也许你会明白。首先，所谓的缓存仍然使用内存。为了快速访问，它使用了哈希表，即Python字典，在内存中运行。cache={}其次，如果maxsize==0，相当于不使用缓存，每次调用未命中数+1。代码逻辑是这样的：defwrapper(*args,**kwds):nonlocalmissesmisses+=1#未命中次数result=user_function(*args,**kwds)returnresult三、如果maxsize==None，相当于无限缓存，所以不需要考虑消去。这个实现很简单，我们直接在函数中使用一个Dictionaries即可实现，例如：cache={}defib(n):ifnincache:returncache[n]ifn<=1:returnnresult=fib(n-1)+fib(n-2)cache[n]=returnresult操作时间：理解了这一点，在装饰器中，这个逻辑就不难理解了：defwrapper(*args,**kwds):nonlocalhits,misseskey=make_key(args,kwds,typed)result=cache_get(key,sentinel)ifresultisnotsentinel:hits+=1returnresultmisses+=1result=user_function(*args,**kwds)cache[key]=resultreturnresult四、真正的缓存淘汰算法。为了消除缓存（键值对），我们需要对缓存进行时间排序，这就需要用到链表。链表的头部是最新的插入，尾部是最旧的??插入。当缓存数量达到最大值时，我们删除最长时间未被使用的链尾节点。为了不删除链尾，我们可以使用循环链表。当缓存满了，直接更新链尾节点，分配给新的节点，作为新的链头。向上。当缓存命中时，我们需要将这个节点移到链表的头部，以保证链表的头部最近被频繁使用。为了移动方便，我们需要一个双向链表。双向循环链表用Python实现，可以简单写成：PREV,NEXT,KEY,RESULT=0,1,2,3#namesforthelinkfieldsroot=[]#rootofthecirculardoublelinkedlistroot[:]=[root,root,None,None]#initializebypointingtoself最后一行代码有些朋友可能不理解：root[:]=[root,root,None,None]，画个图你就明白了：这些箭头指向的内存地址节点。增加是这样的：对比这张图，再看源码，就很容易理解了。尤其是这一块的代码逻辑是面试的重点。如果能手写出这样一个线程安全的LRU缓存淘汰算法，无疑是非常棒的。其他LRU算法的实现LRU算法的其他实现，我写了两个，大家可以看这里：LRU缓存淘汰算法-双链表+哈希表[1]LRU缓存淘汰算法-Python有序字典[2]遗言作用装饰器lru_cache的作用是保存函数的计算机结果，下次使用时可以直接从哈希表中取出，避免重复计算，提高效率。简单的直接在函数中使用字典搞定，复杂的点请看lru_cache的代码实现。另一方面，递归函数慢的主要原因之一是重复计算。Python标准库的源码是学习编程最有营养的原材料。好奇的时候，不妨看看源码。相信你会有新的收获。今天的分享就到这里。有收获请点赞、观看、转发、关注。感谢您的支持。参考资料[1]LRU缓存淘汰算法-双链表+哈希表：https://github.com/somenzz/geekbang/blob/master/algorthms/lru_use_link_table.py[2]LRU缓存淘汰算法-Python有序字典：https//github.com/somenzz/geekbang/blob/master/algorthms/lru_use_ordered_dict.py
