LRU（LeastRecentlyUsed，最近最少使用，最长未使用）是一种缓存淘汰算法。缓存是计算机中用来提高访问资源速度的一种方法。将从数据库、硬盘、网络或其他地方读取的数据，暂时存放在一个方便读取的地方（即缓存（Cache）），这样就不用再在上面的地方搜索读取了再次阅读时。一般来说，缓存空间是有限的，只保留经常读取的数据，淘汰不经常读取的数据。LRU是众多缓存淘汰算法中的一种。当缓存容量满时，淘汰最长时间未被访问的元素。他的算法设计很简单。首先是数据结构设计。对于缓存中的每一个元素，可以将其存储为键值对，读取时可以通过键读取对应的数据。缓存是一个优先级队列，元素的优先级在运行过程中不断变化。每次访问一个key时，将该key对应的元素的优先级设置为最低（即最近访问的）。每次插入新元素时，如果键已经存在，则更新其值并将其设置为最近使用的。如果key不存在，检查capacity是否已满。如果已满，则删除缓存中优先级最高的元素，即最长时间未被访问的元素。然后添加一个元素并将其设置为最近访问过的。这是我的伪代码，大家看一下。元素key：value缓存容量Ncache[缓存元素0，缓存元素1，..,缓存元素N]访问key为x的元素：如果x在缓存中，则返回x对应的元素的值，并设置该元素为最近一次访问；如果没有，则返回空z的元素：如果缓存中已经有key为y的元素，则将其值更新为z，并设置为最近一次访问。如果缓存中没有key为y的元素，则检查缓存中的元素个数是否达到了容量。如果是，则删除最旧访问的元素，将一个key为y，value为z的元素添加到缓存中，并设置该元素为最近访问的。具体这个优先级队列怎么实现，一个简单的实现就是让每个缓存的元素维护一个时间变量。如果访问或添加元素，则元素时间设置为0，剩余元素时间+1。当缓存满了需要淘汰内存时，删除时间值最大的元素。这个设计很明显，时间复杂度很高。每次插入和读取时，都需要更新所有元素的时间。淘汰的时候也要遍历找到时间最大的元素。一种更有效的方法是使用哈希表和双向链表。哈希表的特点是大部分时间查找时间复杂度为O(1)，但没有优先级，甚至没有先后顺序。双向链表的特点是在头尾增删效率高，但查找效率低。因此，可以设置这样的缓存结构。哈希表用于存储键和对应元素的地址，以便快速访问和判断元素是否存在。在双向链表中，每个节点存储一个元素的键值对。当一个元素成为最高优先级时，相应的节点被放置在链表的头部。当缓存容量满时，丢弃链表末尾的节点，同时删除哈希表中的key。为了方便操作，链表采用双向链表，目的是方便删除。双向链表中的头节点和尾节点是不包含有用数据的虚拟节点。双向链表中的节点之所以也存储值，是因为元素被丢弃的时候。哈希表很容易从被丢弃的元素中获取对应的key。以下是我的代码。对于双向链表数据结构，我已经实现了这些操作，方便缓存调用。typeLRUDoubleListNodestruct{prev,next*LRUDoubleListNodekey,valueint}//双向链表typeLRUDoubleListstruct{head,tail*LRUDoubleListNode}//构造一个初始双向链表funcNewLRUDoubleList()LRUDoubleList{l:=LRUDoubleList{}l.head=&LRUDoubleListNode{}l.tail=&LRUDoubleListNode{}l.head.next=l.taill.tail.prev=l.headreturnl}//将节点添加到链表头部func(l*LRUDoubleList)addToHead(node*LRUDoubleListNode){headNext:=l.head.nextl.head.next=nodeheadNext.prev=nodenode.next=headNextnode.prev=l.head}//移除节点func(l*LRUDoubleList)remove(node*LRUDoubleListNode){node.prev.next=node.nextnode.next.prev=node.prev}//移除尾节点func(l*LRUDoubleList)removeFromTail()*LRUDoubleListNode{ifl.head.next==l.tail{returnnil}node:=l.tail.prevl.remove(node)returnnode}对于缓存结构，实现了这些操作//缓存结构类型LRUCachestruct{capacityint键盘映射map[int]*LRUDoubleListNodecacheLRUDoubleList}//构造缓存funcNewLRUCache(capacityint)LRUCache{lru:=LRUCache{capacity:capacity}lru.keymap=make(map[int]*LRUDoubleListNode)lru.cache=NewLRUDoubleList()returnlru}//设置一个key为最近访问的func(lru*LRUCache)setMostRecently(keyint){node:=lru.keymap[key]lru.cache.remove(node)lru.cache.addToHead(node)}//添加元素func(lru*LRUCache)addItem(key,Valueint){node:=&LRUDoubleListNode{key:key,value:Value}lru.keymap[key]=nodelru.cache.addToHead(node)}//移除元素func(lru*LRUCache)removeItem(keyint){//这个好像没有用到node:=lru.keymap[key]lru.cache.remove(node)delete(lru.keymap,key)}//去掉最长时间不访问元素func(lru*LRUCache)removeLeastRecently(){node:=lru.cache.removeFromTail()delete(lru.keymap,node.key)}//读取操作func(lru*LRUCache)Get(keyint)int{如果项目，ok:=lru.keymap[key];好的{lru.setMostRecently(item.key)返回item.value}else{rreturn-1}}//新操作func(lru*LRUCache)Put(keyint,valueint){ifitem,ok:=lru.keymap[key];ok{item.value=valuelru.setMostRecently(item.key)}else{iflen(lru.keymap)>=lru.capacity{lru.removeLeastRecently()}lru.addItem(key,value)}}Python实现来自typingimportDict,List,UnionclassDoubleListNode(object):'''存储键值对的双向链表节点属性：key：缓存键值：缓存值prev：前一个指针节点：post指针'''def__init__(self,键=无，值=无）：自我。key:int=keyself.value:int=valueself.prev:DoubleListNode=Noneself.next:DoubleListNode=NoneclassDoubleList(object):'''存储键值对的双向链表属性：head：头指针，非included有用数据，即adummynodetail:tail指针，不包含有用数据，即adummynode'''def__init__(self):self.head=DoubleListNode()self.tail=DoubleListNode()self.head.next=自我。尾巴self.tail.prev=self.headdefadd_to_head(self,node:DoubleListNode):'''添加一个新节点到双列表节点的头部Args:node:newnodeThisnodeshouldbecreatedbeforecallingReturns:NoneRaise:None'''head_next=self.head.nextself.head.next=nodehead_next.prev=nodenode.next=head_nextnode.prev=self.headdefremove(self,node:DoubleListNode):'''从链中删除一个nodeArgs：node：要删除的节点。此节点在调用之前应通过其他方法找到其实例Returns:NoneRaise:None'''node.prev.next=node.nextnode.next.prev=node.prevdefremove_from_tail(self)->Union[DoubleListNode,None]:'''删除链表末尾的节点Args:None返回:如果链表中包含有用的数据，则返回要删除的节点实例。否则返回NoneRaise:None'''ifself.head.next==self.tail:returnNoneelse:node=self.tail.prevself.remove(node)returnnodeclassLRUCache(object):'''LRUcacheclass,属性：cache：缓存链表，每个节点存储缓存的键值对capacity：capacity，超过这个容量，最长时间没有被使用的缓存节点将被丢弃keymap：hashtable，每个key对应一个缓存节点'''def__init__(self,capacity):'''初始化，指定容量'''self.capacity=capacityself.keymap:Dict[int,DoubleListNode]={}self.cache=DoubleList()defadd_item(self,key:int,value:int):'''添加新缓存Args:key:cachekeyvalue:cachevalueReturns:NoneRaise:None'''node=DoubleListNode(key=key,value=值）自我。keymap[key]=nodeself.cache.add_to_head(node)defremove_item(self,key:int):#'''删除缓存参数：key:缓存的keyReturns:Noneraise:None'''#这个好像没有用到node=self.keymap[key]self.cache.remove(node)delself.keymap[key]defremove_least_recently(self):'''删除最不用的缓存Args:NoneReturns:NoneRaise:None'''node=self.cache.remove_from_tail()delself.keymap[node.key]defset_most_recently(self,key:int):'''设置一个key对应的缓存为最近使用过的args:key:cachedkeyReturns:NoneRaise:None'''node=self.keymap[key]self.cache.remove(node)self.cache.add_to_head(node)defget(self,key:int)->int:'''读取缓存Args:key:缓存的keyReturns:如果缓存存在，则返回缓存的值，否则，return-1Raise:None'''ifkeyinself.keymap:self.set_most_recently(key)returnself.keymap[key].valueelse:return-1defput(self,key:int,value:int):'''新增存储Args:key:存储的键value:存储的值返回：无提升：无'''如果在self.keymap中键入：self.keymap[key].value=valueself.set_most_recently(key)else:iflen(self.keymap)>=self.capacity:self.remove_least_recently()self.add_item(键,值)
