LRU 是 Least Recently Used 的縮寫，即最近最少使用，作為一種經典的快取策略，它的基本思想是長期不被使用的資料，在未來被用到的幾率也不大，所以當新的資料進來時我們可以優先把這些資料替換掉，
一、基本要求
- 固定大小：限制記憶體使用，
- 快速訪問：快取插入和查找操作應該很快，最好是 O(1) 時間，
- 在達到記憶體限制的情況下替換條目：快取應該具有有效的演算法來在記憶體已滿時驅逐條目，
二、資料結構
下面提供兩種實作方式，并完成相關代碼，
2.1 Map
在 Javascript 中，Map 的 key 是有序的，當迭代的時候，他們以插入的順序回傳鍵值，結合這個特性，我們也通過 Map 實作 LRU 演算法，
2.2 Doubly Linked List
我們也可通過雙向鏈表（Doubly Linked List）維護快取條目，通過對鏈表的增、刪、改實作資料管理，為確保能夠從鏈表中快速讀取某個節點的資料，我們可以通過 Map 來存盤對鏈表中節點的參考，
三、Map 實作
在 初始化時 完成兩件事情：
- 配置存盤限制，當大于此限制，快取條目將按照最近讀取情況被驅逐，
- 創建一個用于存盤快取資料的 Map ，
在 添加資料 時：
- 判斷當前存盤資料中是否包含新進資料，如果存在，則洗掉當前資料
- 判斷當前存盤空間是否被用盡，如果已用盡則洗掉 Map 頭部的資料，
map.delete(map.keys().next().value) - 插入新資料到 Map 的尾部
基于 Javascript Map 實作 LRU，代碼如下：
class LRUCache {
size = 5
constructor(size) {
this.cache = new Map()
this.size = size || this.size
}
get(key) {
if (this.cache.has(key)) {
// 存在即更新
let temp = this.cache.get(key)
this.cache.delete(key)
this.cache.set(key, temp)
return temp
}
return null
}
set(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key)
}
if (this.cache.size >= this.size) {
this.cache.delete(this.cache.keys().next().value)
}
this.cache.set(key, value)
}
}
四、雙向鏈表實作
4.1 定義節點類
包含 prev，next，data 三個屬性，分別用以存盤指向前后節點的參考，以及當前節點要存盤的資料，
{
prev: Node
next: Node
data: { key: string, data: any}
}
4.2 定義鏈表類
包含 head、tail 屬性，分別指向鏈表的 頭節點 和 尾節點，
當從鏈表中讀取資料時，需要將當前讀取的資料移動到鏈表頭部；添加資料時，將新節點插入到頭部；當鏈表節點數量大于限定的閥值，需要從鏈表尾部洗掉節點，
{
head: Node
next: Node
moveNodeToHead(node)
insertNodeToHead(node)
deleteLastNode()
}
4.3 定義 LRU 類
為 LRU 定義屬性：linkLine 用以存盤指向鏈表的參考；size 用以配置存盤空間大小限制；
為簡化從鏈表中查找節點，再定義 map 屬性，用以存盤不同鍵指向鏈表節點的參考，
定義成員方法，set(key,value) 用以添加資料，get(key) 讀取一條資料，
4.4 set(key,value)
- 如果 map 中存在當前 key，則修改當前節點的值，然后從鏈表中把當前節點移動到鏈表頭部；
- 否則：
- 判斷當前鏈表節點數量是否達到了存盤上線，如果是，則洗掉鏈表尾部的節點，同時從 map 中移除相應的節點參考；
- 創建新節點，然后插入到鏈表頭部，并添加 map 參考，
4.5 get(key)
如果 map 中存在當前 key，從鏈表中讀取節點，將其移動到鏈表頭部，并回傳結果，否則回傳空，
{
linkLine: LinkLine
map: Map
size: Number
set(key, value)
get(key)
}
4.6 代碼實作
class LinkNode {
prev = null
next = null
constructor(key, value) {
this.data = https://www.cnblogs.com/kelsen/archive/2022/09/29/{ key, value }
}
}
class LinkLine {
head = null
tail = null
constructor() {
const headNode = new LinkNode('head', 'head')
const tailNode = new LinkNode('tail', 'tail')
headNode.next = tailNode
tailNode.prev = headNode
this.head = headNode
this.tail = tailNode
}
moveNodeToFirst(node) {
node.prev.next = node.next
node.next.prev = node.prev
this.insertNodeToFirst(node)
}
insertNodeToFirst(node) {
const second = this.head.next
this.head.next = node
node.prev = this.head
node.next = second
second.prev = node
}
delete(node) {
node.prev.next = node.next
node.next.prev = node.prev
}
deleteLastNode() {
const last = this.tail.prev
this.tail.prev = last.prev
last.prev.next = this.tail
return last
}
}
class LRUCache {
linkLine = null
map = {}
size = 5
constructor(size) {
this.size = size || this.size
this.linkLine = new LinkLine
}
get(key) {
let value
if (this.map[key]) {
const node = this.map[key]
value = https://www.cnblogs.com/kelsen/archive/2022/09/29/node.value
this.linkLine.moveNodeToFirst(node)
}
return value
}
set(key, value) {
if (this.map[key]) {
const node = this.map[key]
node.value = value
this.linkLine.moveNodeToFirst(node)
} else {
// 洗掉最后一個元素
if (Object.keys(this.map).length >= this.size) {
const lastNode = this.linkLine.deleteLastNode()
delete this.map[lastNode.data.key]
}
const newNode = new LinkNode(key, value)
this.linkLine.insertNodeToFirst(newNode)
this.map[key] = newNode
}
}
}
https://gauliang.github.io/blogs/2022/lru-algorithm/
識微見遠 格物致知轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/510743.html
標籤：其他