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

  实现思路: hashtable + 双向链表

  时间复杂度: 插入,查找,删除:O(1)

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

  运行环境:

  linux:redhat , fedora ,centos等(理论上ubuntu , debian,mac os等也可以运行)

  代码:

  [cpp] view plaincopy

  #ifndef __LRUCACHE_H__

  #define __LRUCACHE_H__

  #include

  #include

  #include

  #include

  using namespace __gnu_cxx;

  template

  struct Node{

  K key;

  D data;

  Node *prev, *next;

  };

  template

  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[size];

  for(size_t i = 0; i < size; ++i)

  cached_entries.push_back(entries + i);

  head = new Node;

  tail = new Node;

  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* node){

  node->prev->next = node->next;

  node->next->prev = node->prev;

  }

  void attach(Node* node){

  node->prev = head;

  node->next = head->next;

  head->next = node;

  node->next->prev = node;

  }

  private:

  hash_map* > cached_map;

  vector* > cached_entries;

  Node * head, *tail;

  Node * entries;

  bool pthread_safe;

  pthread_mutex_t cached_mutex;

  };

  template

  void LRUCache::Put(K key , D data){

  cached_lock();

  Node *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

  D LRUCache::Get(K key){

  cached_lock();

  Node *node = cached_map[key];

  if(node){

  detach(node);

  attach(node);

  cached_unlock();

  return node->data;

  }

  else{

  cached_unlock();

  return D();

  }

  }

  #endif

  测试用例:

  [cpp] view plaincopy

  /*

  Compile:

  g++ -o app app.cpp LRUCache.cpp -lpthread

  Run:

  ./app

  */

  #include

  #include

  #include "LRUCache.h"

  using namespace std;

  int

  main(void){

  //int k = 10 ,

  // max = 100;

  int k = 100000 ,

  max = 1000000;

  LRUCache * lru_cache = new LRUCache(k , true);

  int tmp = 0;

  for(int i = 0 ; i < 2*k ; ++i){

  tmp = rand() % max;

  lru_cache->Put(tmp, tmp + 1000000);

  cout<

  }

  for(int i = 0 ; i < k ; ++i){

  tmp = rand() % max;

  if(lru_cache->Get(tmp) == 0)

  cout《"miss : "<

  else

  cout《"hit : "< www.yzyedu.com

04-25 02:08