LRU缓存算法 - C++版

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。

实现思路：  hashtable + 双向链表

时间复杂度：    插入，查找，删除：O（1）

空间使用情况：  O(N) ：一个链表存储K个数据(stl的hash_map实际占的空间比较大).

运行环境：

Linux：RedHat ， Fedora ，CentOS等（理论上Ubuntu ， debian，mac os等也可以运行）

代码：

#ifndef __LRUCACHE_H__
#define __LRUCACHE_H__

#include <vector>
#include <ext/hash_map>
#include <pthread.h>
#include <assert.h>

using namespace __gnu_cxx;

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

template <class K, class D>
class LRUCache{
public:
    LRUCache(size_t size , bool is_pthread_safe = false){
        if(size <= 0)
            size = 1024;

        pthread_safe = is_pthread_safe;
        if(pthread_safe)
            pthread_mutex_init(&cached_mutex , NULL);

        entries = new Node<K,D>[size];
        for(size_t i = 0; i < size; ++i)
            cached_entries.push_back(entries + i);

        head = new Node<K,D>;
        tail = new Node<K,D>;
        head->prev = NULL;
        head->next = tail;
        tail->prev = head;
        tail->next = NULL;
    }

    ~LRUCache(){
        if(pthread_safe)
            pthread_mutex_destroy(&cached_mutex);
        delete head;
        delete tail;
        delete[] entries;
    }

    void Put(K key, D data);
    D Get(K key);
   
private:
    void cached_lock(void){
        if(pthread_safe)
            pthread_mutex_lock(&cached_mutex);
    }
    void cached_unlock(void){
        if(pthread_safe)
            pthread_mutex_unlock(&cached_mutex);
    }
    void detach(Node<K,D>* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void attach(Node<K,D>* node){
        node->prev = head;
        node->next = head->next;
        head->next = node;
        node->next->prev = node;
    }

private:
    hash_map<K, Node<K,D>* > cached_map;
    vector<Node<K,D>* > cached_entries;
    Node<K,D> * head, *tail;
    Node<K,D> * entries;
    bool pthread_safe;
    pthread_mutex_t cached_mutex;
};

template<class K , class D>
void LRUCache<K,D>::Put(K key , D data){
    cached_lock();
    Node<K,D> *node = cached_map[key];
    if(node){
        detach(node);
        node->data = data;
        attach(node);
    }
    else{
        if(cached_entries.empty()){
            node = tail->prev;
            detach(node);
            cached_map.erase(node->key);
        }
        else{
            node = cached_entries.back();
            cached_entries.pop_back();
        }
        node->key = key;
        node->data = data;
        cached_map[key] = node;
        attach(node);
    }
    cached_unlock();
}

template<class K , class D>
D LRUCache<K,D>::Get(K key){
    cached_lock();
    Node<K,D> *node = cached_map[key];
    if(node){
        detach(node);
        attach(node);
        cached_unlock();
        return node->data;
    }
    else{
        cached_unlock();
        return D();
    }
}

#endif

测试用例：

/*
Compile:
  g++ -o app app.cpp LRUCache.cpp -lpthread
Run:
  ./app
*/
#include <iostream>
#include <string>

#include "LRUCache.h"

using namespace std;

int
main(void){
    //int k = 10 ,
    //    max = 100;
    int k = 100000 ,
        max = 1000000;
    LRUCache<int , int> * lru_cache = new LRUCache<int , int>(k , true);
   
    int tmp = 0;
    for(int i = 0 ; i < 2*k ; ++i){
        tmp = rand() % max;
        lru_cache->Put(tmp, tmp + 1000000);
        cout<<tmp<<endl;
    }

    for(int i = 0 ; i < k ; ++i){
        tmp = rand() % max;
        if(lru_cache->Get(tmp) == 0)
            cout<<"miss : "<<tmp<<endl;
        else
            cout<<"hit  : "<<tmp<<"  value : "<<lru_cache->Get(tmp)<<endl;
    }

    delete lru_cache;
    return 0;
}

其实，上面的代码，有一些毛病的。改天我会继续改进。

例如：

1：冗余操作。cached_entries完全可以用一个counter代替。

2：过度抽象。

3：Get、Put的interface不合理。如果真的去实现一个磁盘block的LRU cache，就会发现之前的接口需要重写了。

不过对于大家理解LRU算法。应该有一定的帮助的。