Leetcode 146：LRU Cache

发表于

这是 Leetcode 146 题，要求实现简单的LRU（Least Recently Used）Cache，解决这道题目的主要思想是：

  1. 使用双向链表（如 STL 中的 list）作为 cache的数据结构，保证在头尾插入和删除的时间复杂度都是 O(1)。每次访问的 Entry 若在 cache 中命中，就将它移到链表头部，若没有命中则分两种情况：若 cache 未满，将新 Entry 插入链表头部；若 cache 满了，先删除链表尾部的 Entry（即最近最少使用的 Entry），再将新 Entry 插入链表头部。
  2. 使用哈希表（如 STL 中的 unordered_map）存储 Entry 的键和 Entry 在 cachae 中位置（如list的迭代器）的映射，可以用 O(1) 时间从 cache 中找到相应的 Entry。

下面是一份提交通过的代码：

#include <list>
#include <iostream>
#include <unordered_map>
using namespace std;

class LRUCache
{
public:
    LRUCache(int capacity)
    { capacity_ = capacity; }

    int get(int key)
    {
        if (hashmap_.find(key) == hashmap_.end())
            return -1;

        moreToHead(key);
        return hashmap_[key]->value_;
    }

    void set(int key, int value)
    {
        if (hashmap_.find(key) == hashmap_.end()) {
            Entry entry(key, value);
            if (cache_.size() >= capacity_) {
            	hashmap_.erase(cache_.back().key_);
            	cache_.pop_back();
            }

            cache_.push_front(entry);
            hashmap_[key] = cache_.begin();
        } else {
            hashmap_[key]->value_ = value;
            moreToHead(key);
        }
    }

private:
    struct Entry
    {
        int key_;
        int value_;
        Entry(int key, int value) : key_(key), value_(value) { }
    };

    unordered_map<int, list<Entry>::iterator> hashmap_;
    list<Entry> cache_;
    int capacity_;

    void moreToHead(int key)
    {
        Entry entry = *hashmap_[key];
        cache_.erase(hashmap_[key]);
        cache_.push_front(entry);
        hashmap_[key] = cache_.begin();
    }
};

杨传辉在《大规模分布式存储系统》一书中讲到：LRU 算法在大多数情况下表现是不错的，但有一个问题：假如某一个查询做了一次全表扫描，将导致缓冲池中的大量页面（可能包含很多很快被访问的热点页面）被替换，从而污染缓冲池。现代数据库一般采用 LIRS（Low Inter-reference Recency Set）算法：将缓冲池分为两级，数据首先进入第一级，如果数据在较短的时间内被访问两次或者以上，则成为热点数据进入第二级，每一级内部还是采用 LRU 替换算法。MySQL 的 InnoDB 存储引擎就用了类似的思想：其内部的 LRU 链表分为两部分：新子链表（new sublist）和老子链表（old sublist），默认情况下前者占 5/8，后者占 3/8。页面首先插入到老子链表，InnoDB 要求页面在老子链表停留时间超过一定值，比如 1 秒，才有可能被转移到新子链表。当出现全表扫描时，InnoDB 将数据页面载入到老子链表，由于数据页面在老子链表中的停留时间不够，不会被转移到新子链表中，这就避免了新子链表中的页面被替换出去的情况。

0%