文档章节

如何用C++实现一个LRU Cache

汉克斯
 汉克斯
发布于 2015/08/05 16:07
字数 1356
阅读 487
收藏 3
LRU

什么是LRU Cache

LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 什么是Cache?狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。

Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

数据结构

LRU的典型实现是hash map + doubly linked list, 双向链表用于存储数据结点,并且它是按照结点最近被使用的时间来存储的。 如果一个结点被访问了, 我们有理由相信它在接下来的一段时间被访问的概率要大于其它结点。于是, 我们把它放到双向链表的头部。当我们往双向链表里插入一个结点, 我们也有可能很快就会使用到它,同样把它插入到头部。 我们使用这种方式不断地调整着双向链表,链表尾部的结点自然也就是最近一段时间, 最久没有使用到的结点。那么,当我们的Cache满了, 需要替换掉的就是双向链表中最后的那个结点(不是尾结点,头尾结点不存储实际内容)。

如下是双向链表示意图,注意头尾结点不存储实际内容:

头 --> 结 --> 结 --> 结 --> 尾
结     点     点     点     结
点 <-- 1  <-- 2 <-- 3  <-- 点

假如上图Cache已满了,我们要替换的就是结点3。

哈希表的作用是什么呢?如果没有哈希表,我们要访问某个结点,就需要顺序地一个个找, 时间复杂度是O(n)。使用哈希表可以让我们在O(1)的时间找到想要访问的结点, 或者返回未找到。

Cache接口

Cache主要有两个接口:

T Get(K key); 
void Put(K key, T data);

当我们通过键值来访问类型为T的数据时,调用Get函数。如果键值为key的数据已经在 Cache中,那就返回该数据,同时将存储该数据的结点移到双向链表头部。 如果我们查询的数据不在Cache中,我们就可以通过Put接口将数据插入双向链表中。 如果此时的Cache还没满,那么我们将新结点插入到链表头部, 同时用哈希表保存结点的键值及结点地址对。如果Cache已经满了, 我们就将链表中的最后一个结点(注意不是尾结点)的内容替换为新内容, 然后移动到头部,更新哈希表。

C++代码

注意,hash map并不是C++标准的一部分,我使用的是Linux下g++ 4.6.1, hash_map放在/usr/include/c++/4.6/ext下,需要使用__gnu_cxx名空间, Linux平台可以切换到c++的include目录:cd /usr/include/c++/版本 然后grep -iR “hash_map” ./ 查看在哪个文件中,一般头文件的最后几行会提示它所在的名空间。 其它平台请自行探索。XD

当然如果你已经很fashion地在使用C++ 11,就不会有这些小困扰了。

// A simple LRU cache written in C++
// Hash map + doubly linked list
#include <iostream>
#include <vector>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

template <class K, class T>
struct Node{
    K key;
    T data;
    Node *prev, *next;
};

template <class K, class T>
class LRUCache{
public:
    LRUCache(size_t size){
        entries_ = new Node<K,T>[size];
        for(int i=0; i<size; ++i)// 存储可用结点的地址
            free_entries_.push_back(entries_+i);
        head_ = new Node<K,T>;
        tail_ = new Node<K,T>;
        head_->prev = NULL;
        head_->next = tail_;
        tail_->prev = head_;
        tail_->next = NULL;
    }
    ~LRUCache(){
        delete head_;
        delete tail_;
        delete[] entries_;
    }
    void Put(K key, T data){
        Node<K,T> *node = hashmap_[key];
        if(node){ // node exists
            detach(node);
            node->data = data;
            attach(node);
        }
        else{
            if(free_entries_.empty()){// 可用结点为空,即cache已满
                node = tail_->prev;
                detach(node);
                hashmap_.erase(node->key);
            }
            else{
                node = free_entries_.back();
                free_entries_.pop_back();
            }
            node->key = key;
            node->data = data;
            hashmap_[key] = node;
            attach(node);
        }
    }
    T Get(K key){
        Node<K,T> *node = hashmap_[key];
        if(node){
            detach(node);
            attach(node);
            return node->data;
        }
        else{// 如果cache中没有,返回T的默认值。与hashmap行为一致
            return T();
        }
    }
private:
    // 分离结点
    void detach(Node<K,T>* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    // 将结点插入头部
    void attach(Node<K,T>* node){
        node->prev = head_;
        node->next = head_->next;
        head_->next = node;
        node->next->prev = node;
    }
private:
    hash_map<K, Node<K,T>* > hashmap_;
    vector<Node<K,T>* > free_entries_; // 存储可用结点的地址
    Node<K,T> *head_, *tail_;
    Node<K,T> *entries_; // 双向链表中的结点
};

int main(){
    hash_map<int, int> map;
    map[9]= 999;
    cout<<map[9]<<endl;
    cout<<map[10]<<endl;
    LRUCache<int, string> lru_cache(100);
    lru_cache.Put(1, "one");
    cout<<lru_cache.Get(1)<<endl;
    if(lru_cache.Get(2) == "")
        lru_cache.Put(2, "two");
    cout<<lru_cache.Get(2);
    return 0;
}

参考链接

http://www.cs.uml.edu/~jlu1/doc/codes/lruCache.html

© 著作权归作者所有

共有 人打赏支持
汉克斯
粉丝 15
博文 13
码字总数 19282
作品 0
CTO(技术副总裁)
私信 提问
LruCache在美团DSP系统中的应用演进

背景 DSP系统是互联网广告需求方平台,用于承接媒体流量,投放广告。业务特点是并发度高,平均响应低(百毫秒)。 为了能够有效提高DSP系统的性能,美团平台引入了一种带有清退机制的缓存结构...

美团技术团队
2018/12/24
0
0
Android LRUCache原理及使用(对象软引用不行,使用LRU算法)

> 对象软引用,弱引用 A a = new A(); SoftReference sr = new SoftReference(a); a = sr.get(); > LRUCache原理及使用 在Android中采用LRU算法的常用缓存有两种:LruCache和DisLruCache,分......

desaco
01/25
0
0
Android内存优化之内存缓存

什么是缓存? 缓存技术原理就是把用户访问的所有对象看作一个全集,经过算法标记哪些是用户经常访问的对象,把这些对象放到一个集合里,这个集合是全集一个子集,下一次用户再访问的时候会先...

今晚打猴子
2015/08/21
0
0
安卓图片的异步请求及使用LruCache缓存和手机内存两层存储图片,避免重新加载页面带来的重新请求

看到网友的一片技术博客讲解了LruCache的使用,我把它加到了我的项目中,但是加入断点发现,列表上下滑动时,确实可以不用重新加载图片,但是重新打开这个activity或者重新启动应用,LruCach...

bluecoffee
2015/04/03
0
0
Android源码解析——LruCache

我认为在写涉及到数据结构或算法的实现类的源码解析博客时,不应该急于讲它的使用或马上展开对源码的解析,而是要先交待一下这个数据结构或算法的资料,了解它的设计,再从它的设计出发去讲如...

浩码农
2016/05/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js数组遍历和对象遍历

数组遍历 for for(var i=0,len=arr.length;i<len;i++){console.log(arr[i]);} forEach - ES5语法,性能比for弱,不能使用break终止循环,不能使用return arr.forEach(function(item,inde......

祖达
33分钟前
2
0
Java网络编程

基本概念 网络IO会涉及到同步,异步,阻塞,非阻塞等几个概念。 一个网络IO读取过程是数据从 网卡 到 内核缓冲区 到 用户内存 的过程。同步和异步区别在于数据从内核到用户内存的过程是否需要...

春哥大魔王的博客
55分钟前
2
0
Spring "reg:zookeeper" 的前缀 "reg" 未绑定等类似问题解决方案。

今天同事遇到一个Spring启动加载配置文件时,不识别reg:zookeeper标签的问题。 我查看配置,发现是Spring配置文件的头部没有引入reg标签的命名空间,具体如下图: 所以,以后遇到类似的标签未...

花漾年华
今天
2
0
阿里云领衔云市场

近期,2018年Q4及全年的全球云基础设施服务市场数据新鲜出炉,发布方是美国市场研究机构Synergy Research Group。这个机构是专做电信网络市场情报的公司,成立于1999年,每年都会公布各大公有...

linuxCool
今天
2
0
C++友元函数和友元类(C++ friend)详解

私有成员只能在类的成员函数内部访问,如果想在别处访问对象的私有成员,只能通过类提供的接口(成员函数)间接地进行。这固然能够带来数据隐藏的好处,利于将来程序的扩充,但也会增加程序书...

shzwork
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部