lfu （least frequently used），是一种缓存算法，它对每一个数据块都有一个访问次数的记录，也就是一个数据块的访问次数越大，在将来越可能访问。
1.每个节点（数据块）都有一个访问次数，新插入的节点访问次数为1
2.相同访问次数的依据时间排序，后插入的在前面
3.当需要淘汰数据时，会从尾部，也就是访问次数从小到大，开始淘汰
这里是使用c 实现的lfu缓存：主要利用了一个multiset，unorder_map分别来根据访问次数排序和保存数据。
这里是需要使用的节点结构
#include
#include <unordered_map>
#include
using namespace std;
template
struct cachekey
{
key key;
int count;
cachekey(key k) :key(k), count(1) {}
void change(int x) {
count = x;
}
int getcount() {
return count;
}
};
template
struct cachenode
{
cachekey* cachekey;
val val;
cachenode(cachekey* ck, val v) :cachekey(ck), val(v) {}
cachenode(key k, val v):val(v) {
cachekey = new cachekey(k);
}
};
template
struct cmp //仿函数，提供cachekey的比较方式
{
bool operator()(cachekey const* x, cachekey const* y) {
return x->count < y->count;
}
}; c lfu
/*
lfu (least frequently used)
根据数据的历史访问次数来决定淘汰数据，也就是当前时刻访问次数大的数据，
在下一时刻也可能被访问到。
1.每个节点（数据块）都有一个访问次数
2.相同访问次数的依据时间排序，后插入的在前面
3.当需要淘汰数据时，会从尾部，也就是访问次数从小到大，开始淘汰
*/
template
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);
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) {
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*,cmp> cacheset; //利用红黑树根据访问次数排序
unordered_map*> 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 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);
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* 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*, cmp> cacheset;
unordered_map*> cachemap;
size_t cachesize;
int countmaxaverage;
int countcuraverage;
int countall;
}; lfu与lru对比
lfu算法的命中率会更高一些，且能解决一些周期性的访问带来命中率下降的情况。