Diseño de memoria caché LRU

Question

Caché utilizada menos recientemente (LRU) es descartar los elementos usados ​​menos recientemente primero ¿Cómo se diseña e implementa dicha clase de caché? Los requisitos de diseño son las siguientes:

1) Encuentre el artículo tan rápidamente como podamos

2) una vez por fallos de caché y una memoria caché está llena, tenemos que reemplazar el elemento menos recientemente utilizado lo más rápido posible .

¿Cómo analizar e implementar esta pregunta en términos de patrón de diseño y diseño de algoritmo?

Answer 1

Una lista vinculada + tabla hash de punteros a los nodos de la lista vinculada es la forma habitual de implementar cachés LRU. Esto da O (1) operaciones (asumiendo un hash decente). Ventaja de esto (siendo O (1)): puede hacer una versión multiproceso simplemente bloqueando toda la estructura. Usted no tiene que preocuparse de bloqueo granular etc.

En pocas palabras, la forma en que funciona:

En un acceso de un valor, mover el nodo correspondiente en la lista enlazada a la cabeza.

Cuando necesite eliminar un valor de la memoria caché, lo eliminará del extremo posterior.

Cuando agrega un valor a la memoria caché, simplemente lo coloca al principio de la lista vinculada.

Gracias a doublep, aquí está el sitio con una implementación en C++: Miscellaneous Container Templates.

Answer 2

¿La memoria caché es una estructura de datos que admite el valor de recuperación por clave como la tabla hash? LRU significa que la memoria caché tiene cierta limitación de tamaño que necesitamos eliminar las entradas menos utilizadas periódicamente.

Si implementa con lista enlazada + tabla hash de punteros ¿cómo puede hacer O (1) recuperación de valor por clave?

Implementaré LRU caché con una tabla hash que el valor de cada entrada es valor + punteros a la entrada anterior/siguiente.

En cuanto al acceso de subprocesamiento múltiple, preferiría el bloqueo de lector-escritor (idealmente implementado por bloqueo de giro ya que la contención suele ser rápida) para supervisar.

Answer 3

Esta es mi implementación sencilla de ejemplo de C++ para la memoria caché LRU, con la combinación de hash (unordered_map) y una lista. Los elementos en la lista tienen una clave para acceder al mapa, y los elementos en el mapa tienen un iterador de lista para acceder a la lista.

#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

que tienen una implementación LRU here. La interfaz sigue a std :: map, por lo que no debería ser tan difícil de usar. Además, puede proporcionar un controlador de respaldo personalizado, que se utiliza si los datos se invalidan en el caché.

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

Aquí está mi implementación para un caché LRU simple y básico.

//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 doblemente enlazada puede manejar esto. Un mapa es una buena manera de rastrear la posición del nodo según su clave.

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 de sustitución de páginas Técnica:

Cuando se hace referencia a una página, la página puede ser requerida en la memoria caché.

If in the cache: tenemos que ponerlo al frente de la cola del caché.

If NOT in the cache: lo traemos en caché. En palabras simples, agregamos una nueva página al frente de la cola del caché. Si la caché está llena, es decir, todos los marcos están llenos, eliminamos una página de la parte posterior de la cola de caché y agregamos la nueva página al frente de la cola de caché.

# 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) 

de entrada/salida

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

Output: 
Page Fault: 10