十分钟看懂JS的LRU Cache 算法(上)

我心飞翔 分类:javascript

前文

leetcode上刷题时,遇到一个难得能够直接在前端用得上的算法思路(说实话,前端能用到算法的场景真的少的可怜),所以抓住和大家做一个分享。恰逢金三银四求职季,多掌握一个知识点,多一份进大厂打工的希望!加油,打工人!

图片

正文

简介

关于缓存,有个常见的例子是,当用户访问不同站点时,浏览器需要缓存在对应站点的一些信息,这样当下次访问同一个站点的时候,就可以使访问速度变快(因为一部分数据可以直接从缓存读取)。 但是想想房价都那么高了,内存空间同样也是珍贵的(呜呜呜),所以必须有一些规则来管理缓存的使用,而LRU(Least Recently Used) Cache就是其中之一,直接翻译就是**“最不经常使用的数据,重要性是最低的,应该优先删除”。**这个规则还满人性化的,经常访问的,肯定相对更重要。

需求分析

假设我们要实现一个简化版的这个功能,遵循下隔壁后端大佬同事的crud原则,先整理下需求:

  1. 需要提供put方法,用于写入不同的缓存数据,假设每条数据形式是{'域名','info'},例如{'https://segmentfault.com': '一些关键信息'}(如果是同一站点重复写入,就覆盖);
  2. 当缓存达到上限时, 调用put写入缓存之前, 要删除最近最少使用的数据
  3. 提供get方法,用于读取缓存数据,同时需要把被读取的数据,移动到最近使用数据 ;
  4. 考虑到读取性能,希望get操作的复杂度是O(1)(简单理解就是,读取缓存时不能去遍历所有数据)

数据选型

首先题目里很明显的提到了,需要能够标记数据的插入或使用顺序, 所以肯定不能简单使用object实现,需要借助数组,或者es6MapSet实现(MapSet数据遍历是有序的,遍历顺序即插入顺序);

其次需要实现O(1)复杂度,那就也无法用单纯使用数组来实现,所以可以考虑的只有MapSet,那么最后再考虑下数据重复性的问题,会发现这道题不太需要考虑这个场景,所以我们可以先使用Map来实现。

由于Map的特性是:新插入的数据排在后面,旧数据放在前面, 所以我们只要专注于维持这个逻辑就好了:

  • 如果遇到要删除数据,则优先从前面删除, 因为最前面的必定是最不常用数据;
  • 如果读取某条数据,则应该把数据放到末尾,保证该数据变为最近使用数据;

简单用几个图来表示对应的场景:

空间未满时插入数据:

图片

空间已满时插入数据:

图片

读取数据:

图片

算法实现

接下来就可以一步步是实现代码了,首先是最基本的 构造函数:

// 第一步代码
class LRUCache {
    constructor(n){
        this.size = n; // 初始化最大缓存数据条数n
        this.data = new Map(); // 初始化缓存空间map
    }
}
 

接下来是put方法,put方法要处理3个逻辑:

  1. 如果待写入的域名,已存在于内存之中,直接更新数据并移动到末尾;
  2. 如果当前未达到缓存数量上限,直接写入新数据;
  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种逻辑:

  1. 根据给定的key,查找是否有对应的信息,若不存在则返回false;
  2. 若第一步结果存在,则把被访问数据移动到末尾
// 第一步代码
class LRUCache {
    constructor(n){
        this.size = n; // 初始化最大缓存数据条数n
        this.data = new Map(); // 初始化缓存空间map
    }
// 第二步代码
    put(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

小结

到这里其实代码就结束了,也是一个相对轻松的一篇文章,估计花个十分钟稍微看看也就大概掌握了,当然,细心的同学可能留意到了,标题里有个(上)字,意味着还有个(下)篇,因为本文的思路主要借助了es6Map的特点和优势来完成,有点取巧。而下一篇里会介绍只用es5来处理这个场景。确切的说,下一篇会介绍更加正规和通用的处理方案

总结

最近专栏的粉丝涨的很快,也陆续收到一些读者的反馈,有点受宠若惊,写的东西能得到大家的认可,心里是很开心。也希望大家对于喜爱的文章,能够点赞和收藏,这样也能一定程度上给我个反馈,哪些文章写的较好,哪些文章还有不足,或者对于行文风格和内容有任何意见的,都欢迎私信交流。

image.png

最后依然是惯例,RingCentral目前在杭州也设置了办公点,而且可以申请长期远程办公,告别996,工作生活两不误,有兴趣的同学可以私信咨询(主页有联系方式),可以免费帮忙内推~

回复

我来回复
  • 暂无回复内容