编写一个具有put,get功能的LFU Cache类,并写上注释
时间: 2024-05-19 13:14:26 浏览: 54
行业分类-设备装置-具有增强速度的写辅助存储器.zip
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # 存储缓存的字典,key为缓存的键,value为缓存的值和访问次数的元组
self.freq = {} # 存储访问次数和对应的缓存键的字典
self.min_freq = 0 # 最小访问次数
def get(self, key: int) -> int:
if key not in self.cache: # 如果缓存中没有该键,则返回-1
return -1
value, count = self.cache[key] # 获取缓存中键对应的值和访问次数
self.freq[count].pop(key) # 从对应的访问次数字典中删除该键
if not self.freq[count]: # 如果该访问次数已经没有对应的键,则删除该访问次数
self.freq.pop(count)
if self.min_freq == count: # 如果最小访问次数等于该访问次数,则最小访问次数加1
self.min_freq += 1
count += 1 # 访问次数加1
self.cache[key] = (value, count) # 更新缓存中键对应的值和访问次数
if count not in self.freq: # 如果访问次数不存在,则创建该访问次数
self.freq[count] = {}
self.freq[count][key] = None # 将该键加入到对应的访问次数字典中
return value
def put(self, key: int, value: int) -> None:
if self.capacity == 0: # 缓存容量为0,则直接返回
return
if key in self.cache: # 如果缓存中已经存在该键,则更新键对应的值和访问次数
_, count = self.cache[key]
self.freq[count].pop(key)
if not self.freq[count]: # 如果该访问次数已经没有对应的键,则删除该访问次数
self.freq.pop(count)
if self.min_freq == count: # 如果最小访问次数等于该访问次数,则最小访问次数加1
self.min_freq += 1
count += 1 # 访问次数加1
self.cache[key] = (value, count) # 更新缓存中键对应的值和访问次数
if count not in self.freq: # 如果访问次数不存在,则创建该访问次数
self.freq[count] = {}
self.freq[count][key] = None # 将该键加入到对应的访问次数字典中
else:
if len(self.cache) == self.capacity: # 如果缓存已满,则删除最少使用的缓存
key_to_remove = self.freq[self.min_freq].popitem(last=False)[0]
del self.cache[key_to_remove]
count = 1 # 访问次数为1
self.cache[key] = (value, count) # 更新缓存中键对应的值和访问次数
self.freq[count][key] = None # 将该键加入到对应的访问次数字典中
self.min_freq = 1 # 最小访问次数为1
阅读全文