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