LFU缓存结构
LFU缓存结构
LFU（least frequently used），即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但之后就不再使用，这类页将会长时间留在内存中。
策略：
缓存中最多存放K条记录，如果新的K+1条记录要加入，就需要根据策略删除一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删除掉这个key的记录；如果调用次数最少的key有多个，上次调用发生最早的key被删除。
解答：
整体结构设计成发生set和get操作次数一样的key，都放在一个双向链表里（桶）。对于不同的操作次数，分别设置桶，然后桶和桶之间按照操作次数从小到大串起来，桶和桶之间看成一个双向链表。
当某一个key发生set和get时，来到key所在的位置，把key从原来的桶中去掉，也就是key的上一个节点和下一个节点之间相连。然后把key扔到次数+1之后的桶中，如果没有次数+1的桶就新建一个桶，保证桶之间依然时双向链表的链接；如果已经有次数+1的桶，就把key放到这个桶的头部。如果key原来所在的桶中只有key这一个记录，就删掉原来的桶，保证桶之间依然是双向链表的链接。
//节点的结构
class Node {
public:int key;int value;int times; //这个节点发生get或者set的次数总和Node* up; //节点之间是双向链表，所以有上一个节点Node* down; //节点之间是双向链表，所以有下一个节点Node(int key, int value, int times) : key(key), value(value), times(times) {}
};//桶结构
class NodeList {
public:Node* head; //桶的头节点Node* tail; //桶的尾节点NodeList* last; //桶之间是双向链表，指向前一个桶NodeList* next; //桶之间是双向链表，指向后一个桶NodeList(Node* node){head = node;tail = node;}//把一个新的节点加入这个桶，新的节点都放在顶端变成新的头部void addNodeFromHead(Node* newHead){newHead->down = head;head->up = newHead;head = newHead;}//判断这个桶是不是空的bool isEmpty(){return head == nullptr;}//删除node节点并保证node的上下环境重新连接void deleteNode(Node* node){if (head == tail){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;}
};//总的缓存结构
class LFUCache {
private:int capacity; //缓存的大小限制，即Kint size; //缓存目前有多少节点//表示key由哪个节点表示map records;//表示节点在哪个桶里map heads;NodeList* headList; //整个结构中位于最左边的桶public:LFUCache(int K){this->capacity = K;this->size = 0;headList = nullptr;}//removeNodeList:刚刚减少了一个节点的桶//这个函数的功能是，判断刚刚减少了一个节点的桶是否已空//1.如果不空，什么也不做////2.如果空了，removeNodeList还是整个缓存结构最左边headList//删除这个桶的同时也要让最左的桶变成removeNodeList的下一个////3.如果空了，removeNodeList不是整个缓存结构结构最左边的桶headList//把这个桶删除，并保证上一个桶和下一个桶之间还是双向链表的连接方式private://函数的返回值表示刚刚减少了一个节点的桶是否已经为空，空则返回true，不空则为falsebool modifyHeadList(NodeList* removeNodeList){if (removeNodeList->isEmpty()){if (headList == removeNodeList){headList = removeNodeList->next;if (headList != nullptr){headList->last = nullptr;}}else{removeNodeList->last->next = removeNodeList->next;if (removeNodeList->next != nullptr)removeNodeList->next->last = removeNodeList->last;}return true;}return false;}//函数的功能//node这个节点的次数+1，这个节点原来在oldNodeList里//把node从oldNodeList删掉，然后放到次数+1的桶中//整个过程既要保证桶之间仍然是双向链表，也要保证节点之间仍然是双向链表void move(Node* node, NodeList* oldNodeList){oldNodeList->deleteNode(node);//preList表示次数+1的桶的前一个桶是谁//如果oldNodeList删掉node之后还有节点//oldNodeList就是次数+1的桶的前一个桶//如果oldNodeList删除node之后空了，oldNodeList需要删除的//所以次数+1的桶的前一个桶是oldNodeList的前一个NodeList* preList = modifyHeadList(oldNodeList) ? oldNodeList->last : oldNodeList;//nextList表示次数+1的桶的后一个桶是谁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.insert(pair(node, nextList));}else{if (nextList->head->times == node->times){nextList->addNodeFromHead(node);heads.insert(pair(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.insert(pair(node, nextList));}}}
public:void set(int key, int value){if (records.count(key)){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--;}Node* node = new Node(key, value, 1);if (headList == nullptr)headList = new NodeList(node);else{if (headList->head->times == node->times)headList->addNodeFromHead(node);else{NodeList* newList = new NodeList(node);newList->next = headList;headList->last = newList;headList = newList;}}records.insert(pair(key, node));heads.insert(pair(node, headList));size++;}}int get(int key){if (!records.count(key))return -1;Node* node = records.at(key);node->times++;NodeList* curNodeList = heads.at(node);move(node, curNodeList);return node->value;}
};
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！