python LFU算法
旺旺小小超 人气:0在第一节中实现了双向链表DoubleLinkedList类，上一节中基于双向链表实现了LRU算法，本节课我们继续基于双向链表实现LFU(Least frequently used 最不经常使用)算法。
一、重写Node节点类
构建LFUNode类 继承自第一节中的Node类，添加freq属性用来表示节点使用频率
class LFUNode(Node): def __init__(self, key, value): """ LFU节点 增加频率属性 :param key: :param value: """ self.freq = 0 super(LFUNode, self).__init__(key, value)
二、LFU实现
LFU的实现除了get和put之外还有一个私有的__update_freq更新节点频率方法，读写某节点时都需要对该节点的频率属性进行更新。除了map之外新增加一个freq_map来存储每个频率下的双向链表，当达到最大容量时移除最小频率下的头部的节点。
class LFUCache(object):
def __init__(self, capacity=0xffffffff):
"""
LFU缓存置换算法 最不经常使用
:param capacity:
"""
self.capacity = capacity
self.size = 0
self.map = {}
self.freq_map = {}
def __update_freq(self, node):
"""
更新节点频率
:param node:
:return:
"""
freq = node.freq
# 当前节点所在频率存在 在当前频率链表中移除当前节点
if freq in self.freq_map:
node = self.freq_map[freq].remove(node)
# 当前频率链表为空时删除该频率链表
if self.freq_map[freq].size == 0:
del self.freq_map[freq]
# 将节点按照新频率写入频率链表
freq += 1
node.freq = freq
if freq not in self.freq_map:
self.freq_map[freq] = DoubleLinkedList()
self.freq_map[freq].append(node)
return node
def get(self, key):
"""
获取元素
:return:
"""
# 节点不存在
if key not in self.map:
return None
# 节点存在 更新使用频率
old_node = self.map.get(key)
new_node = self.__update_freq(old_node)
self.map[key] = new_node
return new_node.value
def put(self, key, value):
"""
设置元素
:param key:
:param value:
:return:
"""
# 节点已存在 更新频率
if key in self.map:
old_node = self.map.get(key)
old_node.value = value
new_node = self.__update_freq(old_node)
self.map[key] = new_node
else:
# 节点容量达到上限 移除最小频率链表头部的节点
if self.size >= self.capacity:
min_freq = min(self.freq_map)
node = self.freq_map[min_freq].pop()
del self.map[node.key]
self.size -= 1
# 构建新的节点 更新频率
new_node = LFUNode(key, value)
new_node = self.__update_freq(new_node)
self.map[key] = new_node
self.size += 1
return new_node
def print(self):
"""
打印当前链表
:return:
"""
for freq, link in self.freq_map.items():
print("frequencies： %d" % freq)
link.print()三、测试逻辑
if __name__ == '__main__': lfu_cache = LFUCache(4) lfu_cache.put(1, 1) lfu_cache.print() lfu_cache.put(2, 2) lfu_cache.print() print(lfu_cache.get(1)) lfu_cache.print() lfu_cache.put(3, 3) lfu_cache.print() lfu_cache.put(4, 4) lfu_cache.print() lfu_cache.put(5, 5) lfu_cache.print() print(lfu_cache.get(2)) lfu_cache.put(4, 400) lfu_cache.print()
测试结果:
加载全部内容