当前位置:网站首页>使用JS完成一个LRU缓存
使用JS完成一个LRU缓存
2022-07-06 03:47:00 【会说法语的猪】
1. 什么是LRU缓存
LRU
英文全称是 Least Recently Used
,英译过来就是”最近最少使用“的意思。 它是页面置换算法中的一种。
百度百科
LRU
是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t
,当须淘汰一个页面时,选择现有页面中其t
值最大的,即最近最少使用的页面予以淘汰。
通俗解释就是说
假如我们有一块内存,专门用来缓存我们最近发访问的网页,访问一个新网页,我们就会往内存中添加一个网页地址,随着网页的不断增加,内存存满了,这个时候我们就需要考虑删除一些网页了。这个时候我们找到内存中最早访问的那个网页地址,然后把它删掉。
这一整个过程就可以称之为LRU
算法。
两点需要注意:
①当我们访问内存中已经存在了的网址,那么该网址需要更新在内存中的存储顺序。
②当我们内存中还没有数据的时候,不需要执行删除操作。
2.实现LRU思路梳理
- 我们需要一块有限的存储空间,因为无限的化就没必要使用
LRU
算发删除数据了。 - 我们这块存储空间里面存储的数据需要是有序的,因为我们必须要顺序来删除数据,所以可以考虑使用
Array
、Map
数据结构来存储,不能使用Object
,因为它是无序的。 - 我们能够删除或者添加以及获取到这块存储空间中的指定数据。
- 存储空间存满之后,在添加数据时,会自动删除时间最久远的那条数据。
实现就是我们实现一个LRUCache的类,用作存储空间,采用es6中的Map数据结构存储数据,因为它的时间复杂度为
O(1)
且有序,实现get,set方法用来获取和添加数据,存储空间有长度限制,不需要提供删除方法,当我们的内存长度满了之后,自动删除最近最久未被使用的数据,当使用get获取数据时,更新顺序到到最前面
3. 代码
js
class LRUCache {
constructor(length) {
this.length = length // 存储长度
this.map = new Map() // 存储数据
}
// 存储数据,通过键值对的方式
set(key, value) {
if(this.map.has(key)) {
this.map.delete(key)
}
this.map.set(key, value)
// 如果超出了容量,则删除最久的数据(map中即第一个)
if(this.map.size > this.length) {
this.map.delete(this.map.keys().next().value)
}
}
// 获取数据
get(key) {
if(!this.map.has(key)) {
return null
}
const val = this.map.get(key) // 获取元素
this.map.delete(key) // 删除元素
this.map.set(key, val) // 重新插入元素,更新存储顺序
}
}
const lruCache = new LRUCache(3)
lruCache.set('name', 'wft')
lruCache.set('age', 18)
lruCache.set('sex', '男')
lruCache.set('len', '超出长度')
console.log(lruCache, '----->>>')
ts
interface ILRUCache {
length: number
map: Map<unknown, unknown>
set(key: unknown, value: unknown): void
get(key: unknown): void
}
class LRUCache implements ILRUCache {
length: number
map: Map<unknown, unknown>
constructor(length: number) {
this.length = length
this.map = new Map()
}
set(key: unknown, value: unknown) {
if(this.map.has(key)) {
this.map.delete(key)
}
this.map.set(key, value)
if(this.map.size > this.length) {
this.map.delete(this.map.keys().next().value)
}
}
get(key: unknown) {
if(!this.map.has(key)) {
return null
}
const val = this.map.get(key)
this.map.delete(key)
this.map.set(key, val)
}
}
const lruCache = new LRUCache(3)
lruCache.set('name', 'wft')
lruCache.set('age', 18)
lruCache.set('sex', '男')
lruCache.set('len', '超出长度')
console.log(lruCache, '----->>>')
边栏推荐
- Prime Protocol宣布在Moonbeam上的跨链互连应用程序
- Force buckle 1189 Maximum number of "balloons"
- 遥感图像超分辨重建综述
- [practice] mathematics in lottery
- 3分钟带你了解微信小程序开发
- Cross origin cross domain request
- Pytorch基础——(1)张量(tensor)的初始化
- 1.16 - check code
- Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
- Why do you want to start pointer compression?
猜你喜欢
Edcircles: a real time circle detector with a false detection control translation
WPF效果第一百九十一篇之框选ListBox
Ethernet port &arm & MOS &push-pull open drain &up and down &high and low sides &time domain and frequency domain Fourier
No qualifying bean of type ‘......‘ available
多项目编程极简用例
Multi project programming minimalist use case
Blue style mall website footer code
KS003基于JSP和Servlet实现的商城系统
MySQL about self growth
Brush questions in summer -day3
随机推荐
关于非虚函数的假派生
RT-Thread--Lwip之FTP(2)
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
[Massey] Massey font format and typesetting requirements
three. JS page background animation liquid JS special effect
WPF效果第一百九十一篇之框选ListBox
[practical exercise] face location model based on skin color
UDP reliable transport protocol (quic)
Containerization Foundation
Mathematical modeling regression analysis relationship between variables
On Data Mining
Data analysis Seaborn visualization (for personal use)
Crawler of explanation and application of agency theory
Python implementation of maddpg - (1) openai maddpg environment configuration
Pytoch foundation - (2) mathematical operation of tensor
3.2 detailed explanation of rtthread serial port device (V2)
Failure causes and optimization methods of LTE CSFB
BUAA喜鹊筑巢
Multi project programming minimalist use case
C (thirty) C combobox listview TreeView