LRU算法详解
什么是LRU算法
就是⼀种缓存淘汰策略。计算机的缓存容量有限,如果缓存满了就要删除⼀些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么⽤的缓存,⽽把有⽤的数据继续留在缓存⾥,⽅便之后继续使⽤。LRU 缓存淘汰算法就是⼀种常⽤策略。LRU 的全称是 Least Recently Used,也就是淘汰掉最近最久未使用的缓存。
算法思路
⾸先要接收⼀个 capacity 参数作为缓存的最⼤容量,然后实现两个 API,⼀个是 put(key, val) ⽅法存⼊键值对,另⼀个是 get(key) ⽅法获取 key 对应的 val,如果 key 不存在则返回-1。注意哦,get 和 put ⽅法必须都是 O(1) 的时间复杂度,我们举个具体例⼦,来看看 LRU 算法怎么⼯作。
/* 缓存容量为 2 */
const cache = new LRUCache(2);
cache.put(1, 1);
// cache = [{1: 1}]
cache.put(2, 2);
// cache = [{2: 2}, {1: 1}]
cache.get(1); // 返回 1
// cache = [{1: 1}, {2: 2}]
// 解释:因为最近访问了键 1,所以提前⾄队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [{3: 3}, {1: 1}]
// 解释:缓存容量已满,需要删除内容空出位置,优先删除久未使⽤的数据,也就是队尾的数据,然后把新的数据插⼊队头
cache.get(2); // 返回 -1 (未找到)
// cache = [{3: 3}, {1: 1}]
cache.put(1, 4);
// cache = [{1: 4}, {3: 3}]
// 解释:键 1 已存在,把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头
复制代码
算法设计
分析上⾯的操作过程,要让 put 和 get ⽅法的时间复杂度为 O(1),我们可以总结出 cache 这个数据结构必要的条件:查找快,插⼊快,删除快,有顺序之分。所以我们不能使用数组去保存缓存,因为数组的查需要O(n),这里我们选择Map
,为什么选择 Map
结构,我们来分析一下:
可以通过map.keys().next().value
来获取第一个的键值,map.set()
操作类似数组的push
操作,将值保存在最前面的位置,而且删除缓存也可以直接使用delete(key)方法,满足O(1)
代码实现
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
}
get(key) {
let val = this.map.get(key);
if (typeof val === 'undefined') { return -1 }
// 重新计算位置
this.map.delete(key);
this.map.set(key, val);
return val
}
put(key, val) {
// 如果已经有这个key值,则更新
if(this.map.has(key)) {
this.map.delete(key);
}
this.map.set(key, val);
// 删除超出的key
let keys = this.map.keys()
while (this.map.size > this.capacity) {
this.map.delete(keys.next().value)
}
}
}
复制代码
通过get方法获取缓存的时候,如果命中了,就需要把命中的缓存放到第一个位置。在 put 方法里面,如果缓存超出了容量,通过map.keys.next().value
获取到最久未使用的缓存的key,进行删除。
实际运用
在Vue的keep-alive
组件中就用了这个算法,我们可以来分析一下keep-alive
的原理
export default {
name: "keep-alive",
// 抽象组件属性 ,它在组件实例建立父子关系的时候会被忽略,发生在 initLifecycle 的过程中
abstract: true,
props: {
// 被缓存组件
include: patternTypes,
// 不被缓存组件
exclude: patternTypes,
// 指定缓存大小
max: [String, Number]
},
created() {
// 初始化用于存储缓存的 cache 对象
this.cache = Object.create(null);
// 初始化用于存储VNode key值的 keys 数组
this.keys = [];
},
destroyed() {
for (const key in this.cache) {
// 删除所有缓存
pruneCacheEntry(this.cache, key, this.keys);
}
},
mounted() {
// 监听缓存(include)/不缓存(exclude)组件的变化
// 在变化时,重新调整 cache
// pruneCache:遍历 cache,如果缓存的节点名称与传入的规则没有匹配上的话,就把这个节点从缓存中移除
this.$watch("include", val => {
pruneCache(this, name => matches(val, name));
});
this.$watch("exclude", val => {
pruneCache(this, name => !matches(val, name));
});
},
render() {
// 获取第一个子元素的 vnode
const slot = this.$slots.default;
const vnode: VNode = getFirstComponentChild(slot);
const componentOptions: ?VNodeComponentOptions =
vnode && vnode.componentOptions;
if (componentOptions) {
// name 不在 inlcude 中或者在 exlude 中则直接返回 vnode,否则继续进行下一步
// check pattern
const name: ?string = getComponentName(componentOptions);
const { include, exclude } = this;
if (
// not included
(include && (!name || !matches(include, name))) ||
// excluded
(exclude && name && matches(exclude, name))
) {
return vnode;
}
const { cache, keys } = this;
// 获取键,优先获取组件的 name 字段,否则是组件的 tag
const key: ?string =
vnode.key == null
? // same constructor may get registered as different local components
// so cid alone is not enough (#3269)
componentOptions.Ctor.cid +
(componentOptions.tag ? `::${componentOptions.tag}` : "")
: vnode.key;
// --------------------------------------------------
// 下面就是 LRU 算法了,
// 如果在缓存里有则调整,
// 没有则放入(长度超过 max,则淘汰最近没有访问的)
// --------------------------------------------------
// 如果命中缓存,则从缓存中获取 vnode 的组件实例,并且调整 key 的顺序放入 keys 数组的末尾
if (cache[key]) {
vnode.componentInstance = cache[key].componentInstance;
// make current key freshest
remove(keys, key);
keys.push(key);
}
// 如果没有命中缓存,就把 vnode 放进缓存
else {
cache[key] = vnode;
keys.push(key);
// prune oldest entry
// 如果配置了 max 并且缓存的长度超过了 this.max,还要从缓存中删除第一个
if (this.max && keys.length > parseInt(this.max)) {
pruneCacheEntry(cache, keys[0], keys, this._vnode);
}
}
// keepAlive标记位
vnode.data.keepAlive = true;
}
return vnode || (slot && slot[0]);
}
};
// 移除 key 缓存
function pruneCacheEntry (
cache: VNodeCache,
key: string,
keys: Array<string>,
current?: VNode
) {
const cached = cache[key]
if (cached && (!current || cached.tag !== current.tag)) {
cached.componentInstance.$destroy()
}
cache[key] = null
remove(keys, key)
}
// remove 方法(shared/util.js)
/**
* Remove an item from an array.
*/
export function remove (arr: Array<any>, item: any): Array<any> | void {
if (arr.length) {
const index = arr.indexOf(item)
if (index > -1) {
return arr.splice(index, 1)
}
}
}
复制代码
在 keep-alive
缓存超过最大时,使用的缓存淘汰算法就是 LRU 算法,它在实现的过程中用到了 cache
对象用于保存缓存的组件实例及 key
值,keys
数组用于保存缓存组件的 key
,当 keep-alive
中渲染一个需要缓存的实例时:
- 判断缓存中是否已缓存了该实例,缓存了则直接获取,并调整
key
在keys
中的位置 - 如果没有缓存,则缓存该实例,若
keys
的长度大于max
(缓存长度超过上限),则移除keys[0]
缓存
小结
LRU算法在很多项目和系统中都有使用,比如安卓系统的任务管理界面,会把最近使用的放在最前面,最近最久未使用的任务放到后面。
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的