什么是 LFU 算法?

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

舉一個(gè)簡(jiǎn)單的??：緩存中有 A、B 兩個(gè)數(shù)據(jù)，且已達(dá)到上限，如果 數(shù)據(jù) A 先被訪問了 10 次，然后 數(shù)據(jù) B 被訪問 1 次，當(dāng)存入新的 數(shù)據(jù) C 時(shí)，如果當(dāng)前是 LRU 算法，會(huì)將 數(shù)據(jù) A 淘汰，而如果是 LFU 算法，則會(huì)淘汰 數(shù)據(jù) B。

簡(jiǎn)單來說，就是在 LRU 算法中，不管訪問的頻率，只要最近訪問過，就不會(huì)將這個(gè)數(shù)據(jù)淘汰，而在 LFU 算法中，將訪問的頻率作為權(quán)重，只要訪問頻率越高，該數(shù)據(jù)就越不會(huì)被淘汰，即使該數(shù)據(jù)很久沒有被訪問過。

算法實(shí)現(xiàn)

我們還是通過一段 JavaScript 代碼來實(shí)現(xiàn)這個(gè)邏輯。

class?LFUCache?{
?freqs?=?{}?//?用于標(biāo)記訪問頻率
?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?還沒被讀取，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
????}
??}
}

如果該緩存不存在，要先判斷緩存是否超過容量，如果超過，需要淘汰掉使用頻率最低的數(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
????}
????//?判斷緩存是否超過容量
????const?list?=?Object.keys(this.cache)
????if?(list.length?>=?this.capacity)?{
??????//?超過存儲(chǔ)大小，刪除訪問頻率最低的數(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]
????}
????//?寫入緩存，默認(rèn)頻率為0，表示還未使用過
????this.cache[key]?=?{?value,?freq:?0?}
????//?寫入讀取頻率數(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)過，可以直接復(fù)用
???this.active(key)
???return?this.cache[key]
??}
??return?undefined
??}
}

關(guān)于 LFU 緩存算法實(shí)現(xiàn)就到這里了，當(dāng)然該算法一般使用雙鏈表的形式來實(shí)現(xiàn)，這里的實(shí)現(xiàn)方式，只是為了方便理解其原理，感興趣的話可以在網(wǎng)上搜索下更加高效的實(shí)現(xiàn)方式。