Python中的LFU缓存
假设我们要设计和实现最不常用(LFU)缓存系统的数据结构。它应该支持以下操作-
get(key)–如果键存在于缓存中，它将用于获取键的值，否则返回-1。
put(key,value)–如果键不存在，它将用于设置或插入值。
当缓存达到最大容量时，它应在插入新元素之前使最不常用的元素无效。
因此，如果使用容量2初始化LFUCache并调用这些方法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。
为了解决这个问题，我们将遵循以下步骤-
初始化程序将获取容量值
保持：=容量
Minimum_freq：=1
node_for_freq：=一个根据插入顺序保存数据的映射
node_for_key：=一个新映射
定义一个函数_update()。这将需要关键，值
x，频率：=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（键，值）
返回值
定义一个功能put()。这将需要关键，值
node_for_key[key]：=value，1
node_for_freq[1，键]：=值，1
如果保持等于0，则
除此以外，
Minimum_freq：=1
已删除：=按照FIFO顺序从node_for_freq[least_freq]中删除一个元素
node_for_key中的delete元素对应于已删除的键[0]
保持：=保持-1
_update（键，值）
如果node_for_key中的键不为零，则
除此以外，
例
让我们看下面的实现以更好地理解-
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