J'implémente le cache LRU en Java en utilisant ma propre implémentation de DoublyLinkedList avec un noeud ayant une clé entière et des valeurs où la clé indique l'identifiant de la page et la valeur indique son emplacement sur le disque. En outre, j'utilise un Hashmap pour l'accès O (1). Je connais les bases de l'implémentation suivantes:Implémenter une action lors de la mise en oeuvre de cache java dans LRU
Si la clé demandée est un hit de cache, alors renvoyez sa valeur (c'est-à-dire son emplacement) et déplacez ce noeud vers l'avant de la liste DoublyLinkedList.
J'ai un doute sur l'autre aspect important quand c'est un échec. Selon diverses ressources, quand c'est un échec alors le numéro de page qui est la clé dans mon cas est mis à la tête de LinkedList et en faisant cela, si nous rencontrons la capacité d'être plein, alors nous supprimons l'élément à la fin puis entrez-le à l'avant. Maintenant, aux fins de la mise en œuvre, quelle devrait être la 'valeur' d'un tel numéro de page (c'est-à-dire la clé) lorsque je l'amène dans le cache? Devrais-je le mettre à la poubelle? Dans mon implémentation ci-dessous de la méthode 'get', je retourne -1 actuellement sur un échec.
De même, dans le code de production pratique du cache LRU, le cache contient-il les numéros de page ou les valeurs réelles stockées à ces numéros de page? T
Aidez-moi à clarifier cet aspect. Merci.
import java.util.HashMap;
public class LRU {
private static class Node {
Node previous;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
Node head = null;
Node tail = null;
HashMap<Integer, Node> hmap = new HashMap<>();
public int get(int key) {
if (hmap.containsKey(key)) {
Node n = hmap.get(key);
remove(n);
moveToFront(n);
return n.value;
}
return -1;
}
public void remove(Node n) {
// if n is head
if (n.previous == null) {
head = head.next;
} else {
n.previous.next = n.next;
}
//if n is tail
if (n.next == null) {
tail = n.previous;
} else {
n.next.previous = n.previous;
}
}
public void moveToFront(Node n) {
if(n==head)
return;
if(n.next==null)
{
n.previous.next=n.next;
tail = n.previous;
n.previous = null;
n.next = head;
head = n;
}
else {
n.previous.next=n.next;
n.next.previous=n.previous;
}
}
public void set(int key, int value) {
}
}
Dans le "code de production pratique", vous utilisez 'LinkedHashMap' au lieu de déployer votre propre code. De plus, cela n'a aucun sens d'insérer des nœuds dénotant des entrées inexistantes. À ce stade, vous avez seulement décrit une sorte de carte, sans indiquer ce que signifient les «numéros de page» ou les «valeurs réelles stockées à ces numéros de page». Donc, ne posez pas de questions à ce sujet, vous êtes celui qui a décidé qu'un cache est nécessaire pour ces données. – Holger
S'il vous plaît, allez-y doucement. Rookie ici. –
Cela n'a rien à voir avec être "recrue" pour comprendre que nous ne pouvons pas répondre à des questions sur des choses spécifiques à votre application que vous n'avez pas expliqué. Créer un cache LRU est aussi simple que de sous-classer 'LinkedHashMap', en utilisant [ce constructeur] (https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#LinkedHashMap-int-float -boolean-) avec 'true', donc les hits déplacent les entrées vers l'avant et remplacent [' removeEldestEntry'] (https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html# removeEldestEntry-java.util.Map.Entry-) dont la documentation montre déjà comment faire une taille fixe. – Holger