| 什么是LRU？ |
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
我们需要记住以下几点就行了：这里以队列为例
- 要设置一个容量，比如我们设置队列的长度为2；
- 当进来一个元素，比如（'a',1），插入到列表中[('a',1)]，再进来一个('b',2)，插入到列表中，[('a',1),('b',2)]，再进来一个('c',3)，此时列表已满，这时我们要将最久未被使用的元素删除，也就是('a','1')，再将新元素插入到列表中，[('b',2),('c',3)]；同时，如果当前插入的元素在列表中已经存在，那么我们也要将其移到最近使用的位置；
- 假设这时我们使用了('b','2')，那么当前元素就是我们最近使用过的了，队列就变为[('c',3),('b',2)]，下次再添加一个新的元素的时候就是优先将('c','3')移除了；
- 我们要保证删除和插入的时间复杂度为O(1)，因此要使用字典，而且字典中的元素要是有序的，因此使用python自带的OrderedDict；
- 进一步的是，假设我们要自己实现底层，那么使用的结果就是hash双向链表，这样查找、删除、插入的时间复杂度就都是O(1)；
| 方法一：列表模拟 |
class LRUCache:
#@param capacity,an integer
def __init__(self,capacity):
self.cache ={}
self.used_list=[]
self.capacity = capacity
#@return an integer
def get(self,key):
if key in self.cache:
#使用一个list来记录访问的顺序，最先访问的放在list的前面，最后访问的放在list的后面，故cache已满时，则删除list[0]，然后插入新项；
if key != self.used_list[-1]:
self.used_list.remove(key)
self.used_list.append(key)
return self.cache[key]
else:
return -1
def set(self,key,value):
if key in self.cache:
self.used_list.remove(key)
elif len(self.cache) == self.capacity:
self.cache.pop(self.used_list.pop(0))
self.used_list.append(key)
self.cache[key] = value
| 方法二：有序字典模拟 |
import collections
# 基于orderedDict实现
class LRUCache(collections.OrderedDict):
'''
function:利用collection.OrdereDict数据类型实现最近最少使用的算法
OrdereDict有个特殊的方法popitem(Last=False)时则实现队列，弹出最先插入的元素
而当Last=True则实现堆栈方法，弹出的是最近插入的那个元素。
实现了两个方法：get(key)取出键中对应的值，若没有返回None
set(key,value)更具LRU特性添加元素
'''
def __init__(self, size=2):
self.size = size
self.cache = collections.OrderedDict() # 有序字典
def get(self, key):
if key in self.cache.keys():
# 因为在访问的同时还要记录访问的次数（顺序）
value = self.cache.pop(key)
# 保证最近访问的永远在list的最后面
self.cache[key] = value
return value
else:
value = None
return value
def set(self, key, value):
if key in self.cache.keys():
self.cache.pop(key)
self.cache[key] = value
elif self.size == len(self.cache):
self.cache.popitem(last=False)
self.cache[key] = value
else:
self.cache[key] = value
测试小例子：
if __name__ == '__main__':
test = LRUCache()
test.set('a', 1)
print(test.cache)
test.set('b', 2)
print(test.cache)
test.set('c', 3)
print(test.cache)
test.set('d', 4)
print(test.cache)
test.set('e', 5)
print(test.cache)
# test.set('f',6)
t1 = test.get('d')
print(t1)
print(test.cache)
结果：
OrderedDict([('a', 1)])
OrderedDict([('a', 1), ('b', 2)])
OrderedDict([('a', 1), ('b', 2), ('c', 3)])
OrderedDict([('b', 2), ('c', 3), ('d', 4)])
OrderedDict([('c', 3), ('d', 4), ('e', 5)])
4
OrderedDict([('c', 3), ('e', 5), ('d', 4)])
| 方法三：hash双向链表 |
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
self.prev = None
class DoubleList:
def __init__(self):
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.size = 0
self.head.next = self.tail
self.tail.prev = self.head
def addLast(self, x):
x.prev = self.tail.prev
x.next = self.tail
self.tail.prev.next = x
self.tail.prev = x
self.size += 1
def remove(self, x):
x.prev.next = x.next
x.next.prev = x.prev
self.size -= 1
def removeFirst(self):
if self.head.next == self.tail:
return None
first = self.head.next
self.remove(first)
return first
def getSize(self):
return self.size
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = DoubleList()
self.dic = {}
def makeRecently(self, key):
x = self.dic.get(key)
self.cache.remove(x)
self.cache.addLast(x)
def addRecently(self, key, val):
x = Node(key, val)
self.cache.addLast(x)
self.dic[key] = x
def deleteKey(self, key):
x = self.dic.get(key)
self.cache.remove(x)
self.dic.pop(key)
def removeLeastRecently(self):
deleteNode = self.cache.removeFirst()
deleteKey = deleteNode.key
self.dic.pop(deleteKey)
def get(self, key):
if not key in self.dic:
return -1
self.makeRecently(key)
return self.dic.get(key)
def put(self, key ,val):
if key in self.dic:
self.deleteKey(key)
self.addRecently(key, val)
return
if self.cap == self.cache.size:
self.removeLeastRecently()
self.addRecently(key, val)
这种实现还有点问题，只要掌握思路就好了。
参考：
百度百科
https://blog.csdn.net/qq_35810838/article/details/83035759
labuladong的算法小抄