当前位置:网站首页>Use js to complete an LRU cache
Use js to complete an LRU cache
2022-07-06 03:53:00 【French speaking pig】
1. What is? LRU cache
LRU
The full English name is Least Recently Used
, English translation ” Recently at least use “ It means . It is one of the page replacement algorithms .
Baidu Encyclopedia
LRU
Is a common page replacement algorithm , Select the most recent unused page to weed out . The algorithm gives each page an access field , Used to record the time of a page since it was last visitedt
, When a page has to be eliminated , Select one of the existing pagest
The most valuable , That is, the most recently used pages are eliminated .
Popular explanation means
Suppose we have a piece of memory , It is specially used to cache the web pages we recently visited , Visit a new web page , We will add a web page address to the memory , With the increasing number of web pages , The memory is full , At this time, we need to consider deleting some web pages . At this time, we find the address of the web page we first visited in memory , Then delete it .
This whole process can be calledLRU
Algorithm .
Two points need attention :
① When we visit a web address that already exists in memory , Then the URL needs to update the storage order in memory .
② When we have no data in memory , There is no need to delete .
2. Realization LRU Train of thought
- We need a limited storage space , Because infinity doesn't have to be used
LRU
The data has been deleted . - The data stored in our storage space needs to be orderly , Because we have to delete data in order , So think about it
Array
、Map
Data structures to store , Out of commissionObject
, Because it's disordered . - We can delete or add and obtain the specified data in this storage space .
- When the storage space is full , When adding data , The oldest piece of data will be automatically deleted .
Implementation is that we implement a LRUCache Class , Used as storage space , use es6 Medium Map Data structures store data , Because its time complexity is
O(1)
And orderly , Realization get,set Method is used to get and add data , The storage space is limited in length , There is no need to provide a deletion method , When our memory length is full , Automatically delete the most recently unused data , When using get When getting data , Update the order to the top
3. Code
js
class LRUCache {
constructor(length) {
this.length = length // Storage length
this.map = new Map() // Store the data
}
// Store the data , By means of key value pairs
set(key, value) {
if(this.map.has(key)) {
this.map.delete(key)
}
this.map.set(key, value)
// If the capacity is exceeded , Delete the longest data (map Middle is the first )
if(this.map.size > this.length) {
this.map.delete(this.map.keys().next().value)
}
}
// get data
get(key) {
if(!this.map.has(key)) {
return null
}
const val = this.map.get(key) // Get elements
this.map.delete(key) // Remove elements
this.map.set(key, val) // Reinsert elements , Update storage order
}
}
const lruCache = new LRUCache(3)
lruCache.set('name', 'wft')
lruCache.set('age', 18)
lruCache.set('sex', ' male ')
lruCache.set('len', ' Out of length ')
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', ' male ')
lruCache.set('len', ' Out of length ')
console.log(lruCache, '----->>>')
Learn from :https://juejin.cn/post/7105654083347808263
边栏推荐
- Microkernel structure understanding
- P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
- Canvas cut blocks game code
- 在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
- Cubemx 移植正点原子LCD显示例程
- Take you to wechat applet development in 3 minutes
- math_极限&微分&导数&微商/对数函数的导函数推导(导数定义极限法)/指数函数求导公式推导(反函数求导法则/对数求导法)
- Conditionally [jsonignore]
- Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
- [Massey] Massey font format and typesetting requirements
猜你喜欢
Développement d'un module d'élimination des bavardages à clé basé sur la FPGA
在 .NET 6 中使用 Startup.cs 更简洁的方法
How do we make money in agriculture, rural areas and farmers? 100% for reference
2.1 rtthread pin device details
C#(三十)之C#comboBox ListView treeView
Exchange bottles (graph theory + thinking)
2.2 fonctionnement stm32 GPIO
自动化测试怎么规范部署?
JS music online playback plug-in vsplayaudio js
mysql关于自增长增长问题
随机推荐
3分钟带你了解微信小程序开发
Multi project programming minimalist use case
BUAA喜鹊筑巢
math_极限&微分&导数&微商/对数函数的导函数推导(导数定义极限法)/指数函数求导公式推导(反函数求导法则/对数求导法)
KS008基于SSM的新闻发布系统
Containerization Foundation
Codeforces Global Round 19
Cubemx 移植正点原子LCD显示例程
Prime protocol announces cross chain interconnection applications on moonbeam
[slam] lidar camera external parameter calibration (Hong Kong University marslab) does not need a QR code calibration board
User perceived monitoring experience
Cf603e pastoral oddities [CDQ divide and conquer, revocable and search set]
In Net 6 CS more concise method
How to modify field constraints (type, default, null, etc.) in a table
C form application of C (27)
Mapping between QoE and KQI
How to standardize the deployment of automated testing?
[prediction model] difference method model
Schnuka: visual positioning system working principle of visual positioning system
[Massey] Massey font format and typesetting requirements