在Python中实现最少使用的缓存的程序
假设我们要为最不常用(LFU)缓存系统实现数据结构。它应支持以下操作:
get(key)−如果密钥存在于高速缓存中,则这有助于获取密钥的值,否则返回-1。
set(key,value)−如果密钥不存在,将用于设置或插入值。
当缓存达到最大容量时,它应在插入新元素之前使最不常用的元素无效。
因此,如果使用容量2初始化LFUCache并调用这些方法cache.set(1,1);cache.set(2,2);cache.get(1);cache.set(3,3);cache.get(2);cache.set(4,4);cache.get(1);cache.get(3);cache.get(4);那么输出将分别为1,-1,1,-1,4。
为了解决这个问题,我们将遵循以下步骤-
初始化程序将获取容量值
保持:=容量
Minimum_freq:=1
node_for_freq:=一个根据插入顺序保存数据的映射
node_for_key:=一个新映射
定义一个功能_update()。这将需要关键,价值
x,freq:=node_for_key[key]
从node_for_freq[freq]中删除与键对应的元素
如果node_for_freq[least_freq]的大小等于0,则
minimum_freq:=Minimum_freq+1
node_for_freq[freq+1,key]:=值,freq+1
node_for_key[key]:=值,freq+1
定义一个功能get()。这将需要关键
如果不在node_for_key中的密钥为非零,则
返回-1
值:=node_for_key[key,0]
_update(key,value)
返回值
定义一个功能set()。这将需要关键,价值
如果node_for_key中的密钥为非零,则
_update(key,value)
除此以外,
保持:=保持−1
已删除:=按照FIFO顺序从node_for_freq[least_freq]中删除一个元素
node_for_key中的delete元素对应于已删除的键[0]
node_for_key[key]:=value,1
node_for_freq[1,键]:=值,1
如果保持等于0,则
除此以外,
Minimum_freq:=1
让我们看下面的实现以更好地理解-
示例
from collections import defaultdict, OrderedDict class LFUCache: def __init__(self, capacity): self.remain = capacity self.least_freq = 1 self.node_for_freq = defaultdict(OrderedDict) self.node_for_key = dict() def _update(self, key, value): _, freq = self.node_for_key[key] self.node_for_freq[freq].pop(key) if len(self.node_for_freq[self.least_freq]) == 0: self.least_freq += 1 self.node_for_freq[freq+1][key] = (value, freq+1) self.node_for_key[key] = (value, freq+1) def get(self, key): if key not in self.node_for_key: return −1 value = self.node_for_key[key][0] self._update(key, value) return value def set(self, key, value): if key in self.node_for_key: self._update(key, value) else: self.node_for_key[key] = (value,1) self.node_for_freq[1][key] = (value,1) if self.remain == 0: removed = self.node_for_freq[self.least_freq].popitem(last=False) self.node_for_key.pop(removed[0]) else: self.remain −= 1 self.least_freq = 1 cache = LFUCache(2) cache.set(1, 1) cache.set(2, 2) print(cache.get(1)) cache.set(3, 3) print(cache.get(2)) cache.set(4, 4) print(cache.get(1)) print(cache.get(3)) print(cache.get(4))
输入值
cache.set(1, 1) cache.set(2, 2) cache.get(1) cache.set(3, 3) cache.get(2) cache.set(4, 4) cache.get(1) cache.get(3) cache.get(4)输出结果
1 −1 1 −1 4