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那些事」,做全栈开发工程师

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180605B075CH00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券