介紹
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）**等算法。
最後，如果你覺得我的分享對你有幫助，請給予我一個愛心，並且分享這篇文章，這將是對我最大的鼓勵！