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