Python LFU最近很少使用的实现

内存缓存是软件或硬件的一个元素，它将经常访问的数据存储在一个方便的位置。缓存用于通过减少访问数据所需的能量来改善系统性能。内存容量决定了缓存可以存储多少数据。当内存缓存已满时，必须驱逐一些数据，以便为新数据提供空间。

此外，还有世界将要结束的事实。最不经常使用 (LFU) 缓存存储替换策略是其中之一。LFU 缓存中的每个项目都有一个消费计数，表示该项目被访问的次数。当内存缓存已满时，使用最少的项目将被删除。这种方法基于一个前提，即不经常使用的项目在将来会更少地使用。

可以使用允许快速项查找、插入和删除的数据结构来实现 LFU 缓存。字典（或哈希表）是此任务的一个很好选择。以下是如何在 Python 中使用字典实现 LFU 缓存的方法。

class LFUCache:
   def __init__(self, capacity: int):
      self.capacity = capacity
      self.cache = {}  # Dictionary to store the items in the cache
      self.counts = {}  # Dictionary to store the usage count of each item

   def get(self, key: int) -> int:
      if key in self.cache:
         # Increment the usage count of the item
         self.counts[key] += 1
         return self.cache[key]
      else:
         return -1

   def put(self, key: int, value: int) -> None:
      if self.capacity == 0:
         return

      if key in self.cache:
         # Update the value of the item and increment its usage count
         self.cache[key] = value
         self.counts[key] += 1
      else:
         if len(self.cache) >= self.capacity:
            # Evict the item with the lowest usage count
            min_count = min(self.counts.values())
            items = [k for k, v in self.counts.items() if v == min_count]
            del self.cache[items[0]]
            del self.counts[items[0]]
         # Add the new item to the cache with a usage count of 1
         self.cache[key] = value
         self.counts[key] = 1

cache = LFUCache(2)  # Create an LFU cache with capacity 2
cache.put(1, 1)  # Add key 1 with value 1 to the cache
cache.put(2, 2)  # Add key 2 with value 2 to the cache
print(cache.get(1))  # Output: 1
cache.put(3, 3)  # Add key 3 with value 3 to the cache, evicting key 2
print(cache.get(2))  # Output: -1 (key 2 is no longer in the cache)
print(cache.get(3))  # Output: 3
cache.put(4, 4)  # Add key 4 with value 4 to the cache, evicting key 1
print(cache.get(1))  # Output: -1 (key 1 is no longer in the cache)
print(cache.get(3))  # Output: 3
print(cache.get(4))  # Output: 4

输出

初始化命令

__init__ 方法创建两个字典： ‘self.cache’ 用于保存缓存中的项目和 ‘self.counts’ 用于保留每个项目的使用计数。

获取命令

‘get’ 方法在缓存中搜索指定的键，如果找到，则增加项目的使用计数并转换其值。如果找不到键，则函数返回 ‘-1’ 。

放置命令

‘put’ 方法在缓存中添加或修改键和值的组合。如果键已经存在于缓存中，则更新项的值并增加其使用计数。如果键在缓存中不存在，则添加键值对，如果内存缓存已满，则删除与最低使用计数的项。使用 ‘min’ 操作来确定在 ‘self.counts’ 中具有最低消耗计数的项，然后利用结果知识找出具有该使用计数的 ‘self.cache’ 中的所有项。然后，删除项列表中的第一项。

这种实现提供了一种高效的实现方法。最后，当存储空间已满时，LFU缓存使用基于带宽的删除规则来确定要删除的项。当项的缓存已满，并且需要一个新项时，将删除使用计数最低的项目。这保证了缓存始终包含最常用的项目，可以提高缓存命中率和性能。

LFU缓存实现使用哈希表和优先级队列数据结构来高效地维护缓存及其使用计数。