如何在Python中实现一个高性能的LRU-K淘汰算法？-Python教程-PHP中文网

标准functools.lru_cache实现的是lru而非lru-k，因lru-k需记录每键最近k次访问时间戳并按第k次时间淘汰，而lru_cache仅跟踪最后一次访问；直接修改lru_cache无法满足lru-k的k次历史约束与o(1)淘汰定位要求。

如何在python中实现一个高性能的lru-k淘汰算法？

为什么标准`functools.lru_cache`不等于LRU-K

标准lru_cache实现的是LRU（最近最少使用），只看最后一次访问时间；而LRU-K需要记录每个键的**最近K次访问时间戳**，淘汰时优先剔除“第K次访问最久远”的项。这导致两者逻辑完全不同：LRU-K能更好抵抗扫描类突发访问（比如一次全表遍历把热点数据挤出缓存），但代价是内存开销翻K倍、插入/查询变慢。

如果你直接拿lru_cache改maxsize或加计数器，结果只会得到一个行为不可控的伪LRU-K——它既不满足K次历史约束，也无法在O(1)内定位待淘汰项。

用`heapq` + `dict`组合实现可淘汰的LRU-K核心结构

关键不是堆本身，而是如何让堆里每个元素能被快速更新和标记失效。标准做法是“懒删除”+“双字典”：

self._access_history：映射key → deque，存最近最多K个timestamp（用time.time()或单调递增序号）
self._heap：最小堆，存元组(kth_timestamp, key, version)，其中version用于检测过期
self._versions：映射key → int，每次更新access_history[key]时自增，确保旧堆项能被识别为失效

每次get(key)时，先push新时间戳进deque，超长则pop左端；再往堆里推新元组，并更新version。淘汰时不断heappop直到拿到一个version匹配的项。

示例片段（简化版）：

Python数据分析(免费版)

提供Python数据清洗、统计分析与可视化建议，覆盖业务报表与科研数据的快速处理流程。

下载

import heapq
from collections import defaultdict, deque
<p>class LRUKCache:
def <strong>init</strong>(self, k=2, maxsize=128):
self.k = k
self.maxsize = maxsize
self._data = {}
self._access_history = defaultdict(lambda: deque(maxlen=k))
self._heap = []
self._versions = defaultdict(int)
self._next_version = 0</p><pre class="brush:python;toolbar:false;">def _push_access(self, key):
    self._access_history[key].append(time.time())
    self._versions[key] += 1
    ver = self._versions[key]
    # 只取第k次访问时间（不足k次则取最早一次）
    ts = self._access_history[key][0] if len(self._access_history[key]) < self.k else self._access_history[key][0]
    heapq.heappush(self._heap, (ts, key, ver))

def get(self, key):
    if key not in self._data:
        return None
    self._push_access(key)
    return self._data[key]

`delitem`和淘汰触发时机必须手动控制

Python的dict没有容量满时自动回调机制，所以不能依赖__setitem__内部判断是否超限。必须显式检查并调用淘汰逻辑：

在set(key, value)末尾加if len(self._data) > self.maxsize: self._evict()
_evict()里用懒删除：循环heappop，对每个弹出项检查ver == self._versions[key]且key in self._data，匹配才真正删
别忘了删self._data[key]、清空self._access_history[key]、不重置_versions[key]（避免版本号复用）