什么是LRU? |
---|
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。 我们需要记住以下几点就行了:这里以队列为例
方法一:列表模拟 |
---|
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的算法小抄