【算法工程师笔试机构|LRU缓存淘汰算法（Python）】使用哈希链表实现，而哈希链表由双向链表和哈希表构建。
参考自算法就像搭乐高：带你手撸 LRU 算法
class Node:
"""
节点类
"""def __init__(self, k, v):
self.k = k
self.v = v
self.next = None
self.prev = Noneclass DoubleList:
"""
双向链表
"""def __init__(self):
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0def addLast(self, x):
"""
尾部添加节点
:param x:
:return:
"""
x.next = self.tail
x.prev = self.tail.prev
self.tail.prev.next = x
self.tail.prev = x
self.size += 1def remove(self, x):
"""
删除节点
:param x:
:return:
"""
x.prev.next = x.next
x.next.prev = x.prev
self.size -= 1def removeFirst(self):
"""
删除列表的第一个节点
:return:
"""
first = self.head.next
if first == self.tail:
return None
self.remove(first)
return firstdef length(self):
"""
列表长度
:return:
"""
return self.sizeclass LRUCache:
"""
LRU类
"""def __init__(self, capacity):
self.capacity = capacity
self.cache = DoubleList()
self.map = {}def get(self, key):
"""
获取key
:param key:
:return:
"""
if not self.map.get(key):
return -1
self.makeRecently(key)
return self.map.get(key).vdef put(self, key, val):
"""
添加或修改类
:param key:
:param val:
:return:
"""
if self.map.get(key):
self.deleteKey(key)
self.addRecently(key, val)
return
if self.cache.length() == self.capacity:
self.removeLeaseRecently()
self.addRecently(key, val)def makeRecently(self, key):
"""
将节点提升为最近使用的
:param key:
:return:
"""
node = self.map.get(key)
self.cache.remove(node)
self.cache.addLast(node)def deleteKey(self, key):
"""
删除key
:param key:
:return:
"""
node = self.map.get(key)
self.cache.remove(node)
self.map.pop(key)def removeLeaseRecently(self):
"""
删除最久未使用的
:return:
"""
node = self.cache.removeFirst()
self.map.pop(node.k)def addRecently(self, key, val):
"""
添加最新使用的
:param key:
:param val:
:return:
"""
node = Node(key, val)
self.cache.addLast(node)
self.map[key] = nodelru = LRUCache(2)
print(lru.get(1))
lru.put(1, 2)
print(lru.get(1))
lru.put(2, 3)
lru.put(3, 4)
print(lru.cache.tail.prev.k, lru.cache.tail.prev.v)
推荐阅读
- 计算机|基于SqlSugar的开发框架循序渐进介绍（5）-- 在服务层使用接口注入方式实现IOC控制反转
- 关于Python不为人知的10大谬论
- 10个Python绘画表白代码内附源码，再不收藏你只能单身了
- django框架|django框架——模型层（下）
- django框架|django框架——模型层（上）
- django框架|django框架——ajax
- django框架|django框架——路由层
- web框架|django框架——模板层
- web框架|django框架——django基础使用