LFU（Least Frequently Used ）也是一种常见的缓存算法。
LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。
设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：
要求以上两个方法的时间复杂度为O(1)的
其中圆形为小双向链表的节点，有上指针up、下指针down、键值key、数据项value以及出现次数times
class Node
{
public:
Node(int key, int value, int times)
{
this->key = key;
this->times = times;
this->value = value;
}
int key;
int value;
int times;
Node *up;
Node *down;
};
其中矩形为大双向链表，其中包含两个小双向链表节点的指针，一个表示小双向链表的头，一个表示小双向链表的尾，还有next指针和last指针，分别指向前一级大链表节点和后一级大链表节点。
class NodeList
{
public:
NodeList(Node *node)
:head(node)
, tail(node)
, last(nullptr)
, next(nullptr)
{
}
void addNodeFromHead(Node *newHead)
{
newHead->down = head;
head->up = newHead;
head = newHead;
}
bool isEmpty()
{
return head == nullptr;
}
void deleteNode(Node *node)
{
if (head == tail)
{
delete head;
head = nullptr;
tail = nullptr;
}
else
{
if (node == head)
{
head = node->down;
head->up = nullptr;
}
else if (node == tail)
{
tail = node->up;
tail->down = nullptr;
}
else
{
node->up->down = node->down;
node->down->up = node->up;
}
node->up = nullptr;
node->down = nullptr;
delete node;
}
}
Node *head;
Node *tail;
NodeList *last;
NodeList *next;
};
最后使用以上两个结构形成LFU结构
#include <iostream>
#include <unordered_map>
using namespace std;
class LFUCache
{
public:
LFUCache(int capacity)
{
this->capacity = capacity;
this->size = 0;
headList = nullptr;
}
void set(int key, int value)
{
if (records.find(key) != records.end())
{
Node *node = records[key];
node->value = value;
node->times++;
NodeList *curNodeList = heads.at(node);
move(node, curNodeList);
}
else
{
// 这种情况应该先删除一个节点，并消除他的影响。
if (size == capacity)
{
Node *node = headList->tail;
headList->deleteNode(node);
modifyHeadList(headList);
records.erase(node->key);
heads.erase(node);
size--;
}
// 先判断大头是不是空，如果是空，那么新建1的NodeList，如果不是空，那么就判断大头的次数是不是1，如果是1，那么直接加，如果不是1，就新建1的NodeList
Node *node = new Node(key, value, 1);
if (headList == nullptr) //第一次加入数据
{
headList = new NodeList(node);
}
else {
// 看看已有的最低次数，如果为1，不需要新建，如果不是1就需要新建一个NodeList。
if (headList->head->times== node->times)
{
headList->addNodeFromHead(node);
}
else { // 换头的操作 新建一个1词频的大链表节点
NodeList *newList = new NodeList(node);
newList->next = headList;
headList->last = newList;
headList = newList;
}
}
// 结构信息的更新
records[key]= node;
heads[node] = headList;
size++;
}
}
void move(Node *node, NodeList *oldNodeList)
{
oldNodeList->deleteNode(node);
// node将会进入到一个新链表中，那么这个新链表的前一个链表是哪个？
NodeList *preList = modifyHeadList(oldNodeList) ? oldNodeList->last : oldNodeList;//也有可能为空
NodeList *nextList = oldNodeList->next;//也有可能为空
if (nextList == nullptr)
{
NodeList *newList = new NodeList(node);
if (preList != nullptr)
{
preList->next = newList;
}
newList->last = preList;
if (headList == nullptr)
{
headList = newList;
}
heads[node] = newList;
}
else
{
if (nextList->head->times == node->times)
{
nextList->addNodeFromHead(node);
heads[node] = nextList;
}
else
{
NodeList *newList = new NodeList(node);
if (preList != nullptr)
{
preList->next = newList;
}
newList->last = preList;
newList->next = nextList;
nextList->last = newList;
if (headList == nextList)
{
headList = newList;
}
heads[node] = newList;
}
}
}
// 只有当一个链表中有一个节点被删除了，才会掉用这个函数
// 会将该NodeList节点删除
bool modifyHeadList(NodeList *nodeList)
{
if (headList->isEmpty())
{
if (headList == nodeList)
{
headList = nodeList->next;
if (headList != nullptr)
{
headList->last = nullptr;
}
}
else
{
nodeList->last->next = nodeList->next;
if (nodeList->next != nullptr)
{
nodeList->next->last = nodeList->last;
}
}
delete nodeList;
return true;
}
return false;
}
int get(int key)
{
if (records.find(key) == records.end())
{
return -1; // 标记为不存在
}
Node *node = records[key];
node->times++;
NodeList *curNodeList = heads[node];
move(node, curNodeList); //
return node->value;
}
private:
int capacity; // 最多多少个
int size; // 实际有多少个
unordered_map<int, Node*> records; // 为了由key找Node
unordered_map<Node*, NodeList*> heads; // 任何一个Node他是属于哪个Nodelist
NodeList *headList; // 整个结构中第一个Nodelist是谁，方便快速的删除。并且可以找到整个结构，虽然不是第一个也可以做到
};
int main(int argc, char **argv)
{
system("pause");
return EXIT_SUCCESS;
}