菜鸟笔记LFU （Least Frequently Used），是一种缓存算法，它对每一个数据块都有一个访问次数的记录，也就是一个数据块的访问次数越大，在将来越可能访问。
1.每个节点（数据块）都有一个访问次数，新插入的节点访问次数为1
2.相同访问次数的依据时间排序，后插入的在前面
3.当需要淘汰数据时，会从尾部，也就是访问次数从小到大，开始淘汰
这里是使用c++实现的LFU缓存：主要利用了一个multiset，unorder_map分别来根据访问次数排序和保存数据。
这里是需要使用的节点结构
#include <string>
#include <unordered_map>
#include <set>
using namespace std;
template<class KEY>
struct CacheKey
{
KEY key;
int count;
CacheKey(KEY k) :key(k), count(1) {}
void change(int x) {
count += x;
}
int getcount() {
return count;
}
};
template<class KEY,class VAL>
struct CacheNode
{
CacheKey<KEY>* cacheKey;
VAL val;
CacheNode(CacheKey<KEY>* ck, VAL v) :cacheKey(ck), val(v) {}
CacheNode(KEY k, VAL v):val(v) {
cacheKey = new CacheKey<KEY>(k);
}
};
template<class KEY>
struct CMP //仿函数，提供CacheKey的比较方式
{
bool operator()(CacheKey<KEY> const* x, CacheKey<KEY> const* y) {
return x->count < y->count;
}
};c++ LFU
/*
LFU (least Frequently Used)
根据数据的历史访问次数来决定淘汰数据，也就是当前时刻访问次数大的数据，
在下一时刻也可能被访问到。
1.每个节点（数据块）都有一个访问次数
2.相同访问次数的依据时间排序，后插入的在前面
3.当需要淘汰数据时，会从尾部，也就是访问次数从小到大，开始淘汰
*/
template<class KEY, class VAL >
class Lfu
{
public:
Lfu(size_t size) :cacheSize(size){
}
~Lfu() {
auto ite = cacheMap.begin();
while (ite != cacheMap.end()) {
delete ite->second->cacheKey;
delete ite->second;
++ite;
}
cacheMap.clear();
cacheSet.clear();
}
public:
void put(KEY key, VAL val) {
this->check_cache_size();
auto node = new CacheNode<KEY, VAL>(key, val);
cacheMap[key] = node;
cacheSet.insert(node->cacheKey);
}
bool get(KEY key, VAL* val) {
if (cacheMap.count(key)) {
auto node = this->removeFromSet(key);
if(val)
*val = node->val;
node->cacheKey->change(1);
cacheSet.insert(node->cacheKey);
return true;
}
return false;
}
VAL get(KEY key) {
VAL v;
this->get(key, &v);
return v;
}
void remove(KEY key) {
if(cacheMap.count(key)){
auto node = cacheMap[key];
this->removeFromSet(node->key);
delete node->key;
delete node;
cacheMap.erase(key);
}
}
bool exist(KEY key) {
if (cacheMap.count(key))
return true;
return false;
}
void print_test() {
auto ite = cacheSet.begin();
while (ite != cacheSet.end()) {
cout << "count: " << (*ite)->count << " key: " << (*ite)->key << endl;
++ite;
}
cout << "======================================" << endl;
}
private:
//将节点从set中删除，返回删除的node
void removeFromSet(CacheKey<KEY>* key) {
auto ite = cacheSet.find(key);
while(ite != cacheSet.end()){
if(key == cacheMap[(*ite)->key]->key){
cacheSet.erase(ite);
break;
}
auto itex = ite;
++ite;
if(ite != cacheSet.end() && (*ite)->getcount() != (*itex)->getcount()){
break;
}
}
}
//检查缓存数量是否超出了大小限制
void check_cache_size() {
while (cacheMap.size() >= cacheSize) {
auto ite = cacheSet.begin();
cacheMap.erase((*ite)->key);
cacheSet.erase(ite);
}
}
private:
multiset<CacheKey<KEY>*,CMP<KEY>> cacheSet; //利用红黑树根据访问次数排序
unordered_map<KEY, CacheNode<KEY, VAL>*> cacheMap; //缓存MAP
size_t cacheSize; //缓存空间大小
};LFU-Aging LFU的改进版
由于LFU的淘汰策略是淘汰访问次数最小的数据块，但是新插入的数据块的访问次数为1，这样就会产生缓存污染，使得新数据块被淘汰。所以在LFU算法之上，引入访问次数平均值概念，当平均值大于最大平均值限制时，将所有节点的访问次数减去最大平均值限制的一半或一个固定值。
c++ LFU-Aging
/*
LFU-Aging 对于LFU的改进版
LFU对于新数据不友好，因为新插入的数据访问次数count=1,放在尾部
如果需要淘汰就会将新数据淘汰。
所以LFU-Aging加入了平均访问次数的概念
如果节点的平均访问次数大于某个固定值x时，则将所有节点的count值减去x/2
这样可解决“缓存污染”
*/
template<class KEY, class VAL >
class LfuAging
{
public:
LfuAging(size_t size,int maxAverage = 10)
:cacheSize(size), countMaxAverage(maxAverage), countCurAverage(1), countAll(0){
}
~LfuAging() {
auto ite = cacheMap.begin();
while (ite != cacheMap.end()) {
delete ite->second->cacheKey;
delete ite->second;
++ite;
}
cacheMap.clear();
cacheSet.clear();
}
public:
void put(KEY key, VAL val) {
this->check_cache_size();
auto node = new CacheNode<KEY, VAL>(key, val);
cacheMap[key] = node;
cacheSet.insert(node->cacheKey);
this->average(1);
}
bool get(KEY key, VAL* val) {
if (cacheMap.count(key)) {
auto node = this->removeFromSet(key);
if (val)
* val = node->val;
node->cacheKey->change(1);
cacheSet.insert(node->cacheKey);
this->average(1);
return true;
}
return false;
}
VAL get(KEY key) {
VAL v;
this->get(key, &v);
return v;
}
void remove(KEY key) {
auto node = this->removeFromSet(key);
if (node) {
cacheMap.erase(key);
this->average(-node->cacheKey->getcount());
delete node->cacheKey;
delete node;
}
}
bool exist(KEY key) {
if (cacheMap.count(key))
return true;
return false;
}
void print_test() {
auto ite = cacheSet.begin();
while (ite != cacheSet.end()) {
cout << "count: " << (*ite)->count << " key: " << (*ite)->key << endl;
++ite;
}
cout << "======================================" << endl;
}
private:
CacheNode<KEY, VAL>* removeFromSet(KEY key) {
if (cacheMap.count(key)) {
auto node = cacheMap[key];
auto ite = cacheSet.begin();
while (ite != cacheSet.end()) {
if ((*ite) == node->cacheKey) {
cacheSet.erase(ite);
break;
}
++ite;
}
return node;
}
return nullptr;
}
void check_cache_size() {
while (cacheMap.size() >= cacheSize) {
auto ite = cacheSet.begin();
cacheMap.erase((*ite)->key);
cacheSet.erase(ite);
}
}
void average(int change) {
countAll += change;
int av = countAll / cacheMap.size();
if (av >= countMaxAverage) {
auto ite = cacheSet.begin();
while (ite != cacheSet.end()) {
(*ite)->change(-(countMaxAverage / 2));
++ite;
}
countAll = countAll - ((countMaxAverage / 2) * cacheMap.size());
}
}
private:
multiset<CacheKey<KEY>*, CMP<KEY>> cacheSet;
unordered_map<KEY, CacheNode<KEY, VAL>*> cacheMap;
size_t cacheSize;
int countMaxAverage;
int countCurAverage;
int countAll;
};LFU与LRU对比
LFU算法的命中率会更高一些，且能解决一些周期性的访问带来命中率下降的情况。