LRU缓存设计

Question

最近最少使用（LRU）缓存将丢弃最近最少使用的项目 您如何设计和实现这样的缓存类？设计要求如下：

1）以最快的速度找到该项目，我们可以

2）一旦高速缓存未命中和缓存已满，我们需要快速更换最近最少使用的物品尽可能。

如何根据设计模式和算法设计来分析和实现这个问题？

Answer 1

指向链表节点的链表+哈希表是实现LRU缓存的常用方式。这给了O（1）操作（假设一个体面的散列）。这个优点（作为O（1））：你可以通过锁定整个结构来执行多线程版本。你不必担心粒状锁定等

简单地说，它的工作方式：

在一个值的访问，您将相应的节点链表头部。

当您需要从缓存中删除值时，您将从尾部删除。

将值添加到缓存时，只需将其放置在链接列表的头部即可。

感谢doublep，这里是C++实现的网站：Miscellaneous Container Templates。

Answer 2

缓存一个数据结构，它支持像哈希表一样的检索值？ LRU意味着缓存具有一定的大小限制，我们需要定期丢弃最少使用的条目。

如果你使用指针的链表+哈希表实现你怎么做O（1）通过键检索值？

我会用散列表实现LRU缓存，每个条目的值都是value +指向prev/next条目的指针。

关于多线程访问，我宁愿读者锁定器（理想情况下通过自旋锁实现，因为争用通常很快）来监视。

Answer 3

这是我对LRU缓存的简单示例C++实现，结合了hash（unordered_map）和list。列表中的项目具有访问地图的关键，并且地图上的项目具有访问列表的列表的迭代器。

#include <list> 
#include <unordered_map> 
#include <assert.h> 

using namespace std; 

template <class KEY_T, class VAL_T> class LRUCache{ 
private: 
     list< pair<KEY_T,VAL_T> > item_list; 
     unordered_map<KEY_T, decltype(item_list.begin()) > item_map; 
     size_t cache_size; 
private: 
     void clean(void){ 
       while(item_map.size()>cache_size){ 
         auto last_it = item_list.end(); last_it --; 
         item_map.erase(last_it->first); 
         item_list.pop_back(); 
       } 
     }; 
public: 
     LRUCache(int cache_size_):cache_size(cache_size_){ 
       ; 
     }; 

     void put(const KEY_T &key, const VAL_T &val){ 
       auto it = item_map.find(key); 
       if(it != item_map.end()){ 
         item_list.erase(it->second); 
         item_map.erase(it); 
       } 
       item_list.push_front(make_pair(key,val)); 
       item_map.insert(make_pair(key, item_list.begin())); 
       clean(); 
     }; 
     bool exist(const KEY_T &key){ 
       return (item_map.count(key)>0); 
     }; 
     VAL_T get(const KEY_T &key){ 
       assert(exist(key)); 
       auto it = item_map.find(key); 
       item_list.splice(item_list.begin(), item_list, it->second); 
       return it->second->second; 
     }; 

}; 

Answer 4

我有一个LRU实现here。接口遵循std :: map，所以它不应该很难使用。此外，您可以提供自定义备份处理程序，用于数据在缓存中失效时使用。

sweet::Cache<std::string,std::vector<int>, 48> c1; 
c1.insert("key1", std::vector<int>()); 
c1.insert("key2", std::vector<int>()); 
assert(c1.contains("key1")); 

Answer 5

这是我对基本的简单LRU缓存的实现。

//LRU Cache 
#include <cassert> 
#include <list> 

template <typename K, 
      typename V 
      > 
class LRUCache 
    { 
    // Key access history, most recent at back 
    typedef std::list<K> List; 

    // Key to value and key history iterator 
    typedef unordered_map< K, 
          std::pair< 
            V, 
            typename std::list<K>::iterator 
            > 
         > Cache; 

    typedef V (*Fn)(const K&); 

public: 
    LRUCache(size_t aCapacity, Fn aFn) 
     : mFn(aFn) 
     , mCapacity(aCapacity) 
     {} 

    //get value for key aKey 
    V operator()(const K& aKey) 
     { 
     typename Cache::iterator it = mCache.find(aKey); 
     if(it == mCache.end()) //cache-miss: did not find the key 
      { 
      V v = mFn(aKey); 
      insert(aKey, v); 
      return v; 
      } 

     // cache-hit 
     // Update access record by moving accessed key to back of the list 
     mList.splice(mList.end(), mList, (it)->second.second); 

     // return the retrieved value 
     return (it)->second.first; 
     } 

private: 
     // insert a new key-value pair in the cache 
    void insert(const K& aKey, V aValue) 
     { 
     //method should be called only when cache-miss happens 
     assert(mCache.find(aKey) == mCache.end()); 

     // make space if necessary 
     if(mList.size() == mCapacity) 
      { 
      evict(); 
      } 

     // record k as most-recently-used key 
     typename std::list<K>::iterator it = mList.insert(mList.end(), aKey); 

     // create key-value entry, linked to the usage record 
     mCache.insert(std::make_pair(aKey, std::make_pair(aValue, it))); 
     } 

     //Purge the least-recently used element in the cache 
    void evict() 
     { 
     assert(!mList.empty()); 

     // identify least-recently-used key 
     const typename Cache::iterator it = mCache.find(mList.front()); 

     //erase both elements to completely purge record 
     mCache.erase(it); 
     mList.pop_front(); 
     } 

private: 
    List mList; 
    Cache mCache; 
    Fn mFn; 
    size_t mCapacity; 
    }; 

Answer 6

using hash table and doubly linked list to design LRU Cache

双链表可以处理这个问题。根据关键字，地图是跟踪节点位置的好方法。

class LRUCache{ 

//define the double linked list, each node stores both the key and value. 
struct Node{ 
    Node* next; 
    Node* prev; 
    int value; 
    int key; 
    Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){}; 
    Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){}; 
}; 


map<int,Node*>mp; //map the key to the node in the linked list 
int cp; //capacity 
Node* tail; // double linked list tail pointer 
Node* head; // double linked list head pointer 



public: 
    //constructor 
    LRUCache(int capacity) { 
     cp = capacity; 
     mp.clear(); 
     head=NULL; 
     tail=NULL; 
    } 

    //insert node to the tail of the linked list 
    void insertNode(Node* node){ 
     if (!head){ 
      head = node; 
      tail = node; 
     }else{ 
      tail->next = node; 
      node->prev = tail; 
      tail = tail->next; 
     } 
    } 

    //remove current node 
    void rmNode(Node* node){ 
     if (node==head){ 
      head = head->next; 
      if (head){head->prev = NULL;} 
     }else{ 
      if (node==tail){ 
       tail =tail->prev; 
       tail->next = NULL; 
      }else{ 
       node->next->prev = node->prev; 
       node->prev->next = node->next; 
      } 
     } 
    } 

    // move current node to the tail of the linked list 
    void moveNode(Node* node){ 
     if (tail==node){ 
      return; 
     }else{ 
      if (node==head){ 
       node->next->prev = NULL; 
       head = node->next; 
       tail->next = node; 
       node->prev = tail; 
       tail=tail->next; 
      }else{ 
       node->prev->next = node->next; 
       node->next->prev = node->prev; 
       tail->next = node; 
       node->prev = tail; 
       tail=tail->next; 
      } 
     } 
    } 


    /////////////////////////////////////////////////////////////////////// 
    // get method 
    /////////////////////////////////////////////////////////////////////// 
    int get(int key) { 
     if (mp.find(key)==mp.end()){ 
      return -1; 
     }else{ 
      Node *tmp = mp[key]; 
      moveNode(tmp); 
      return mp[key]->value; 
     } 
    } 

    /////////////////////////////////////////////////////////////////////// 
    // set method 
    /////////////////////////////////////////////////////////////////////// 
    void set(int key, int value) { 
     if (mp.find(key)!=mp.end()){ 
      moveNode(mp[key]); 
      mp[key]->value = value; 
     }else{ 
      if (mp.size()==cp){ 
       mp.erase(head->key); 
       rmNode(head); 
      } 
      Node * node = new Node(key,value); 
      mp[key] = node; 
      insertNode(node); 
     } 
    } 
}; 

Answer 7

LRU页面置换技术：

当一个页面被引用，所需要的页面可能是在缓存中。

If in the cache：我们需要将它放到缓存队列的前面。

If NOT in the cache：我们把它放在缓存中。简而言之，我们在缓存队列的前面添加一个新页面。如果缓存已满，即所有帧都已满，我们从缓存队列的后面移除一个页面，并将新页面添加到缓存队列的前面。

# Cache Size 
csize = int(input()) 

# Sequence of pages 
pages = list(map(int,input().split())) 

# Take a cache list 
cache=[] 

# Keep track of number of elements in cache 
n=0 

# Count Page Fault 
fault=0 

for page in pages: 
    # If page exists in cache 
    if page in cache: 
     # Move the page to front as it is most recent page 
     # First remove from cache and then append at front 
     cache.remove(page) 
     cache.append(page) 
    else: 
     # Cache is full 
     if(n==csize): 
      # Remove the least recent page 
      cache.pop(0) 
     else: 
      # Increment element count in cache 
      n=n+1 

     # Page not exist in cache => Page Fault 
     fault += 1 
     cache.append(page) 

print("Page Fault:",fault) 

输入/输出

Input: 
3 
1 2 3 4 1 2 5 1 2 3 4 5 

Output: 
Page Fault: 10