Lru 和lfu的区别

### LRU 和 LFU 缓存置换算法的区别 #### 定义与工作原理 LRU (Least Recently Used) 是一种基于最近使用的频率来淘汰缓存项的策略。当缓存达到其容量上限时，会移除最长时间未被访问的数据项[^2]。 LFU (Least Frequently Used) 则关注的是数据项被访问的频次。即使某个条目很久之前就被加载到缓存中，只要它经常被请求，则不会轻易被淘汰；相反，那些很少被访问的项目会被优先考虑清除出去[^1]。 #### 实现机制 对于 **LRU** 来说，通常可以利用双向链表加上哈希映射的方式实现高效的查找、插入以及删除操作： ```python class LRUCache: def __init__(self, capacity: int): self.cache = {} self.capacity = capacity self.order = [] def get(self, key: str) -> any: if key not in self.cache: return None value = self.cache[key] # Move the accessed item to the end of order list. self.order.remove(key) self.order.append(key) return value def put(self, key: str, value: any) -> None: if len(self.cache) >= self.capacity and key not in self.cache: oldest_key = next(iter(self.cache)) del self.cache[oldest_key] elif key in self.cache: self.get(key) # Update its position. self.cache[key] = value self.order.append(key) ``` 而针对 **LFU**, 需要额外维护一个计数器或者字典用于跟踪各个键值对被访问次数，并且还需要能够快速找到具有最低频率的对象以便于替换： ```python from collections import defaultdict, OrderedDict class Node: def __init__(self, key=None, val=0, freq=0): self.key = key self.val = val self.freq = freq class LFUCache: def __init__(self, capacity: int): self.cap = capacity self.size = 0 self.min_freq = 0 self.k_f = {} # Key-to-Freq mapping self.f_k_v = defaultdict(OrderedDict) def _increase_frequency(self, node: 'Node'): f_kv = self.f_k_v[node.freq] k = node.key v = node.val del f_kv[k] new_node = Node(k, v, node.freq + 1) self.f_k_v[new_node.freq][k] = new_node self.k_f[k].freq += 1 if not f_kv and self.min_freq == node.freq: self.min_freq += 1 def get(self, key: int) -> int: if key not in self.k_f or self.cap <= 0: return -1 node = self.k_f[key] self._increase_frequency(node) return node.val def put(self, key: int, value: int) -> None: if self.cap <= 0: return if key in self.k_f: old_node = self.k_f[key] old_node.val = value self._increase_frequency(old_node) else: if self.size >= self.cap: evict_node = self.f_k_v[self.min_freq].popitem(last=False)[1] del self.k_f[evict_node.key] self.size -= 1 new_node = Node(key=key, val=value, freq=1) self.f_k_v[1][key] = new_node self.k_f[key] = new_node self.size += 1 self.min_freq = 1 ``` 这两种方法各有优劣，在实际应用中可根据具体需求选择合适的方案[^3]。

Lru（Least Recently Used）和Lfu（Least Frequently Used）都是缓存淘汰算法，但它们的淘汰规则不同。Lru算法淘汰最近最少使用的缓存数据，而Lfu算法淘汰使用频率最少的缓存数据。