介紹
LFU(Least Frequently Used)快取是一種用於緩存(cache)中數據替換的算法。
它的基本思想是,當緩存空間不足時,優先移除那些最少被使用的數據,以便為新的數據騰出空間。
LFU快取跟其他替換算法(如LRU)不同,它不僅考慮數據的訪問頻率,還考慮了每個數據的實際使用次數。每當數據被訪問時,其相應的使用計數器會增加。當緩存空間不足時,LFU快取將選擇使用計數器值最小的數據進行替換。
以下是LFU快取的基本操作流程:
- 初始化:設定緩存的最大容量和空的緩存數據結構。
- 存儲數據:當數據要存入緩存時,首先檢查數據是否已存在於緩存中。如果是,則增加相應的使用計數器值;如果不是,則將數據添加到緩存中並將其使用計數器初始化為1。
- 訪問數據:當數據被訪問時,相應的使用計數器增加1。
- 替換數據:當緩存空間不足時,找到使用計數器值最小的數據進行替換。如果有多個數據具有相同的最小使用計數器值,則選擇最早被存儲的那個進行替換。
- 更新緩存:如果緩存中的數據發生變化(新增、訪問或替換),需要相應地更新緩存數據結構。
LFU快取的優點是能有效地保留那些被頻繁訪問的數據,並且在緩存空間不足時優先替換那些較少使用的數據,從而提高緩存的效率。然而,LFU快取也有一些限制,例如計數器可能受到訪問模式的影響,並且需要額外的存儲空間來維護使用計數器。因此,在實際應用中,需要仔細考慮數據訪問模式以及性能和存儲要求等因素,選擇最適合的緩存替換算法。
實作
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.frequency = 1;
this.prev = null;
this.next = null;
}
}
class DLinkedList {
constructor() {
// 建立兩個 node,分別為 head 與 tail
this.head = new Node(null, null);
this.tail = new Node(null, null);
// head 的 next 指標指向 tail
this.head.next = this.tail;
// tail 的 prev 指標指向 head
this.tail.prev = this.head;
}
removeNode(node) {
// 前一個 node (node.prev) 的 next 指標指向下一個 node (node.next)
node.prev.next = node.next;
// 下一個 node (node.next)的 prev 指標指向前一個 node (node.prev)
node.next.prev = node.prev;
}
addNode(node) {
// node 的 next 指標指向 tail
node.next = this.tail;
// node 的 prev 指標指向 tail 的前一個 node (tail.prev)
node.prev = this.tail.prev;
// tail 的前一個 node (tail.prev) 的 next 指標指向 node
this.tail.prev.next = node;
// tail 的 prev 指標指向 node
this.tail.prev = node;
}
removeHead() {
let node = this.head.next;
this.removeNode(node);
return node.key;
}
isEmpty() {
return this.head.next === this.tail;
}
}
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.currentSize = 0;
this.leastFrequency = 0;
this.cache = new Map(); // store { key : Node }
this.frequencyList = new Map(); // store { frequency : DLinkedList }
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
let node = this.cache.get(key);
this.updateFrequency(node);
return node.value;
}
put(key, value) {
if (this.capacity === 0) {
return;
}
if (this.cache.has(key)) {
let node = this.cache.get(key);
node.value = value;
this.updateFrequency(node);
} else {
// 目前快取數量已經到達最大容量,所以要刪除『最小頻率』且『最舊』的快取
if (this.currentSize === this.capacity) {
let leastFrequentList = this.frequencyList.get(this.leastFrequency);
let deletedKey = leastFrequentList.removeHead();
this.cache.delete(deletedKey);
this.currentSize--;
}
// 要建立新的快取,先建立 Node,再來存入 cache 中。
// 再來則是存入頻率為 1 的的 frequencyList。
// 若沒有頻率為 1 的,建立一個。若有,則新增一個 node。
// 並且要將最小頻率設定為 1。
// 還要將目前的快取數量加上 1。
let node = new Node(key, value);
this.cache.set(key, node);
if (!this.frequencyList.has(1)) {
this.frequencyList.set(1, new DLinkedList());
}
this.frequencyList.get(1).addNode(node);
this.leastFrequency = 1;
this.currentSize++;
}
}
/**
* @param {*} node
* updateFrequency 方法的工作流程如下:
* - 接受一個節點作為參數,這個節點代表一個緩存項。
* - 查找該節點當前的訪問頻率,並找到該頻率對應的雙向鍊表(我們在 frequencyList 中為每個頻率都儲存了一個雙向鍊表,鍊表中的每個節點都是該頻率下的緩存項)。
* - 將這個節點從當前訪問頻率的雙向鍊表中移除。
* - 檢查移除節點後,當前頻率的鍊表是否為空。如果為空,並且該頻率恰好是當前的最小頻率,那麼將最小頻率加 1。
* 這是因為我們剛剛移除了頻率最低的節點,所以最低頻率需要增加。
* - 將節點的訪問頻率加 1。
* - 將節點加入到新的頻率對應的雙向鍊表中。如果新的頻率還沒有對應的鍊表,那麼建立一個新的鍊表。
*
* 這個方法的主要作用是維護緩存中的訪問頻率資訊,確保我們能夠正確地追蹤和更新每個緩存項的訪問頻率,並且在需要時能夠找到當前訪問頻率最低的緩存項。
* 這是實現 LFU 緩存算法的關鍵部分。
*/
updateFrequency(node) {
let oldFrequency = node.frequency;
let oldList = this.frequencyList.get(oldFrequency);
oldList.removeNode(node);
// 檢查移除節點後,當前頻率的鍊表是否為空。
// 如果為空,並且該頻率恰好是當前的最小頻率,那麼將最小頻率加 1。
// 表示 leastFrequency 已經不是最小頻率,往上加 1。
/**
* 如果我們將最小頻率增加 1,確實可能會出現沒有對應的 frequencyList 的情況。
* 然而,這並不會產生問題,因為 leastFrequency 僅在需要刪除最少使用的節點時(也就是當 put 操作的時候,緩存容量已滿)才會被用到。
* 而在這種情況下,由於有新的節點進入,必然會有新的 frequencyList 被創建。
*/
if (oldFrequency === this.leastFrequency && oldList.isEmpty()) {
this.leastFrequency++;
}
// 將節點的訪問頻率加 1。
node.frequency++;
// 如果新的頻率還沒有對應的鍊表,那麼建立一個新的鍊表。
if (!this.frequencyList.has(node.frequency)) {
this.frequencyList.set(node.frequency, new DLinkedList());
}
// 將節點加入到新的頻率對應的雙向鍊表中。
this.frequencyList.get(node.frequency).addNode(node);
}
}
let lfuCache = new LFUCache(2);
lfuCache.put('1', '1');
lfuCache.put('2', '2');
console.log('Output: 1', lfuCache.get('1')); // Output: 1
lfuCache.put('3', '3');
console.log('Output: -1', lfuCache.get('2')); // Output: -1
console.log('Output: 3', lfuCache.get('3')); // Output: 3
lfuCache.put('4', '4');
console.log('Output: -1', lfuCache.get('1')); // Output: 1
console.log('Output: 3', lfuCache.get('3')); // Output: 3
console.log('Output: 4', lfuCache.get('4')); // Output: 4
總結
LFU確實是一種以使用頻率作為判斷標準的緩存替換算法,當緩存空間不足時,它將移除最少被使用的數據。
這種方法可以保證在空間有限的情況下,最常被使用的數據能夠保留在緩存中。然而該算法也有其限制,如計數器可能受到訪問模式的影響,並且需要額外的存儲空間來維護使用計數器。
所以在實際應用中,需要根據數據訪問模式、性能需求、存儲空間等因素來選擇最適合的緩存替換算法,可能是LFU,也可能是其他如LRU(Least Recently Used)、**FIFO(First In, First Out)**等算法。
最後,如果你覺得我的分享對你有幫助,請給予我一個愛心,並且分享這篇文章,這將是對我最大的鼓勵!