什麼是 LFU 演算法？_Shenfq

上次的文章介紹了 LRU 演算法，今天打算來介紹一下 LFU 演算法。在上篇文章中有提到， LFU（Least frequently used：最少使用）演算法與 LRU 演算法只是在淘汰策略上有所不同，LRU 傾向於保留最近有使用的資料，而 LFU 傾向於保留使用頻率較高的資料。

舉一個簡單的🌰：快取中有 A、B 兩個資料，且已達到上限，如果 資料 A 先被訪問了 10 次，然後 資料 B 被訪問 1 次，當存入新的 資料 C 時，如果當前是 LRU 演算法，會將 資料 A 淘汰，而如果是 LFU 演算法，則會淘汰 資料 B。

簡單來說，就是在 LRU 演算法中，不管訪問的頻率，只要最近訪問過，就不會將這個資料淘汰，而在 LFU 演算法中，將訪問的頻率作為權重，只要訪問頻率越高，該資料就越不會被淘汰，即使該資料很久沒有被訪問過。

演算法實現

我們還是通過一段 JavaScript 程式碼來實現這個邏輯。

js class LFUCache { freqs = {} // 用於標記訪問頻率 cache = {} // 用於快取所有資料 capacity = 0 // 快取的最大容量 constructor (capacity) { // 儲存 LFU 可快取的最大容量 this.capacity = capacity } }

與 LRU 演算法一樣，LFU 演算法也需要實現 get 與 put 兩個方法，用於獲取快取和設定快取。

js class LFUCache { // 獲取快取 get (key) { } // 設定快取 put (key, value) { } }

老規矩，先看設定快取的部分。如果該快取的 key 之前存在，需要更新其值。

js class LFUCache { // cache 作為快取的儲存物件 // 其解構為: { key: { freq: 0, value: '' } } // freq 表示該資料讀取的頻率； // value 表示快取的資料； cache = {} // fregs 用於儲存快取資料的頻率 // 其解構為: { 0: [a], 1: [b, c], 2: [d] } // 表示 a 還沒被讀取，b/c 各被讀取1次，d被讀取2次 freqs = {} // 設定快取 put (key, value) { // 先判斷快取是否存在 const cache = this.cache[key] if (cache) { // 如果存在，則重置快取的值 cache.value = value // 更新使用頻率 let { freq } = cache // 從 freqs 中獲取對應 key 的陣列 const keys = this.freqs[freq] const index = keys.indexOf(key) // 從頻率陣列中，刪除對應的 key keys.splice(index, 1) if (keys.length === 0) { // 如果當前頻率已經不存在 key // 將 key 刪除 delete this.freqs[freq] } // 更新頻率加 1 freq = (cache.freq += 1) // 更新頻率陣列 const freqMap = this.freqs[freq] || (this.freqs[freq] = []) freqMap.push(key) return } } }

如果該快取不存在，要先判斷快取是否超過容量，如果超過，需要淘汰掉使用頻率最低的資料。

js class LFUCache { // 更新頻率 active (key, cache) { // 更新使用頻率 let { freq } = cache // 從 freqs 中獲取對應 key 的陣列 const keys = this.freqs[freq] const index = keys.indexOf(key) // 從頻率陣列中，刪除對應的 key keys.splice(index, 1) if (keys.length === 0) { // 如果當前頻率已經不存在 key // 將 key 刪除 delete this.freqs[freq] } // 更新頻率加 1 freq = (cache.freq += 1) // 更新讀取頻率陣列 const freqMap = this.freqs[freq] || (this.freqs[freq] = []) freqMap.push(key) } // 設定快取 put (key, value) { // 先判斷快取是否存在 const cache = this.cache[key] if (cache) { // 如果存在，則重置快取的值 cache.value = value this.active(key, cache) return } // 判斷快取是否超過容量 const list = Object.keys(this.cache) if (list.length >= this.capacity) { // 超過儲存大小，刪除訪問頻率最低的資料 const [first] = Object.keys(this.freqs) const keys = this.freqs[first] const latest = keys.shift() delete this.cache[latest] if (keys.length === 0) delete this.freqs[latest] } // 寫入快取，預設頻率為0，表示還未使用過 this.cache[key] = { value, freq: 0 } // 寫入讀取頻率陣列 const freqMap = this.freqs[0] || (this.freqs[0] = []) freqMap.push(key) } }

實現了設定快取的方法後，再實現獲取快取就很容易了。

js class LRUCache { // 獲取資料 get (key) { if (this.cache[key] !== undefined) { // 如果 key 對應的快取存在，更新其讀取頻率 // 之前已經實現過，可以直接複用 this.active(key) return this.cache[key] } return undefined } }

關於 LFU 快取演算法實現就到這裡了，當然該演算法一般使用雙鏈表的形式來實現，這裡的實現方式，只是為了方便理解其原理，感興趣的話可以在網上搜索下更加高效的實現方式。