[LeetCode]146. LRU Cache

Problem

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Solution

Analysis

cpu缓存cache的一种访问替换方法, lru最近最少使用. 设计题, 根据lru的原理,设计一种方案.

百度百科:为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最久未使用的那个页面调出内存。这就是LRU算法的全部内容。

我的实现方式是使用两个unordered_map, 其中一个记录key和value的映射关系, 一个记录对应key的操作/访问时间, 记录访问时间通过time记录, 每次插入,除了更新key-value映射表之外,也要更新key-time表, 访问时,除了访问key-value放回元素外,还要更新元素访问时间表. 删除时,遍历访问时间表,找到时间最小的位置(这个位置表示最近一段时间内都没有访问,可以删除), 删除key-value表中相应的位置, 删除访问时间表中的位置. 这种方法的缺点是占用了太多额外的空间.

查看别人的解法, 使用一个list链表记录元素, 因为链表有相应的顺序关系,只能从前往后访问,每次访问元素时,将相应的元素放到表头,这样链表尾巴的元素就是可以删除的元素, 另外使用链表的原因是因为这里插入删除元素比较频繁, 所以链表比数组效率要高一点. 另外我们还需要一个映射表, 将相应key映射到链表中元素的位置,方便直接访问.

Code

My Solution

class LRUCache {
public:
    LRUCache(int capacity) {
        time = 1;
        cap = capacity;
    }
    
    int get(int key) {
        if (tabel.find(key) == tabel.end())
            return -1;
        occur[key] = time;
        time++;
        return tabel[key];
    }
    
    void put(int key, int value) {
        if (tabel.size() < cap){
            tabel[key] = value;
            occur[key] = time;
        }else{
            // find the value to be replaced
            // 键可以重复
            if (tabel.find(key) != tabel.end()){
                tabel[key] = value;
                occur[key] = time;
            }else{
                int invalid_key;
                int invalid_time = time;
                for (unordered_map<int, int>::iterator it = occur.begin(); it != occur.end(); it++){
                    if (invalid_time > it->second){
                        invalid_time = it->second;
                        invalid_key = it->first;
                    }
                }
                occur.erase(invalid_key);
                tabel.erase(invalid_key);
                tabel[key] = value;
                occur[key] = time;
            }
        }
        time++;
            
    }
private:
    int time;
    int cap;
    unordered_map<int, int> tabel;// data
    unordered_map<int, int> occur;// occur time
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Recommend

/**
LRU:最近最少使用.
cache容量. 
push(key,value):
    1. key存在, 更新key对应的value,同时更新使用时间/放到最近的位置
    2. key不存在:
        a. 当前cache已满, 替换掉一段时间内都没有使用过的内存, 同时把内容压入,记录访问时间
        b. 未满: 直接插入, 记录访问时间
get(key):
    1. key存在: 返回,value;更新访问时间
    2. key不存在: 返回-1.
这里的访问时间的记录使用list对象: list从前往后访问时间依次变远(删除时,删除后面的结点)

我采取的原始方案:使用一个time字段,记录当前时间.
**/
class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = tabel.find(key);
        if (it == tabel.end()) return -1;
        // 将it->second对象放在ll的头部位置
        // ll.begin()表示位置; ll表示剪裁对象(容器), it->second表示具体对象
        ll.splice(ll.begin(), ll, it->second);// 移动到list头部
        
        return it->second->second;// 返回对应值
    }
    
    void put(int key, int value) {
        auto it = tabel.find(key);
        if (it != tabel.end()) ll.erase(it->second);
        ll.push_front(make_pair(key, value));
        tabel[key] = ll.begin();
        if (tabel.size() > cap){
            int k = ll.rbegin()->first;
            ll.pop_back();
            tabel.erase(k);
        }
    }
private:
    int cap;// 记录容量限制
    list<pair<int, int>> ll; //每个键值对,方便删除和移动 
    unordered_map<int, list<pair<int, int>>::iterator> tabel;//查找
    // 键->list中的iterator对象
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

References

https://www.cnblogs.com/grandyang/p/4587511.html