LRU(Least Recently Used)最新最少使用,缓存机制之一。
class LRUCache {
public:
struct node {
int val;
node *prev;
node *next;
node(int value):val(value),prev(NULL),next(NULL){}
};
int cap;
int cur;
map<int, node*>cachetable;
node *head;
node *tail;
void moveNodeIntoHead(int key)
{
node* tmp = head->next;
if(tmp == cachetable[key])
return;
node* prevnode = cachetable[key]->prev;
node* nextnode = cachetable[key]->next;
prevnode->next = nextnode;
nextnode->prev = prevnode;
head->next = cachetable[key];
cachetable[key]->prev = head;
cachetable[key]->next = tmp;
tmp->prev = cachetable[key];
return;
}
void appendNodeIntoFront(int key, int value)
{
cachetable[key] = new node(value);
node* tmp = head->next;
head->next = cachetable[key];
cachetable[key]->next = tmp;
tmp->prev = cachetable[key];
cachetable[key]->prev = head;
}
void removeNodeFromTail()
{
node* lastnode = tail->prev;
node* prevnode = lastnode->prev;
lastnode->val = INT_MAX;
prevnode->next = tail;
tail->prev = prevnode;
}
LRUCache(int capacity) {
cachetable.clear();
cap = capacity;
cur = 0;
head = new node(0);
tail = new node(0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if(cachetable.find(key) != cachetable.end() && cachetable[key]->val != INT_MAX)
{
moveNodeIntoHead(key);
return head->next->val;
}
return -1;
}
void put(int key, int value) {
if(cachetable.find(key) != cachetable.end() && cachetable[key]->val != INT_MAX)
{
moveNodeIntoHead(key);
head->next->val = value;
}
else
{
if (cur < cap)
{
appendNodeIntoFront(key, value);
cur++;
}
else
{
removeNodeFromTail();
appendNodeIntoFront(key, value);
}
}
}
};
LFU(Least Frequently Used)最不经常使用,缓存算法之一。
class LFUCache {
int cap;
int size;
int minFreq;
unordered_map<int, pair<int, int>> m; //key to {value,freq};
unordered_map<int, list<int>::iterator> mIter; //key to list iterator;
unordered_map<int, list<int>> fm; //freq to key list;
public:
LFUCache(int capacity) {
cap=capacity;
size=0;
}
int get(int key) {
if(m.count(key)==0) return -1;
fm[m[key].second].erase(mIter[key]);
m[key].second++;
fm[m[key].second].push_back(key);
mIter[key]=--fm[m[key].second].end();
if(fm[minFreq].size()==0 )
minFreq++;
return m[key].first;
}
void set(int key, int value) {
if(cap<=0) return;
int storedValue=get(key);
if(storedValue!=-1)
{
m[key].first=value;
return;
}
if(size>=cap )
{
m.erase( fm[minFreq].front() );
mIter.erase( fm[minFreq].front() );
fm[minFreq].pop_front();
size--;
}
m[key]={value, 1};
fm[1].push_back(key);
mIter[key]=--fm[1].end();
minFreq=1;
size++;
}
};