LRU 和 LFU 缓存淘汰算法

缓存淘汰算法有很多种，这里只简单介绍2种：LRU 和 LFU。

• LRU全称 Least recently used，意思为淘汰掉最久未使用（即最老）的一条数据；
• LFU全称 Least-frequently used，意思为淘汰掉过去被访问次数最少的一条数据。

LRU在服务器缓存中经常有用武之地，它有非常成熟的O(1)复杂度的实现方法；LFU也有O(1)的实现方法，它的实现方法是受到LRU实现方法的启发。

LRU

首先实现对每个数据的 O(1) 访问，那么只需要将数据保存在hashmap中，利用[key, value]，实现对数据的快速访问。除此之外，实现LRU算法我们需要：

1. 在缓存已满时，再插入数据时，就需要淘汰最老的数据，怎么确定哪些数据是最老的。
2. 在插入数据时，需要将当前插入的数据标记为最新访问
3. 同理，在查找数据时，需要将查找的数据标记为最新访问

为了解决这3个问题，我们可以引入一条双向链表：

• 如果数据为第一次插入，则将其key插入在尾部
• 如果数据查询一次，则将其key从链表中删除，重新将key从尾部插入

这样，我们就可以确定链表的头部为最老数据、尾部为最新数据。那么第一个问题也就迎刃而解：

• 在插入数据时，如果当前的数据已满，需要淘汰最老的数据，即删除链表的头部节点数据。同时从hashmap中删除数据。

struct MapValue {
    int value;
    list<int>::iterator node_list_iter;
};

class LRU {
public:
    LRU(size_t capacity) : capacity_(capacity) { }
    optional<int> Get(int key) {
        auto it = map_.find(key);
        if(it == map_.end()) {
            return {};
        }

        // 找到了，因为本次访问，该key对应的数据变为最新
        list_.erase(it->second.node_list_iter);
        it->second.node_list_iter = list_.insert(list_.end(), key);
        return it->second.value;
    }

    void Set(int key, int value) 
    {
        // 先查找该节点是否存在
        auto it = map_.find(key);
        if(it == map_.end()) { // 不存在，插入数据
            // 插入数据之前，要看看数据是否已满，如果已满，需要淘汰最老数据
            if(map_.size() >= capacity_) {
                map_.erase(list_.front());
                list_.erase(list_.begin());
            }

            auto&& [it2, b] = map_.insert(make_pair(key, MapValue{value}));
            assert(b);
            it = it2;
        } else { // 存在
            list_.erase(it->second.node_list_iter);
        }

          // 将该key对应的value设置为新的值，并将该key设置为最新(既放入链表末尾)
          it->second.node_list_iter = list_.insert(list_.end(), key);
          it->second.value = value;
      }

private:
    const size_t capacity_; // LRU最多缓存多少条数据
    unordered_map<int, MapValue> map_;
    list<int> list_; // 链表，存储每个节点的key。头节点为最老的节点，尾节点为最新
};

测试代码：

void test_lru()
{
    LRU lru(3);

    lru.set(9001, "9001");
    lru.set(9002, "9002");
    lru.set(9003, "9003");

    lru.set(9004, "9004");
    string value;
    assert(lru.get(9001, value) == false);

    assert(lru.get(9002, value) == true);
    assert(value == "9002");
}

LFU(Least-frequently used)

LFU 是淘汰掉过去被访问次数最少的一条数据，那么我们需要已记录一个key的访问频次，并按照访问频次排序。