LRU (Least recently used, 最近最少使用 ) 和 LFU (Least frequently used, 最不经常使用)是两种经典的 cache 管理算法. 其主要差别在于其核心思想:
LRU: 如果数据最近被访问过, 那么将来被访问的几率也更高
LFU: 如果数据在最近一段时间内访问次数越少, 那么将来被访问的几率也越低
LRU 和 LFU 具备的操作主要是: get and put.
get(key) - 返回 key 对应的值, 如果 key 不存在, 则返回 - 1
put(key, value) - 如果 key 存在则将其对应的值设置为 value, 如果 key 不存在, 则插入新的节点. 如果 cache 已经满了, 则需要以某种准则 (满足某种函数 f(x)) 去除 cache 中已存在的节点.
这一数据结构的核心在于当存储空间满了要插入新的节点时, 以何种规则 (即所谓的 f(x)) 丢弃相应的节点. 在设计 LRU 和 LFU 时的主要差别也在于此.
LRU 的设计与实现
为了快速找到最早更新的节点, 可选的数据结构有: queue,heap,linked list. 由于题目又要求快速访问指定节点, 并且在访问之后要更新它的时间顺序, queue 和 heap 不太适用. 因此考虑使用 linked list, 这里我们选用 double linked list, 简化节点的删除操作, 实现 O(1)的删除效率. 并用 hash table 以便实现 O(logn)时间随机访问节点.
首先是双链表的节点定义:
- struct Node{
- Node *pre;
- Node *next;
- int key;
- int val;
- Node(int k,int v):key(k),val(v),pre(NULL),next(NULL){}
- };
使用 map 将 key 与相应的节点对应起来, 实现以 O(logn)时间随机访问 linked list 中的相应节点, 并进行删除更新等相关操作. 另外在构造函数中还需指定 capacity 的大小:
- class LRUCache {
- public:
- LRUCache(int capacity) {
- capacity_ = capacity;
- head = NULL;
- tail = NULL;
- keyToNode.clear();
- }
- private:
- int capacity_;
- Node *head;// 头节点
- Node *tail;// 尾节点
- unordered_map<int,Node*> keyToNode;//key 与节点 Node 的 map
- };
下面设计辅助函数. 由于我们将节点按照使用的时间顺序插入 double linked list 当中, 所以头节点是最少最近使用的节点, 而尾节点是最近使用的节点. 因此首先设计三个函数: 删除头节点: removeHead()以及插入新节点: insertToEnd(int k, int v), 以及更新已存在节点在双链表中的顺序: moveToEnd(int key).
- void insertToEnd(int k, int v){
- //if full or already exist, return
- if(isFull()||keyToNode.count(k)!=0) return;
- Node *nd = new Node(k,v);
- keyToNode[k] = nd;
- //if head = tail = NULL
- if(!head){
- head = tail = nd;
- }
- else{
- tail->next = nd;
- nd->pre = tail;
- tail = tail->next;
- }
- }
- void removeHead(){
- //if head not exist
- if(!head) return;
- keyToNode.erase(head->key);
- Node *tmp = head;
- if(head == tail)//if only one node
- {
- head = tail = NULL;
- }
- else{
- head = head->next;
- head->pre = NULL;
- }
- delete tmp;
- }
- void moveToEnd(int key){
- //if key not exist or already in the end
- if(keyToNode.count(key) == 0|| keyToNode[key] == tail) return;
- Node *nd = keyToNode[key];
- if(nd == head)//if at the front
- {
- head = head->next;
- head->pre = NULL;
- }
- else{
- nd->pre->next = nd->next;
- nd->next->pre = nd->pre;
- }
- tail->next = nd;
- nd->pre = tail;
- nd->next = NULL;
- tail = tail->next;
- }
get(int key)函数的设计比较简单, 直接查找 map 中 key 值是否存在, 如果不存在返回 - 1, 反之, 更新节点位置到链表尾端并返回其值即可.
- int get(int key) {
- if(keyToNode.count(key) == 0) return -1;
- // 如果存在, 将节点更新到链表尾端
- moveToEnd(key);
- return keyToNode[key]->val;
- }
put(int key, int value)分为以下情况: 1. 如果节点存在, 只需要更新节点的值并更新节点在链表中的位置 (moveToEnd) 即可. 这里我们使用 get 函数判断节点是否存在, 则可以省略 moveToEnd 操作. 2. 如果节点不存在, 则插入节点前需要判断是否溢出, 如果溢出, 则先将头节点删除再在尾节点插入新节点即可.
- void put(int key, int value) {
- //if already exist, update value
- if(get(key)!=-1){
- keyToNode[key]->val = value;
- return;
- }
- //if not exist, insert
- if(isFull()) removeHead();
- insertToEnd(key,value);
- }
代码清单: https://github.com/ShulinLiu/DataStructure-Algorithm/blob/master/LeetCode/LRUCache.hpp
以上即是 LRU 详解与 C++ 实现, LFU 的详解与实现将在下一篇文章介绍, 敬请期待.
来源: http://www.jianshu.com/p/59ab049b808a