面试不再怕,20行Python代码帮你搞懂LRU算法
LRU算法在后端工程师面试中,是一个比较常出现的题目,这篇文章带大家一起,理解LRU算法,并最终用Python轻松实现一个基于LRU算法的缓存。
缓存是什么
先看一张图,当我们访问网页,浏览器会给服务器发请求,服务器会经过一系列的运算,把页面返回给浏览器。
当有多个浏览器同时访问的时候,就会在短时间内发起多个请求,而服务器对每一个请求都要进行一系列相同的操作。重复工作不仅浪费资源,还可能导致响应速度变慢。
LRU是什么
LRU的淘汰逻辑
我们用一张图来描述LRU的淘汰逻辑,图中的缓存是一个列表结构,上面是头结点下面是尾节点,缓存容量为8(8个小格子):
- 有新数据(意味着数据之前没有被缓存过)时,加入到列表头
- 缓存到达最大容量时,需要淘汰数据多出来的数据,此时淘汰列表尾部的数据
- 当缓存中有数据被命中,则将数据移动到列表头部(相当于新加入缓存)
按上面的逻辑我们可以看到,一个数据如果经常被访问就会不断地被移动到列表头部,不会被淘汰出缓存,而越不经常访问的数据,越容易被挤出缓存。
20行Python代码实践LRU
下次面试在遇到LRU的题目,是不是就胸有成竹了?
关注后私信【Python面试】获取Python面试真题一份,希望能够对大家找工作有所帮助!
相关推荐
YENCSDN 2020-11-17
lsjweiyi 2020-11-17
houmenghu 2020-11-17
Erick 2020-11-17
HeyShHeyou 2020-11-17
以梦为马不负韶华 2020-10-20
lhtzbj 2020-11-17
夜斗不是神 2020-11-17
pythonjw 2020-11-17
dingwun 2020-11-16
lhxxhl 2020-11-16
坚持是一种品质 2020-11-16
染血白衣 2020-11-16
huavhuahua 2020-11-20
meylovezn 2020-11-20
逍遥友 2020-11-20
weiiron 2020-11-16