用 Python 实现最不常用缓存系统

假设我们想要实现一个最不常用（LFU）缓存系统的数据结构。它应该支持以下操作：

• get(key) – 如果键存在于缓存中，则获取键的值，否则返回-1。

• set(key, value) – 如果键不存在，则用于设置或插入值。

当缓存达到最大容量时，它应使最不经常使用的元素失效，然后插入新元素。因此，如果 LFUCache 以容量 2 初始化并调用这些方法 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。

为了解决这个问题，我们将遵循以下步骤：

• 初始化程序将获取容量值

• remain：=容量

• least_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相同，则

  • least_freq：=least_freq +1
• node_for_freq[freq+1，key]：=value、freq+1

• node_for_key[key]：=value、freq+1

• 定义一个函数get()。这将获取密钥

• 如果键不在node_for_key中，则非零，则

  • 返回-1
• value：=node_for_key[key，0]

• _update(key，value)

• 返回值

• 定义一个函数set()。这将获取密钥、值

• 如果键在node_for_key中，则非零，则

  • _update(key，value)
• 否则，
  • node_for_key[key]：=value，1

  • node_for_freq[1，key]：=value，1

  • 如果remain与0相同，则

    • removed：=按顺序从fifo中删除node_for_freq[least_freq]中的一个元素

    • 删除node_for_key对应于删除[0]的密钥的元素

  • 否则，

    • remain：=remain-1
  • least_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