Python 标准库之 LRU 缓存实现学习

来源：0xE8551CCB 出处：

https://www.jianshu.com/p/f7258e266cc6

引言

LRU (Least Recently Used) 是缓存置换策略中的一种常用的算法。当缓存队列已满时，新的元素加入队列时，需要从现有队列中移除一个元素，LRU 策略就是将最近最少被访问的元素移除，从而腾出空间给新的元素。

研读 Python 3.6 中 源码可以发现，它是通过一个双向链表加字典实现 LRU 缓存的。下面就来学习一下这个工具函数的实现。

应用

在深入学习该函数之前，我们可以看看它的常规用法。合理使用缓存，可以有效地减少一些长耗时函数调用的次数，从而大大提高整体效率。

看一个经典的例子，即斐波那契函数的递归实现：

众所周知，当需要计算的 N 比较大时，上述函数计算会非常缓慢。我们先来分析下为何上述函数在计算较大 N 时会耗时很久，以便了解为何可以使用缓存机制来提高效率。以下是 N 为 5 时上述函数递归调用树状图：

显然，在调用过程中，有多次重复计算。于是，我们可以添加 装饰器缓存已经计算过的数据，从而改善递归版的斐波那契函数：

当 N = 32 时，可以对比下两个版本计算耗时，可以看到计算效率的提升是惊人的：

当然啦，事实上我们还有更好的方法来实现斐波那契函数（时间复杂度 O(n)），示例如下：

貌似跑偏了，接下来赶紧进入正题，窥探下 是如何实现 LRU 缓存的。

LRU 缓存实现

查看源码，可以看到 LRU 缓存是在函数 中实现的。本节只研究 LRU 是如何在其中实现的，所以，下面的源码中移除了无关的代码。

根据上述源码，我们将分为如下几个节点来分析 LRU 缓存状态（链表的状态）：

初始状态

新增缓存结果（缓存空间未满）

新增缓存结果（缓存空间已满）

命中缓存

缓存初始状态

初始状态下， 为空，并且存在一个指向自身的根指针，示意图如下：

新增缓存结果（空间未满）

接下来，我们向缓存中新增几个节点 K1, K2, K3, K4，对应的链表状态和 状态如下图所示：

新增缓存结果（空间已满）

此时，我们假设缓存已经满了，当我们需要增加新节点 K5 时，需要从原先的链表中“移除”节点 K1，则更新后的示意图如下：

缓存命中

假设此时缓存命中 K2，则会定位到 K2 节点，并返回该节点的值，同时会调整环形链表，将 K2 移动到 root 节点的右侧（即链表的前边），则更新的示意图如下：

总结

中巧妙使用了环形双向链表来实现 LRU 缓存，通过在缓存命中时，将节点移动到队列的前边的方式，从而间接地记录了最近经常访问的节点。当缓存空间满了后，会自动“移除”位于环形队列尾部最近命中频率最低的节点，从而为新增缓存节点腾出了空间。

参考

Cache replacement policies: LRU

The Python Standard Library: lru_cache

（完）

看完本文有收获？请转发分享给更多人

关注「Python那些事」，做全栈开发工程师