lfu算法例子？

LFU的每個數(shù)據(jù)塊都有一個引用計數(shù)，所有數(shù)據(jù)塊按照引用計數(shù)排序，具有相同引用計數(shù)的數(shù)據(jù)塊則按照時間排序。

（1）新加入數(shù)據(jù)插入到隊列尾部（因為引用計數(shù)為1）；

（2）隊列中的數(shù)據(jù)被訪問后，引用計數(shù)增加，隊列重新排序；

（3）當需要淘汰數(shù)據(jù)時，將已經(jīng)排序的列表最后的數(shù)據(jù)塊刪除。

注意LFU和下一小節(jié)要介紹的LRU算法之間存在的不同之處，LRU的淘汰規(guī)則是基于訪問時間，而LFU是基于訪問次數(shù)的。舉個簡單的例子，假設緩存大小為3，數(shù)據(jù)訪問序列為set(2,2)、set(1,1)、get(2)、get(1)、get(2)、set(3,3)、set(4,4)，則在set(4,4)時對于LFU算法應該淘汰(3,3)，而LRU應該淘汰(1,1)。LRU關鍵是看頁面最后一次被使用到發(fā)生調(diào)度的時間長短，而LFU關鍵是看一定時間段內(nèi)頁面被使用的頻率。

那么基于LFU算法的Cache設計應該支持的操作如。

n get(key)：如果Cache中存在該key，則返回對應的value值，否則，返回-1；

n set(key,value)：如果Cache中存在該key，則重置value值；如果不存在該key，則將該key插入到到Cache中，若Cache已滿，則淘汰最少訪問的數(shù)據(jù)。