十分钟用JS写出LRU Cache 算法
SegmentFault
共 3125字,需浏览 7分钟
· 2021-03-30
作者:安歌
来源:SegmentFault 思否社区
简介
关于缓存,有个常见的例子是,当用户访问不同站点时,浏览器需要缓存在对应站点的一些信息,这样当下次访问同一个站点的时候,就可以使访问速度变快(因为一部分数据可以直接从缓存读取)。但是想想房价都那么高了,内存空间同样也是珍贵的(呜呜呜),所以必须有一些规则来管理缓存的使用,而LRU(Least Recently Used) Cache就是其中之一,直接翻译就是“最不经常使用的数据,重要性是最低的,应该优先删除”。这个规则还蛮人性化的,经常访问的,肯定相对更重要。
需求分析
假设我们要实现一个简化版的这个功能,遵循下隔壁后端大佬同事的crud
原则,先整理下需求:
需要提供 put
方法,用于写入不同的缓存数据,假设每条数据形式是{'域名','info'}
,例如{'https://segmentfault.com': '一些关键信息'}
(如果是同一站点重复写入,就覆盖);当缓存达到上限时, 调用 put
写入缓存之前, 要删除最近最少使用的数据;提供 get
方法,用于读取缓存数据,同时需要把被读取的数据,移动到最近使用数据 ;考虑到读取性能,希望 get
操作的复杂度是O(1)
(简单理解就是,读取缓存时不能去遍历所有数据)
数据选型
首先题目里很明显的提到了,需要能够标记数据的插入或使用顺序, 所以肯定不能简单使用object实现,需要借助数组,或者es6
的Map
和Set
实现(Map
和Set
数据遍历是有序的,遍历顺序即插入顺序);
其次需要实现O(1)
复杂度,那就也无法用单纯使用数组来实现,所以可以考虑的只有Map
和Set
,那么最后再考虑下数据重复性的问题,会发现这道题不太需要考虑这个场景,所以我们可以先使用Map
来实现。
由于Map
的特性是:新插入的数据排在后面,旧数据放在前面, 所以我们只要专注于维持这个逻辑就好了:
如果遇到要删除数据,则优先从前面删除, 因为最前面的必定是最不常用数据; 如果读取某条数据,则应该把数据放到末尾,保证该数据变为最近使用数据;
简单用几个图来表示对应的场景:
空间未满时插入数据:
算法实现
// 第一步代码
class LRUCache {
constructor(n){
this.size = n; // 初始化最大缓存数据条数n
this.data = new Map(); // 初始化缓存空间map
}
}
put
方法,put
方法要处理3个逻辑:如果待写入的域名,已存在于内存之中,直接更新数据并移动到末尾; 如果当前未达到缓存数量上限,直接写入新数据; 如果当前已经达到缓存数量上限, 要先删除最不经常使用的数据,再写入数据;
// 第一步代码
class LRUCache {
constructor(n){
this.size = n; // 初始化最大缓存数据条数n
this.data = new Map(); // 初始化缓存空间map
}
// 第二步代码
put(domain, info){
if(this.data.has(domain)){
this.data.delete(domain); // 移除数据
this.data.set(domain, info)// 在末尾重新插入数据
return;
}
if(this.data.size >= this.size) {
// 删除最不常用数据
const firstKey= this.data.keys().next().value; // 不必当心data为空,因为this.size 一般不会取0,满足this.data.size >= this.size时,this.data自然也不为空。
this.data.delete(firstKey);
}
this.data.set(domain, info) // 写入数据
}
}
get
方法了,get
方法同样也要处理2种逻辑:根据给定的 key
,查找是否有对应的信息,若不存在则返回false;若第一步结果存在,则把被访问数据移动到末尾;
// 第一步代码
class LRUCache {
constructor(n){
this.size = n; // 初始化最大缓存数据条数n
this.data = new Map(); // 初始化缓存空间map
}
// 第二步代码
set(domain, info){
if(this.data.size >= this.size) {
// 删除最不常用数据
const firstKey= [...this.data.keys()][0];// 次数不必当心data为空,因为this.size 一般不会取0,满足this.data.size >= this.size时,this.data自然也不为空。
this.data.delete(firstKey);
}
this.data.set(domain, info) // 写入数据
}
// 第三步代码
get (domain) {
if(!this.data.has(domain)){
return false;
}
const info = this.data.get(domain); //获取结果
this.data.delete(domain); // 移除数据
this.data.set(domain, info); // 重新添加该数据
return info;
}
}
n
。小结
es6
中Map
的特点和优势来完成,有点取巧。而下一篇里会介绍只用es5
来处理这个场景。确切的说,下一篇会介绍更加正规和通用的处理方案评论
JS的这些新特性,你都用过么?
大厂技术 高级前端 Node进阶点击上方 程序员成长指北,关注公众号回复1,加入高级Node交流群作为一门不断演进的语言,JavaScript每年都会引入新特性。这些特性的加入,能够帮助我们编写更加简洁、高效、易于维护的代码。然而,并非所有新特性
程序员成长指北
1
用 Shader 实现旗帜飘扬动画效果
我觉得对于刚入门 3D 编程的朋友来说,如果能够完成代码创建模型数据->创建材质->编写Shader动画这一系列,想必会有满满的成就感。今天就用 Cocos Creator 的 utils.MeshUtils.createMesh 接口,带大家感受一下这个流程。这个流程不仅可以用于新手学
COCOS
2
用 R Bookdown 做本书,上线
我的写作基础设施:1、Typora2、Cloudflare R23、Picgo4、Obsidian5、GitHub6、mdnice本合集会一一介绍上述工具的安装、配置、使用等等还会介绍:服务器配置GitHub Pages、Cloudflare Pages、Vercel 的使用用 Jekyll、Boo
机器学习算法与Python实战
0
我用这10招,能减少了80%的BUG
将Python客栈设为“星标⭐”第一时间收到最新资讯前言对于大部分程序员来说,主要的工作时间是在开发和修复BUG。有可能修改了一个BUG,会导致几个新BUG的产生,不断循环。那么,有没有办法能够减少BUG,保证代码质量,提升工作效率?答案是肯定的。如果能做到,我们多出来的时间,多摸点鱼,做点自己喜欢
Python客栈
0
面试官:限流的常见算法有哪些?
限流的实现算法有很多,但常见的限流算法有三种:计数器算法、漏桶算法和令牌桶算法。1.计数器算法计数器算法是在一定的时间间隔里,记录请求次数,当请求次数超过该时间限制时,就把计数器清零,然后重新计算。当请求次数超过间隔内的最大次数时,拒绝访问。计数器算法的实现比较简单,但存在“突刺现象”。突刺现象是指
Stephen
0
985 本硕,秋招上岸阿里算法岗!
↓推荐关注↓节前,我们星球举办了技术&面试交流会,邀请了一些互联网大厂好友以及今年参加社招和校招面试的同学。会上探讨了一系列热门话题,包括大模型发展趋势、算法落地实践、面经总结,以及如何做好面试准备和应对常见考点。基于经验交流与实战经验,我们总结如下:《机器学习算法面试宝典》1.0 发布!今
Python学习与数据挖掘
0
是谁还在坚持用 QQ?腾讯回应:好冷漠...
转自:电脑报近日,“仍有5亿人坚持用QQ”的话题登上微博热搜,引发网友热议。根据腾讯财报,截至2023年第三季度,QQ智能终端月活跃用户数为5.58亿,仅占微信四成。但换个角度看,作为一款25岁的元老级社交应用,QQ破5亿的月活仍然是很多社交App羡慕的存在,超过了微博和知乎总和。只是在用户增量上,
dotNET全栈开发
10
Java版【数据结构与算法】的天花板,收藏好,慢慢看
Java 版数据结构与算法来了,堪称 java 版数据结构与算法的天花板,需要学数据结构与算法的,刷这套就可以了,目录如下,文末附教程地址。基础数据结构-001-二分查找-算法描述基础数据结构-002-二分查找-算法实现基础数据结构-003-二分查找-问题1-循环条件基础数据结构-004-二分查找-
路人甲Java
0