lfu算法優(yōu)缺點(diǎn)？

在LFU算法中，可以為每個(gè)key維護(hù)一個(gè)計(jì)數(shù)器。每次key被訪問(wèn)的時(shí)候，計(jì)數(shù)器增大。計(jì)數(shù)器越大，可以約等于訪問(wèn)越頻繁。

上述簡(jiǎn)單算法存在兩個(gè)問(wèn)題：

在LRU算法中可以維護(hù)一個(gè)雙向鏈表，然后簡(jiǎn)單的把被訪問(wèn)的節(jié)點(diǎn)移至鏈表開(kāi)頭，但在LFU中是不可行的，節(jié)點(diǎn)要嚴(yán)格按照計(jì)數(shù)器進(jìn)行排序，新增節(jié)點(diǎn)或者更新節(jié)點(diǎn)位置時(shí)，時(shí)間復(fù)雜度可能達(dá)到O(N)。

只是簡(jiǎn)單的增加計(jì)數(shù)器的方法并不完美。訪問(wèn)模式是會(huì)頻繁變化的，一段時(shí)間內(nèi)頻繁訪問(wèn)的key一段時(shí)間之后可能會(huì)很少被訪問(wèn)到，只增加計(jì)數(shù)器并不能體現(xiàn)這種趨勢(shì)。

第一個(gè)問(wèn)題很好解決，可以借鑒LRU實(shí)現(xiàn)的經(jīng)驗(yàn)，維護(hù)一個(gè)待淘汰key的pool。第二個(gè)問(wèn)題的解決辦法是，記錄key最后一個(gè)被訪問(wèn)的時(shí)間，然后隨著時(shí)間推移，降低計(jì)數(shù)器。

Redis對(duì)象的結(jié)構(gòu)如下：

typedef struct redisObject {

unsigned type:4;

unsigned encoding:4;

unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or

* LFU data (least significant 8 bits frequency

* and most significant 16 bits access time). */

int refcount;

void *ptr;

} robj;