专栏首页Python私房菜面试不再怕,20行Python代码帮你搞懂LRU算法

面试不再怕,20行Python代码帮你搞懂LRU算法

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的子类,但是存储在内部的元素是有序的(列表的特点)。

解决了数据结构的问题,我们可以直接上手写逻辑了,代码如下:

 1class LRUCache:
 2
 3    def __init__(self, capacity):
 4        self.capacity = capacity
 5        self.queue = collections.OrderedDict()
 6
 7    def get(self, key):
 8        if key not in self.queue:
 9            return -1 // 要找的数据不在缓存中返回-1
10        value = self.queue.pop(key) // 将命中缓存的数据移除
11        self.queue[key] = value // 将命中缓存的数据重新添加到头部
12        return self.queue[key]
13
14
15    def put(self, key, value):
16        if key in self.queue: // 如果已经在缓存中,则先移除老的数据
17            self.queue.pop(key)
18        elif len(self.queue.items()) == self.capacity:
19            self.queue.popitem(last=False) // 如果不在缓存中并且到达最大容量,则把最后的数据淘汰
20        self.queue[key] = value // 将新数据添加到头部

下次面试在遇到LRU的题目,是不是就胸有成竹了?

本文分享自微信公众号 - Python私房菜(python-fans),作者:simpleapples

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用Pipfile代替reqirements.txt

    很多语言都提供了环境隔离的支持,例如nodejs的node_module,golang的go mod,python也有virtualenv和pyvenv等机制。...

    simpleapples
  • 简析Python中的四种队列

    在Python文档中搜索队列(queue)会发现,Python标准库中包含了四种队列,分别是queue.Queue / asyncio.Queue / mult...

    simpleapples
  • 60行Python代码,实现多线程PDF转Word

    工作中经常会遇到需要提取PDF文件中文字的情况,一个PDF还好,复制粘贴一下也花不了太多时间,如果需要把大量PDF转为Word,怎么办呢?

    simpleapples
  • 大型网站架构演变过程、大并发服务器架构

    大型网站架构演变过程: [Step1]web server与数据库分离 ? web动静资源分离 ? 静态请求:如html, js, css, img 动态请...

    s1mba
  • 大型网站架构演变过程、大并发服务器架构

    客户端(浏览器)缓存 前端页面缓存(squid) 页面片段缓存ESI(Edge Side Includes) 本地数据缓存

    bear_fish
  • 浏览器缓存机制剖析

    “缓存一直是前端优化的主战场,利用好缓存就成功了一半。本篇从HTTP请求和响应的头域入手,让你对浏览器缓存有个整体的概念。最终你会发现强缓存,协商缓存 和 启发...

    CSDN技术头条
  • NVelocity标签设置缓存的解决方案

      意外的问题总会让人措手不及,今天与大家分享的就是NVelocity设置缓存的问题,之前刚google了一下发现没什么太好的解决方案,希望在这能为需要的朋友找...

    Java中文社群_老王
  • ASP.NET 缓存(3)

    有2种方式来实现缓存部分页。 片段缓存:这种情况下,你把确定要缓存的内容,包裹在一个专用的用户控件里,然后只需要对这个控件做输出缓存就行。 post-c...

    py3study
  • 浏览器缓存机制剖析

    这是判断是否启用缓存的第一步。如果浏览器通过某些条件(条件之后再说)判断出来,ok现在这个缓存没有过期可以用,那么连请求都不会发的,直接是启用之前浏览器缓存下来...

    用户1263954
  • 缓存策略

    本文作者:IMWeb daihuimi 原文出处:IMWeb社区 未经同意,禁止转载 学习整理了web缓存的一些策略,如有不正确的地方,欢迎指正。 ?...

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券