Python 中的 LFU 缓存

pythonserver side programmingprogramming更新于 2025/9/4 15:08:17

假设我们想要设计和实现一个用于最少使用 (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

相关文章


有用资源