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