La meilleure façon de mettre de cache LRU

Si vous voulez un cache LRU, le plus simple en Java est LinkedHashMap. Le comportement par défaut est FIFO cependant, vous pouvez change "accéder à la commande", ce qui en fait un cache LRU.

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
}

Remarque: j'ai l'aide de la constructeur qui change de la collection de la plus récente d'abord pour les plus récemment utilisés en premier.

De la Javadoc

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.
Parameters:
initialCapacity - the initial capacity
loadFactor - the load factor
accessOrder - the ordering mode - true for access-order, false for insertion-order

Quand accessOrder est true la LinkedHashMap re-arrange la commande de la carte à chaque fois que vous obtenez() une entrée qui n'est pas le dernier.

De cette façon, l'entrée la plus ancienne est du moins ce qui est utilisé récemment.

OriginalL'auteur Peter Lawrey

Considérant le cache permet l'accès simultané, le problème de la bonne conception de cache LRU se résume à:

a) Peut-on éviter l'utilisation de mutex tout en mettant à jour les deux structures(cache de la structure et de la LRU, de la structure).

b) la lecture (get) le fonctionnement du cache exiger mutex?

Plus en détail: - Dire si l'on met en œuvre à l'aide de java.util.de façon concomitante.ConcuurentHashMap(cache de la structure) et java.util.de façon concomitante.ConcurrentLinkedQueue(LRU structure)

a)de Verrouillage à la fois ces deux structures sur les opérations d'édition - addEntry(), removeEntry(), evictEntries (), etc.

b) ci-dessus pourrait probablement passer pour de la lenteur des opérations d'écriture, mais le problème est le même pour la lecture (get) de l'opération, nous avons besoin d'appliquer de verrouillage sur les deux structures. Parce que, obtenir signifie mettre l'entrée à l'avant de la file d'attente pour LRU stratégie.(En supposant que les entrées ont été supprimées à partir de la fin de la file d'attente).

Utilisation simultanée efficace des structures comme ConcurrentHashMap et attendre gratuit ConcurrentLinkedQueue et puis mettre un verrou sur eux est de perdre la raison.

J'ai mis en place un cache LRU, avec la même approche, cependant, la LRU structuré a été mis à jour de manière asynchrone en éliminant le besoin d'utiliser un mutex si l'accès à ces structures. LRU est un détail interne de la Cache et peut être mis en œuvre sans affecter les utilisateurs de la cache.

Plus tard, j'ai aussi lu à propos de ConcurrentLinkedHashMap

https://code.google.com/p/concurrentlinkedhashmap/

Et trouve que c'est aussi essayer de faire la même chose. Pas utilisé cette structure, mais peut-être peut-être un bon ajustement.

OriginalL'auteur aditrip

Énoncé Du Problème :

Créer cache LRU et Employé du magasin d'objet Max =5 objets et de trouver qui connectez-vous d'abord et après ....

package com.test.example.dto;
import java.sql.Timestamp;
/**
* 
* @author [email protected]
*
*/
public class Employee implements Comparable<Employee> {
private int     id;
private String  name;
private int     age;
private Timestamp loginTime ;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public Timestamp getLoginTime() {
return loginTime;
}
public void setLoginTime(Timestamp loginTime) {
this.loginTime = loginTime;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + ", age=" + age + ", loginTime=" + loginTime + "]";
}
Employee(){}
public Employee(int id, String name, int age, Timestamp loginTime) {
super();
this.id = id;
this.name = name;
this.age = age;
this.loginTime = loginTime;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + id;
result = prime * result + ((loginTime == null) ? 0 : loginTime.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
Employee other = (Employee) obj;
if (age != other.age) return false;
if (id != other.id) return false;
if (loginTime == null) {
if (other.loginTime != null) return false;
} else if (!loginTime.equals(other.loginTime)) return false;
if (name == null) {
if (other.name != null) return false;
} else if (!name.equals(other.name)) return false;
return true;
}
@Override
public int compareTo(Employee emp) {
if (emp.getLoginTime().before( this.loginTime) ){
return 1;
} else if (emp.getLoginTime().after(this.loginTime)) {
return -1;
}
return 0;
}
}

LRUObjectCacheExample

package com.test.example;
import java.sql.Timestamp;
import java.util.Calendar;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import com.test.example.dto.Employee;
/**
* 
* @author [email protected]
*
*/
public class LRUObjectCacheExample {
LinkedHashMap<Employee, Boolean>    lruCacheLinkedQueue;
public LRUObjectCacheExample(int capacity) {
lruCacheLinkedQueue = new LinkedHashMap<Employee, Boolean>(capacity, 1.0f, true) {
/**
* 
*/
private static final long   serialVersionUID    = 1L;
@Override
protected boolean removeEldestEntry(
//calling map's entry method
Map.Entry<Employee, Boolean> eldest) {
return this.size() > capacity;
}
};
}
void addDataIntoCache(Employee employee) {
lruCacheLinkedQueue.put(employee, true);
displayLRUQueue();
}
boolean checkIfDataPresentIntoLRUCaache(int data) {
return lruCacheLinkedQueue.get(data) != null;
}
void deletePageNo(int data) {
if (lruCacheLinkedQueue.get(data) != null){
lruCacheLinkedQueue.remove(data);
}
displayLRUQueue();
}
void displayLRUQueue() {
System.out.print("-------------------------------------------------------"+"\n");
System.out.print("Data into LRU Cache : ");
for (Entry<Employee, Boolean> mapEntry : lruCacheLinkedQueue.entrySet()) {
System.out.print("[" + mapEntry.getKey() + "]");
}
System.out.println("");
}
public static void main(String args[]) {
Employee employee1 = new Employee(1,"Shahbaz",29, getCurrentTimeStamp());
Employee employee2 = new Employee(2,"Amit",35,getCurrentTimeStamp());
Employee employee3 = new Employee(3,"viquar",36,getCurrentTimeStamp());
Employee employee4 = new Employee(4,"Sunny",20,getCurrentTimeStamp());
Employee employee5 = new Employee(5,"sachin",28,getCurrentTimeStamp());
Employee employee6 = new Employee(6,"Sneha",25,getCurrentTimeStamp());
Employee employee7 = new Employee(7,"chantan",19,getCurrentTimeStamp());
Employee employee8 = new Employee(8,"nitin",22,getCurrentTimeStamp());
Employee employee9 = new Employee(9,"sanuj",31,getCurrentTimeStamp());
//
LRUObjectCacheExample lru = new LRUObjectCacheExample(5);
lru.addDataIntoCache(employee5);//sachin
lru.addDataIntoCache(employee4);//Sunny
lru.addDataIntoCache(employee3);//viquar
lru.addDataIntoCache(employee2);//Amit
lru.addDataIntoCache(employee1);//Shahbaz -----capacity reached
//
lru.addDataIntoCache(employee6);/Sneha
lru.addDataIntoCache(employee7);//chantan
lru.addDataIntoCache(employee8);//nitin
lru.addDataIntoCache(employee9);//sanuj
//
lru.deletePageNo(3);
lru.deletePageNo(4);
}
private static Timestamp getCurrentTimeStamp(){
return new java.sql.Timestamp(Calendar.getInstance().getTime().getTime());
}
}

Résultats:

**Data into LRU Cache :** 
[Employee [id=1, name=Shahbaz, age=29, loginTime=2015-10-15 18:47:28.1
[Employee [id=6, name=Sneha, age=25, loginTime=2015-10-15 18:47:28.125
[Employee [id=7, name=chantan, age=19, loginTime=2015-10-15 18:47:28.125
[Employee [id=8, name=nitin, age=22, loginTime=2015-10-15 18:47:28.125
[Employee [id=9, name=sanuj, age=31, loginTime=2015-10-15 18:47:28.125

OriginalL'auteur vaquar khan

Pour O(1) accès nous avons besoin d'une table de hachage et de maintenir l'ordre, nous pouvons utiliser DLL.
De base algo - à partir de numéro de page, nous pouvons obtenir DLL nœud à l'aide de la table de hachage. Si la page existe, nous pouvons déplacer le nœud à la tête de la DLL d'autre insérez le nœud de la bibliothèque et de la table de hachage. Si la taille de la DLL est plein, nous pouvons retirer le moins récemment utilisé nœud de la queue.

Voici une implémentation basée sur liste doublement chaînée et unordered_map en C++.

#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;
//List nodeclass
class Node
{
public:
int data;
Node* next;
Node* prev;
};
//Doubly Linked list
class DLList
{
public:
DLList()
{
head = NULL;
tail = NULL;
count = 0;
}
~DLList() {}
Node* addNode(int val);
void print();
void removeTail();
void moveToHead(Node* node);
int size()
{
return count;
}
private:
Node* head;
Node* tail;
int count;
};
//Function to add a node to the list
Node* DLList::addNode(int val)
{
Node* temp = new Node();
temp->data = val;
temp->next = NULL;
temp->prev = NULL;
if ( tail == NULL )
{
tail = temp;
head = temp;
}
else
{
head->prev = temp;
temp->next = head;
head = temp;
}
count++;
return temp;
}
void DLList::moveToHead(Node* node)
{
if (head == node)
return;
node->prev->next = node->next;
if (node->next != NULL)
{
node->next->prev = node->prev;
}
else
{
tail = node->prev;
}
node->next = head;
node->prev = NULL;
head->prev = node;
head = node;
}
void DLList::removeTail()
{
count--;
if (head == tail)
{
delete head;
head = NULL;
tail = NULL;
}
else
{
Node* del = tail;
tail = del->prev;
tail->next = NULL;
delete del;
}
}
void DLList::print()
{
Node* temp = head;
int ctr = 0;
while ( (temp != NULL) && (ctr++ != 25) )
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
class LRUCache
{
public:
LRUCache(int aCacheSize);
void fetchPage(int pageNumber);
private:
int cacheSize;
DLList dlist;
unordered_map< int, Node* > directAccess;
};
LRUCache::LRUCache(int aCacheSize):cacheSize(aCacheSize) { }
void LRUCache::fetchPage(int pageNumber)
{
unordered_map< int, Node* >::const_iterator it = directAccess.find(pageNumber);
if (it != directAccess.end())
{
dlist.moveToHead( (Node*)it->second);
}
else
{
if (dlist.size() == cacheSize-1)
dlist.removeTail();
Node* node = dlist.addNode(pageNumber);
directAccess.insert(pair< int, Node* >(pageNumber,node));
}
dlist.print();
}
int main()
{
LRUCache lruCache(10);
lruCache.fetchPage(5);
lruCache.fetchPage(7);
lruCache.fetchPage(15);
lruCache.fetchPage(34);
lruCache.fetchPage(23);
lruCache.fetchPage(21);
lruCache.fetchPage(7);
lruCache.fetchPage(32);
lruCache.fetchPage(34);
lruCache.fetchPage(35);
lruCache.fetchPage(15);
lruCache.fetchPage(37);
lruCache.fetchPage(17);
lruCache.fetchPage(28);
lruCache.fetchPage(16);
return 0;
}

OriginalL'auteur learner

class LRU {
Map<String, Integer> ageMap = new HashMap<String, Integer>();
int age = 1;
void addElementWithAge(String element) {
ageMap.put(element, age);
age++;
}
String getLeastRecent(Map<String, Integer> ageMap) {
Integer oldestAge = (Integer) ageMap.values().toArray()[0];
String element = null;
for (Entry<String, Integer> entry : ageMap.entrySet()) {
if (oldestAge >= entry.getValue()) {
oldestAge = entry.getValue();
element = entry.getKey();
}
}
return element;
}
public static void main(String args[]) {
LRU obj = new LRU();
obj.addElementWithAge("M1");
obj.addElementWithAge("M2");
obj.addElementWithAge("M3");
obj.addElementWithAge("M4");
obj.addElementWithAge("M1");
}
}

OriginalL'auteur anonymous