cache替换

### 缓存替换算法与策略 #### LRU (Least Recently Used) LRU 是一种常见的缓存替换策略，其核心思想是移除最近最少使用的数据项。每当有新的数据加入到缓存中时，如果缓存已满，则会淘汰最久未被访问的数据项。这种方法假设过去很少使用的对象在未来也很少会被使用。 ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cache = OrderedDict() self.capacity = capacity def get(self, key: int) -> int: if key not in self.cache: return -1 value = self.cache.pop(key) self.cache[key] = value # Move accessed item to the end. return value def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.pop(key) elif len(self.cache) >= self.capacity: self.cache.popitem(last=False) # Remove least recently used item. self.cache[key] = value ``` #### FIFO (First In First Out) FIFO 策略按照进入顺序来决定哪些项目应该被淘汰。最早放入缓存中的条目将是第一个被删除的对象。这种方式实现简单，但在某些情况下可能不是最优的选择，因为它不考虑项目的实际使用频率[^1]。 #### LFU (Least Frequently Used) LFU 考虑的是每个缓存项的使用频次。当需要腾出空间时，LFU 将优先清除那些较少被请求的内容。这有助于保持更常用的数据始终存在于缓存之中。 ```python import heapq from collections import defaultdict class Node: def __init__(self, freq=0, keys=None): self.freq = freq self.keys = set() if keys is None else keys def add_key(self, key): self.keys.add(key) def remove_key(self, key): self.keys.discard(key) class LFUCache: def __init__(self, capacity: int): self.key_to_val = {} self.key_to_freq_node = {} self.min_freq = 0 self.cap = capacity self.freq_map = {0: Node()} def _update_frequency(self, key): node = self.key_to_freq_node[key] next_freq = node.freq + 1 if next_freq not in self.freq_map: new_node = Node(next_freq) self.freq_map[next_freq] = new_node next_node = self.freq_map[next_freq] del self.key_to_freq_node[key] next_node.add_key(key) self.key_to_freq_node[key] = next_node if not node.keys and node.freq == self.min_freq: self.min_freq += 1 def get(self, key: int) -> int: if key not in self.key_to_val: return -1 val = self.key_to_val[key] self._update_frequency(key) return val def put(self, key: int, value: int) -> None: if self.cap <= 0: return if key in self.key_to_val: self.key_to_val[key] = value self._update_frequency(key) return if len(self.key_to_val) >= self.cap: min_freq_node = self.freq_map[self.min_freq] evict_key = list(min_freq_node.keys)[0] min_freq_node.remove_key(evict_key) del self.key_to_val[evict_key] del self.key_to_freq_node[evict_key] self.key_to_val[key] = value self.freq_map.setdefault(1, Node()).add_key(key) self.key_to_freq_node[key] = self.freq_map[1] self.min_freq = 1 ``` #### ARC (Adaptive Replacement Cache) ARC 是一种自适应缓存管理器，它能够动态调整两个不同部分之间的大小比例——一个是用于存储最近频繁访问过的页面；另一个则是用来保存较早之前曾被读取过但仍有可能再次用到的信息。通过这种机制，可以更好地平衡短期和长期的需求变化。