LRU Cache在Python中的实现
LRU Cache - Least Recently Used Cache
最近最久未使用缓存
今天问了同事一个问题,LRU Cache系统如何实现,同事答使用时间戳。那么使用时间戳的话,他可能的想法是在Python里的字典中实现,这样通过判断时间戳的迟早来实现LRU。
首先缓存,比如对于一个这样的函数,task(arg1, arg2)
,缓存主要是缓存其参数和返回值,那么就可以直接使用字典来实现,关键在于参数是可以哈希的,也就是说参数不应该是可变的,这样就可以将参数作为key,函数返回值作为value来存储到字典之中。
那么对于LRU,LRU比较常用的在操作系统内存管理的页面置换中使用到了,就是最近使用的页面在内存中,否则就在硬盘里,为了提高页面的命中率,其英文为hits,没有命中则为misses。对于上面的这个函数来说就是要存储最近使用的参数和返回值这么一个对应关系。
时间戳字典可行吗?
对于同事提到的字典,其缓存模型应该是函数参数作为key,因为要通过key来判断是否命中,时间戳也作为key,因为要比较最近使用,比如缓存已经满了,要将最早使用的缓存清除出去,那么这时候就要比较哪个参数对应的时间是最早的。
这里有一种multi_key_dict
,也就是多个键对应一个值,假设时间戳不会冲突的话,使用时间戳和参数作为键,那么要取到最早的时间戳,也需要一个排序,因为键在字典中是无序的。且不说从这么多键中找出时间戳这种键,并且还有一个问题是如果参数也是时间戳呢= = !
使用list
既然要取时间戳需要排序,那么不用时间戳,直接将对应的key也就是函数参数存储到一个Python列表中就行了,最近使用的在列表头,最早使用的在列表尾,然后用一个字典存储参数-返回值,这样就实现了一个LRU嘛。
如果有参数命中(key在字典中),那么就把这个参数从其原始位置放到列表头,如果满了就删除最后一个元素。这样看起来可以,但是涉及性能问题。从列表中间pop和从头insert都是性能瓶颈操作,时间复杂度在O(n)
。
使用链表
既然使用list在insert时候有性能问题,那么使用单链表呢,只有有头指针,我就可以在头部插入,此时时间复杂度只有O(1)
。但是将参数从单链表尾部移除呢,还得从头遍历一遍到尾部,那那那就用双向循环链表好了,这样找尾部元素,就可以直接使用头指针向前得到了。
看起来好像一切OK了,但是认真想想,如果命中一个参数,那么要将其从中间某个位置弄到最开头呢?双向循环链表还是得去遍历一遍链表去查找,平均的时间复杂度也要O(n)
使用字典和链表相结合
在取缓存的时候,通过字典直接从参数取到返回值,那么可不可以将链表和字典结合起来呢,使用key能不能直接获取到key在链表的位置呢?当然可以,key对应的value存储为这个key对应的链表节点不就可以了,同时这个链表节点还存储了返回值不就刚好可以将返回值取到了嘛。
functools.lru_cache
Python中functools的lru_cache
实现了LRU Cache,核心是一个双向循环链表再加一个字典。
from functools import lru_cache
可以看到lru_cache
的代码:
|
|
首先这是一个带参数的装饰器,使用的时候应该@lru_cache()
,这样会返回decorating_function
,用来装饰用户的函数,其内部会返回将用户的包装后的函数,使用的是_lru_cache_wrapper
:
|
|
当缓存已经满了的时候,这种处理方式还是挺不错的,但是要是我来搞就是删除后面的节点,然后将新节点放到root前面。另外这个人是左撇子么,喜欢逆时针转啊。
OrderedDict相关
另一个使用双向循环链表的例子是OrderedDict,链表保存了key添加到字典的顺序,但其实这个字典实际用的时候,是用的C语言实现的版本:
|
|
下面是OrderedDict的源码:
|
|
这里_Link()
是一个限定属性的类,代码如下;
|
|
_proxy
是from _weakref import proxy as _proxy
对一个对象的弱引用。相对于通常的引用来说,如果一个对象有一个常规的引用,它是不会被垃圾收集器销毁的,但是如果一个对象只剩下一个弱引用,那么它可能被垃圾收集器收回。werkref
|
|
继续来看OrderedDict:
|
|
其它方法就不一一说明了,但是从中可以看出,涉及到元素顺序的操作,双向循环链表的应用还是很广泛的。