Python LRU算法
旺旺小小超 人气:0在第一节中已经实现了双向链表DoubleLinkedList类，本节我们基于双向链表实现LRU（Least Recently Used最近最少使用）缓存置换算法。Redis的淘汰机制就包括LRU算法，用来淘汰那些最近最少使用的数据，具体怎么使用可在redis的配置文件中设置。
一、LRU算法的实现
逻辑很简单，get和put两种操作，其中get时如果元素存在则将节点从当前位置移到链表头部，表示最近被访问到的节点；put时也是，不管节点之前存不存在都要移动到链表头部。同样通过一个map来实现查找时的O(1)复杂度。
class LRUCache(object):
def __init__(self, capacity=0xffffffff):
"""
LRU缓存置换算法 最近最少使用
:param capacity:
"""
self.capacity = capacity
self.size = 0
self.map = {}
self.list = DoubleLinkedList(capacity)
def get(self, key):
"""
获取元素
获取元素不存在 返回None
获取元素已存在 将节点从当前位置删除并添加至链表头部
:param key:
:return:
"""
# 元素不存在
if key not in self.map:
return None
node = self.map.get(key)
self.list.remove(node)
self.list.append_front(node)
return node.value
def put(self, key, value):
"""
添加元素
被添加的元素已存在 更新元素值并已到链表头部
被添加的元素不存在
链表容量达到上限 删除尾部元素
链表容量未达上限 添加至链表头部
:param key:
:param value:
:return:
"""
if key in self.map:
node = self.map.get(key)
node.value = value
self.list.remove(node)
self.list.append_front(node)
else:
if self.size >= self.capacity:
old_node = self.list.remove()
del self.map[old_node.key]
self.size -= 1
node = Node(key, value)
self.map[key] = node
self.list.append_front(node)
self.size += 1
return node
def print(self):
"""
打印当前链表
:return:
"""
self.list.print()二、测试逻辑
if __name__ == '__main__': lru_cache = LRUCache(3) lru_cache.put(1, 1) lru_cache.print() lru_cache.put(2, 2) lru_cache.print() print(lru_cache.get(1)) lru_cache.print() lru_cache.put(3, 3) lru_cache.print() lru_cache.put(1, 100) lru_cache.print() lru_cache.put(4, 4) lru_cache.print() print(lru_cache.get(1)) lru_cache.print()
测试结果:
加载全部内容