前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python 标准库之 LRU 缓存实现学习

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

作者头像
IT派
发布2018-07-30 11:43:33
1.2K0
发布2018-07-30 11:43:33
举报
文章被收录于专栏:IT派

引言

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

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

应用

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

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

代码语言:javascript
复制
def fibonacci(n):
 if n == 0:
 return 0
 if n == 1:
 return 1

 return fibonacci(n - 1) + fibonacci(n - 2)

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

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

代码语言:javascript
复制
@lru_cache()
def fibonacci(n):
 if n == 0:        return 0
 if n == 1:        return 1

 return fibonacci(n - 1) + fibonacci(n - 2)

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

代码语言:javascript
复制
fibonacci(32) = 2178309

# 没有加缓存的递归版本
Elapsed time: 1497.54ms

# 添加缓存的递归版本
Elapsed time: 0.16ms

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

代码语言:javascript
复制
def fibonacci_fast(n):
    a, b = 0, 1
 for _ in range(n):
        a, b = a + b, a    
 return a

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

LRU 缓存实现

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

代码语言:javascript
复制
def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
 # 所有 LRU 缓存元素共享的常量:
    sentinel = object()  # 特殊标记,用来表示缓存未命中
    make_key = _make_key  # 根据函数参数生成缓存 key

 #
 # ---------------------------------
 # | PREV | DATA(KEY+RESULT) | NEXT|
 # ---------------------------------
 #
    PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # 链表各个域

 # 存放 key 到 node 的映射
    cache = {}
    full = False
    cache_get = cache.get
    lock = RLock()  # 链表更新不是线程安全的,所以需要加锁
    root = []  # 关键:环形双向链表
 # 根节点两侧分别是访问频率较高和较低的节点
    root[:] = [root, root, None, None]  # 初始根节点(相当于一个空的头节点)

 def wrapper(*args, **kwds):
 nonlocal root, full
        key = make_key(args, kwds, typed)
 with lock:
            link = cache_get(key)
 if link is not None: # 缓存命中
 # 将被访问的节点移动到环形链表的前面(即 root 的前边)
                link_prev, link_next, _key, result = link
                link_prev[NEXT] = link_next
                link_next[PREV] = link_prev
                last = root[PREV]
                last[NEXT] = root[PREV] = link
                link[PREV] = last
                link[NEXT] = root
 return result

 # 缓存未命中,调用用户函数生成 RESULT
        result = user_function(*args, **kwds)
 with lock:
 if key in cache:
 # 考虑到此时锁已经释放,而且 key 已经被缓存了,就意味着上面的
 # 节点移动已经做了,缓存也更新了,所以此时什么都不用做。
 pass
 elif full: # 新增缓存结果,移除访问频率低的节点
 # 下面的操作是使用 root 当前指向的节点存储 KEY 和 RESULT
                oldroot = root
                oldroot[KEY] = key
                oldroot[RESULT] = result
 # 接下来将原 root 指向的下一个节点作为新的 root,
 # 同时将新 root 节点的 KEY 和 RESULT 清空,这样
 # 使用频率最低的节点结果就从缓存中移除了。
                root = oldroot[NEXT]
                oldkey = root[KEY]
                oldresult = root[RESULT]
                root[KEY] = root[RESULT] = None
 del cache[oldkey]
                cache[key] = oldroot
 else: # 仅仅新增缓存结果
 # 新增节点插入到 root 节点的前面
                last = root[PREV]
                link = [last, root, key, result]
                last[NEXT] = root[PREV] = cache[key] = link
                full = (len(cache) >= maxsize)

 return result

 return wrapper

根据上述源码,我们将分为如下几个节点来分析 LRU 缓存状态(链表的状态):

  1. 初始状态
  2. 新增缓存结果(缓存空间未满)
  3. 新增缓存结果(缓存空间已满)
  4. 命中缓存

缓存初始状态

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

新增缓存结果(空间未满)

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

新增缓存结果(空间已满)

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

缓存命中

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

总结

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

参考

  • Cache replacement policies: LRU
  • The Python Standard Library: lru_cache
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-06-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 IT派 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 引言
  • 应用
  • LRU 缓存实现
    • 缓存初始状态
      • 新增缓存结果(空间未满)
        • 新增缓存结果(空间已满)
          • 缓存命中
          • 总结
          • 参考
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档