第一模块：5-8LFU最少使用缓存置换算法
讲师：咚咚呛
第二模块，课程内容
除记录频率外，还记录同频率最近使用的节点
class LFUNode(Node):
def __init(self, key, value):
self.freq = 0
super(LFUNode, self).__init__(key, value)
class LFUCache(object):
def __init__(self, capacity):
self.capacity = capacity
self.map = {}
self.size = 0
self.freq_map = {} # key：频率，value：频率对应的双向链表
def __update_freq(self, node):
"""更新节点的频率"""
freq = node.freq
node = self.freq_map[freq].remove(node) # 从原频率队列中删除node
if self.freq_map[freq].size == 0:
def self.freq_map[freq] # 若原频率队列变为空，则删除该链表
freq += 1 # 频率加1
node.freq = freq # 更新节点频率
if freq not in self.freq_map:
self.freq_map[freq] = DoubleLinkedList()
self.freq_map[freq].append(node) # 将节点加入新的对应的频率链表
def get(self, key):
if key not in self.map:
return -1
node = self.map.get(key)
sefl.__update_freq(node)
return node.value
def put(self, key, value):
if self.capacity == 0:
return
if key in self.map: # 缓存命中
node = self.map.get(key)
node.value = value
self.__update_freq(node) # 更新节点使用频率
else:
if self.size == self.capacity: # 缓存溢出
min_freq = min(self.freq_map)
node = self.freq_map[min_freq].pop()
def self.map[node.key]
self.size -= 1
node = LFUNode(key, value) # 为新的内容创建新节点
node.freq = 1 # 初始化频率
self.map[key] = node
if node.freq not in self.freq_map:
self.freq_map[node.freq] = DoubleLinkedList()
node = self.freq_map[node.freq].append(node) # 将新节点加入对应的频率双向链表
self.size += 1
def print(self):
print('='*30)
for k, v in self.freq_map.items(): # 打印频率双向链表
print("freq = %d" % k)
self.freq_map[k].print()
print('='*30)
print()