一篇帶你了解什么是 LFU 算法？
上次的文章介紹了 LRU 算法，今天打算來介紹一下 LFU 算法。在上篇文章中有提到， LFU(Least frequently used：最少使用)算法與 LRU 算法只是在淘汰策略上有所不同，LRU 傾向于保留最近有使用的數(shù)據(jù)，而 LFU 傾向于保留使用頻率較高的數(shù)據(jù)。
舉一個簡單的：緩存中有 A、B 兩個數(shù)據(jù)，且已達到上限，如果 數(shù)據(jù) A 先被訪問了 10 次，然后 數(shù)據(jù) B 被訪問 1 次，當存入新的 數(shù)據(jù) C 時，如果當前是 LRU 算法，會將 數(shù)據(jù) A 淘汰，而如果是 LFU 算法，則會淘汰 數(shù)據(jù) B。
簡單來說，就是在 LRU 算法中，不管訪問的頻率，只要最近訪問過，就不會將這個數(shù)據(jù)淘汰，而在 LFU 算法中，將訪問的頻率作為權(quán)重，只要訪問頻率越高，該數(shù)據(jù)就越不會被淘汰，即使該數(shù)據(jù)很久沒有被訪問過。
算法實現(xiàn)
我們還是通過一段 JavaScript 代碼來實現(xiàn)這個邏輯。
class LFUCache {
freqs = {} // 用于標記訪問頻率
cache = {} // 用于緩存所有數(shù)據(jù)
capacity = 0 // 緩存的最大容量
constructor (capacity) {
// 存儲 LFU 可緩存的最大容量
this.capacity = capacity
}
}
與 LRU 算法一樣，LFU 算法也需要實現(xiàn) get 與 put 兩個方法，用于獲取緩存和設置緩存。
class LFUCache {
// 獲取緩存
get (key) { }
// 設置緩存
put (key, value) { }
}
老規(guī)矩，先看設置緩存的部分。如果該緩存的 key 之前存在，需要更新其值。
class LFUCache {
// cache 作為緩存的存儲對象
// 其解構(gòu)為: { key: { freq: 0, value: '' } }
// freq 表示該數(shù)據(jù)讀取的頻率；
// value 表示緩存的數(shù)據(jù)；
cache = {}
// fregs 用于存儲緩存數(shù)據(jù)的頻率
// 其解構(gòu)為: { 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 的數(shù)組
const keys = this.freqs[freq]
const index = keys.indexOf(key)
// 從頻率數(shù)組中，刪除對應的 key
keys.splice(index, 1)
if (keys.length === 0) {
// 如果當前頻率已經(jīng)不存在 key
// 將 key 刪除
delete this.freqs[freq]
}
// 更新頻率加 1
freq = (cache.freq += 1)
// 更新頻率數(shù)組
const freqMap =
this.freqs[freq] ||
(this.freqs[freq] = [])
freqMap.push(key)
return
}
}
}
如果該緩存不存在，要先判斷緩存是否超過容量，如果超過，需要淘汰掉使用頻率最低的數(shù)據(jù)。
class LFUCache {
// 更新頻率
active (key, cache) {
// 更新使用頻率
let { freq } = cache
// 從 freqs 中獲取對應 key 的數(shù)組
const keys = this.freqs[freq]
const index = keys.indexOf(key)
// 從頻率數(shù)組中，刪除對應的 key
keys.splice(index, 1)
if (keys.length === 0) {
// 如果當前頻率已經(jīng)不存在 key
// 將 key 刪除
delete this.freqs[freq]
}
// 更新頻率加 1
freq = (cache.freq += 1)
// 更新讀取頻率數(shù)組
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) {
// 超過存儲大小，刪除訪問頻率最低的數(shù)據(jù)
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 }
// 寫入讀取頻率數(shù)組
const freqMap = this.freqs[0] || (this.freqs[0] = [])
freqMap.push(key)
}
}
實現(xiàn)了設置緩存的方法后，再實現(xiàn)獲取緩存就很容易了。
class LRUCache {
// 獲取數(shù)據(jù)
get (key) {
if (this.cache[key] !== undefined) {
// 如果 key 對應的緩存存在，更新其讀取頻率
// 之前已經(jīng)實現(xiàn)過，可以直接復用
this.active(key)
return this.cache[key]
}
return undefined
}
}
關于 LFU 緩存算法實現(xiàn)就到這里了，當然該算法一般使用雙鏈表的形式來實現(xiàn)，這里的實現(xiàn)方式，只是為了方便理解其原理，感興趣的話可以在網(wǎng)上搜索下更加高效的實現(xiàn)方式。
