LRU算法 学习笔记

LRU算法是一种常见的页面置换算法,选择内存中最近最久未使用的页面予以淘汰,也就是根据数据的历史访问记录来淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

一般LRU实现使用链表维护,实现LRU算法的步骤有三步:

  • 新数据从链表头部插入
  • 当缓存命中时,此数据移动到链表头部
  • 当链表满时,将链表尾部的数据丢弃

img

当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。实现代价是命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。

如何使用JS实现?

使用数组模拟链表(后面要用Map替换掉降低复杂度),提供两个方法,一个用于加入某个kv值,但需要判断链表是否已满,这里我使用set标识,还有一种方法用于设定某个值被命中,也就是标记它为最新使用,我使用hit标识。hit方法需要根据值来找键,普通的数据结构需要O(n)的时间满足这个操作,但可以使用JavaScript ES6提供的Map,就可以降低为O(1),它既能保持键值对还能记住插入顺序。

那么提供一个数据结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
let LRUCache = function (capacity) {
this.capacity = capacity;
this.cache = new Map();
}

LRUCache.prototype.set = function (key, value) {
if (this.cache.has(key)) {
// 如果cache里已经有这个值了,那就做一次更新,相当于做了一次hit
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// 这里要打算往cache里加入新值,但需要提前判断容量,如果容量不够,就需要删除尾部
this.cache.delete(this.cache.keys().next().value);
}
this.cache.set(key, value);
}

LRUCache.prototype.hit = function (key) {
if (this.cache.has(key)) {
// hit的原理是先删除再新加入
this.cache.delete(key);
this.cache.set(key, this.cache.get(key));
return 1; // 表示命中成功,return啥随便你自己定
}
return -1; // 表示命中了个寂寞,return啥还是随便你自己定
}

可以用来解决LRU问题。

扩展LRU算法,详情参考:https://www.jianshu.com/p/d533d8a66795

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2023 Shawn Zhou
  • Hexo 框架强力驱动 | 主题 - Ayer
  • 访问人数: | 浏览次数:

感谢打赏~

支付宝
微信