LRU cache design

Question

La cache meno recente utilizzata (LRU) è quella di eliminare prima gli elementi meno utilizzati di recente Come si progetta e si implementa tale classe cache? I requisiti di progettazione sono i seguenti:

1) trovare un prodotto il più velocemente possibile

2) Una volta che un cache miss e una cache è piena, abbiamo bisogno di sostituire l'elemento meno recentemente utilizzato il più velocemente possibile .

Come analizzare e implementare questa domanda in termini di modello di progettazione e progettazione dell'algoritmo?

Answer 1

Una lista collegata + una lista di puntatori ai nodi della lista collegata è il modo usuale per implementare le cache LRU. Questo dà O (1) operazioni (assumendo un discreto hash). Vantaggio di questo (essendo O (1)): puoi eseguire una versione multithread semplicemente bloccando l'intera struttura. Non devi preoccuparti di blocco granulare ecc

In breve, il modo in cui funziona:

Su un accesso di un valore, è spostare il nodo corrispondente nella lista collegata alla testa.

Quando è necessario rimuovere un valore dalla cache, lo si rimuove dalla coda.

Quando si aggiunge un valore alla cache, è sufficiente posizionarlo all'inizio dell'elenco collegato.

Grazie a doublep, ecco il sito con un'implementazione C++: Miscellaneous Container Templates.

Answer 2

La cache è una struttura dati che supporta il valore di recupero per chiave come tabella hash? LRU indica che la cache ha determinate limitazioni di dimensione che è necessario eliminare periodicamente le voci meno utilizzate.

Se si implementa con la lista collegata + l'hash dei puntatori come si può eseguire O (1) recupero del valore per chiave?

Vorrei implementare la cache di LRU con una tabella hash che il valore di ogni voce è valore + puntatori a prev/next entry.

Per quanto riguarda l'accesso multi-threading, preferisco il blocco lettore-scrittore (idealmente implementato da spin lock poiché la contesa è in genere veloce) da monitorare.

Answer 3

Questa è la mia semplice implementazione di esempio C++ per cache LRU, con la combinazione di hash (unordered_map) ed elenco. Gli elementi in elenco hanno la chiave per accedere alla mappa e gli elementi sulla mappa hanno un iteratore di elenco per accedere all'elenco.

#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

Ho un'implementazione LRU here. L'interfaccia segue std :: map quindi non dovrebbe essere così difficile da usare. Inoltre, è possibile fornire un gestore di backup personalizzato, che viene utilizzato se i dati vengono invalidati nella cache.

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

Ecco la mia implementazione per una cache di base LRU semplice.

//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

una lista collegata a doppio grado di gestire questo. Una mappa è un buon modo per tracciare la posizione del nodo in base alla sua chiave.

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 pagina tecnica di sostituzione:

Quando una pagina viene fatto riferimento, la pagina richiesta può essere nella cache.

If in the cache: dobbiamo portarlo in primo piano nella coda della cache.

If NOT in the cache: lo portiamo nella cache. In parole semplici, aggiungiamo una nuova pagina nella parte anteriore della coda della cache. Se la cache è piena, cioè tutti i frame sono pieni, rimuoviamo una pagina dal retro della coda della cache e aggiungiamo la nuova pagina in primo piano nella coda della 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/Output

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

Output: 
Page Fault: 10