Python 中的 LFU 缓存
假设我们想要设计和实现一个用于最少使用 (LFU) 缓存系统的数据结构。它应该支持以下操作 −
get(key) - 如果缓存中存在该键,则将使用它来获取该键的值,否则返回 -1。
put(key, value) - 如果键不存在,则将使用它来设置或插入该值。
当缓存达到其最大容量时,它应该在插入新元素之前使最不常用的元素无效。
因此,如果 LFUCache 以容量 2 初始化并调用这些方法 cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3); cache.get(2); cache.put(4, 4); cache.get(1); cache.get(3); cache.get(4); 那么输出将分别为 1,-1,1,-1,4。
为了解决这个问题,我们将遵循以下步骤 −
初始化程序将采用容量值
remain := capacity
least_freq := 1
node_for_freq := 一个根据插入顺序保存数据的映射
node_for_key := 一个新的映射
定义一个函数 _update() 。这将获取 key、value
x, freq := node_for_key[key]
从 node_for_freq[freq] 中删除与 key 对应的元素
如果 node_for_freq[least_freq] 的大小与 0 相同,则
least_freq := least_freq + 1
node_for_freq[freq+1, key] := value, freq+1
node_for_key[key] := value, freq+1
定义一个函数 get() 。这将获取密钥
如果 key not in node_for_key 为非零,则
返回 -1
value := node_for_key[key, 0]
_update(key, value)
返回值
定义一个函数 put() 。这将获取 key、value
如果 node_for_key 中的 key 非零,则
_update(key, value)
否则,
node_for_key[key] := value,1
node_for_freq[1, key] := value,1
如果 remain 与 0 相同,则
removed := 按先进先出顺序从 node_for_freq[least_freq] 中删除一个元素
从 node_for_key 中删除与 key 对应的元素已移除[0]
否则,
remain := remain - 1
least_freq := 1
示例
让我们看看下面的实现以便更好地理解 −
import collections class LFUCache: def __init__(self, capacity): self.remain = capacity self.least_freq = 1 self.node_for_freq = collections.defaultdict(collections.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 put(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.put(1, 1) cache.put(2, 2) print(cache.get(1)) cache.put(3, 3) print(cache.get(2)) cache.put(4, 4) print(cache.get(1)) print(cache.get(3)) print(cache.get(4))
输入
cache.put(1, 1) cache.put(2, 2) cache.get(1) cache.put(3, 3) cache.get(2) cache.put(4, 4) cache.get(1) cache.get(3) cache.get(4)
输出
1 -1 1 -1 4
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

