LRU 算法在后端工程师面试中, 是一个比较常出现的题目, 这篇文章带大家一起, 理解 LRU 算法, 并最终用 Python 轻松实现一个基于 LRU 算法的缓存
缓存是什么
先看一张图, 当我们访问网页, 浏览器会给服务器发请求, 服务器会经过一系列的运算, 把页面返回给浏览器
当有多个浏览器同时访问的时候, 就会在短时间内发起多个请求, 而服务器对每一个请求都要进行一系列相同的操作重复工作不仅浪费资源, 还可能导致响应速度变慢
而缓存则可以把服务器返回的页面保存下来, 当有其他的浏览器再访问时候, 就不必劳服务器大驾, 直接由缓存返回页面为了保证响应速度, 缓存通常是基于比较昂贵的硬件, 比如 RAM, 这就决定了我们很难用大量的缓存把所有的页面都存下来, 当恰好没有缓存浏览器请求的页面时, 依然需要请求服务器由于缓存容量有限, 而数据量无限(互联网每天新产生的页面数无法估计), 就需要把好刚用在刀刃上, 缓存那些最有用的信息
LRU 是什么
LRU 是一种缓存淘汰算法(在 OS 中也叫内存换页算法), 由于缓存空间是有限的, 所以要淘汰缓存中不常用的数据, 留下常用的数据, 达到缓存效率的最大化 LRU 就是这样一种决定淘汰谁留下谁的算法, LRU 是 Least recently used 的缩写, 从字面意思最近最少使用, 我们就可以理解 LRU 的淘汰规则
LRU 的淘汰逻辑
我们用一张图来描述 LRU 的淘汰逻辑, 图中的缓存是一个列表结构, 上面是头结点下面是尾节点, 缓存容量为 8(8 个小格子):
有新数据 (意味着数据之前没有被缓存过) 时, 加入到列表头
缓存到达最大容量时, 需要淘汰数据多出来的数据, 此时淘汰列表尾部的数据
当缓存中有数据被命中, 则将数据移动到列表头部(相当于新加入缓存)
按上面的逻辑我们可以看到, 一个数据如果经常被访问就会不断地被移动到列表头部, 不会被淘汰出缓存, 而越不经常访问的数据, 越容易被挤出缓存
20 行 Python 代码实践 LRU
接下来我们用 Python 来实现一个采用 LRU 算法的缓存
从前面的文章中我们可以知道, 缓存简化下来就两个功能, 一个是往里装数据(缓存数据), 一个是往外吐数据(命中缓存), 所以我们的缓存对外只需要 put 和 get 两个接口就可以了
按照前面的示意图, 缓存内部我们只需要有一个列表 (list) 就可以实现 LRU 逻辑, 不过用列表虽然能实现逻辑, 但是在判断是否命中缓存时, 速度可能非常慢 (列表需要遍历才能知道数据有没有在里面) 在 Python 中, 我们可以用基于 hash 的结构, 比如字典 (dict) 或集合(set), 来快速判断数据是否存在, 解决列表实现的性能问题但是字典和集合又是没有顺序的, 如果能有一种既能排序, 又是基于 hash 存储的数据结构, 就好了
在 Python 的 collections 包中, 已经内置了这种实用的结构 OrderedDict,OrderedDict 是 dict 的子类, 但是存储在内部的元素是有序的(列表的特点)
解决了数据结构的问题, 我们可以直接上手写逻辑了, 代码如下:
- class LRUCache:
- def __init__(self, capacity):
- self.capacity = capacity
- self.queue = collections.OrderedDict()
- def get(self, key):
- if key not in self.queue:
- return -1 // 要找的数据不在缓存中返回 - 1
- value = self.queue.pop(key) // 将命中缓存的数据移除
- self.queue[key] = value // 将命中缓存的数据重新添加到头部
- return self.queue[key]
- def put(self, key, value):
- if key in self.queue: // 如果已经在缓存中, 则先移除老的数据
- self.queue.pop(key)
- elif len(self.queue.items()) == self.capacity:
- self.queue.popitem(last=False) // 如果不在缓存中并且到达最大容量, 则把最后的数据淘汰
- self.queue[key] = value // 将新数据添加到头部
下次面试在遇到 LRU 的题目, 是不是就胸有成竹了?
来源: https://juejin.im/post/5a9e6835f265da23937697ea