Cache LRU in Java con operazioni Generics e O (1)

Questa è una domanda che emerge molto nelle interviste di lavoro. L’idea è di definire una struttura dati invece di usare LinkedHashMap di Java.

Una cache LRU cancella la voce meno recente utilizzata per inserirne una nuova. Quindi, dato il seguente scenario:

A - B - C - D - E 

Dove A è l’elemento meno utilizzato di recente, se dovessimo inserire F, dobbiamo rimuovere A.

Questo può essere facilmente implementato se manteniamo una HashMap con le voci della cache di (chiave, valore) e una lista separata che contiene la chiave e il tempo di utilizzo degli elementi. Tuttavia, dovremmo interrogare l’elenco per trovare l’elemento meno recente utilizzato, con una potenziale complessità di tempo O (n).

In che modo questa struttura può essere implementata in Java per oggetti generici e operazioni O (1)?

Questo è diverso dal ansible duplicato in quanto si concentra sull’efficienza (O (1) ops) e sull’implementazione della struttura dati stessa, non sull’estensione di Java.

Dalla domanda stessa, possiamo vedere che il problema delle operazioni O (n) si verifica quando si esegue una query sull’elenco collegato. Pertanto, abbiamo bisogno di una struttura dati alternativa. Dobbiamo essere in grado di aggiornare l’ultima ora di accesso degli elementi da HashMap senza effettuare ricerche.

Possiamo mantenere due strutture dati separate. Una HashMap con coppie (chiave, puntatore) e una lista doppiamente collegata che funzionerà come coda prioritaria per la cancellazione e memorizza i valori. Da HashMap, possiamo puntare a un elemento nella lista doppiamente collegata e aggiornare il suo tempo di recupero. Poiché passiamo direttamente da HashMap all’elemento nell’elenco, la nostra complessità temporale rimane a O (1)

Ad esempio, la nostra lista doppiamente collegata può essere simile a:

 least_recently_used -> A <-> B <-> C <-> D <-> E <- most_recently_used 

Dobbiamo mantenere un puntatore agli elementi LRU e MRU. I valori delle voci saranno memorizzati nell'elenco e quando interrogeremo la HashMap, otterremo un puntatore alla lista. Su get (), dobbiamo mettere l'elemento nella parte più a destra dell'elenco. In put (chiave, valore), se la cache è piena, dobbiamo rimuovere l'elemento sul lato sinistro dell'elenco sia dalla lista che da HashMap.

Quanto segue è un'implementazione di esempio in Java:

 public class LRUCache{ // Define Node with pointers to the previous and next items and a key, value pair class Node { Node previous; Node next; T key; U value; public Node(Node previous, Node next, T key, U value){ this.previous = previous; this.next = next; this.key = key; this.value = value; } } private HashMap> cache; private Node leastRecentlyUsed; private Node mostRecentlyUsed; private int maxSize; private int currentSize; public LRUCache(int maxSize){ this.maxSize = maxSize; this.currentSize = 0; leastRecentlyUsed = new Node(null, null, null, null); mostRecentlyUsed = leastRecentlyUsed; cache = new HashMap>(); } public V get(K key){ Node tempNode = cache.get(key); if (tempNode == null){ return null; } // If MRU leave the list as it is else if (tempNode.key == mostRecentlyUsed.key){ return mostRecentlyUsed.value; } // Get the next and previous nodes Node nextNode = tempNode.next; Node previousNode = tempNode.previous; // If at the left-most, we update LRU if (tempNode.key == leastRecentlyUsed.key){ nextNode.previous = null; leastRecentlyUsed = nextNode; } // If we are in the middle, we need to update the items before and after our item else if (tempNode.key != mostRecentlyUsed.key){ previousNode.next = nextNode; nextNode.previous = previousNode; } // Finally move our item to the MRU tempNode.previous = mostRecentlyUsed; mostRecentlyUsed.next = tempNode; mostRecentlyUsed = tempNode; mostRecentlyUsed.next = null; return tempNode.value; } public void put(K key, V value){ if (cache.containsKey(key)){ return; } // Put the new node at the right-most end of the linked-list Node myNode = new Node(mostRecentlyUsed, null, key, value); mostRecentlyUsed.next = myNode; cache.put(key, myNode); mostRecentlyUsed = myNode; // Delete the left-most entry and update the LRU pointer if (currentSize == maxSize){ cache.remove(leastRecentlyUsed.key); leastRecentlyUsed = leastRecentlyUsed.next; leastRecentlyUsed.previous = null; } // Update cache size, for the first added entry update the LRU pointer else if (currentSize < maxSize){ if (currentSize == 0){ leastRecentlyUsed = myNode; } currentSize++; } } } 

Seguono l’implementazione che supera i test del leetcode questiton + test unitari semplici.

Ho fatto una richiesta di pull con questo a: https://github.com/haoel/leetcode/pull/90/files

LRUCache.java

 import java.util.LinkedHashMap; import java.util.Iterator; public class LRUCache { private int capacity; private LinkedHashMap map; public LRUCache(int capacity) { this.capacity = capacity; this.map = new LinkedHashMap<>(); } public int get(int key) { Integer value = this.map.get(key); if (value == null) { value = -1; } else { this.set(key, value); } return value; } public void set(int key, int value) { if (this.map.containsKey(key)) { this.map.remove(key); } else if (this.map.size() == this.capacity) { Iterator it = this.map.keySet().iterator(); it.next(); it.remove(); } map.put(key, value); } } 

LRUCacheTest.java :

 import java.util.ArrayList; import org.junit.Test; import static org.junit.Assert.*; public class LRUCacheTest { private LRUCache c; public LRUCacheTest() { this.c = new LRUCache(2); } @Test public void testCacheStartsEmpty() { assertEquals(c.get(1), -1); } @Test public void testSetBelowCapacity() { c.set(1, 1); assertEquals(c.get(1), 1); assertEquals(c.get(2), -1); c.set(2, 4); assertEquals(c.get(1), 1); assertEquals(c.get(2), 4); } @Test public void testCapacityReachedOldestRemoved() { c.set(1, 1); c.set(2, 4); c.set(3, 9); assertEquals(c.get(1), -1); assertEquals(c.get(2), 4); assertEquals(c.get(3), 9); } @Test public void testGetRenewsEntry() { c.set(1, 1); c.set(2, 4); assertEquals(c.get(1), 1); c.set(3, 9); assertEquals(c.get(1), 1); assertEquals(c.get(2), -1); assertEquals(c.get(3), 9); } } 

removeEldestEntry () implementazione alternativa

Non sono sicuro che ne valga la pena dato che richiede lo stesso numero di linee, ma qui va a finire:

 import java.util.LinkedHashMap; import java.util.Iterator; import java.util.Map; class LinkedhashMapWithCapacity extends LinkedHashMap { private int capacity; public LinkedhashMapWithCapacity(int capacity) { this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return this.size() > this.capacity; } } public class LRUCache { private LinkedhashMapWithCapacity map; public LRUCache(int capacity) { this.map = new LinkedhashMapWithCapacity<>(capacity); } public int get(int key) { Integer value = this.map.get(key); if (value == null) { value = -1; } else { this.set(key, value); } return value; } public void set(int key, int value) { if (this.map.containsKey(key)) this.map.remove(key); this.map.get(key); } } 

La LinkedHashMap è stata progettata pensando a questo

Dal javadocs:

Viene fornito un costruttore speciale per creare una mappa hash collegata il cui ordine di iterazione è l’ordine in cui le sue voci sono state l ‘ultimo accesso, dall’accesso meno recente a quello più recente (accesso-ordine). Questo tipo di mappa è adatto alla creazione di cache LRU. Invocare put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, o unire i risultati dei metodi in un accesso alla voce corrispondente (supponendo che esista al termine del richiamo). I metodi replace sostituiscono solo un accesso alla voce se il valore viene sostituito. Il metodo putAll genera un accesso alla voce per ogni mapping nella mappa specificata, nell’ordine in cui i mapping dei valori-chiave sono forniti dall’iter iteratore della voce della mappa specificata. Nessun altro metodo genera accessi alle voci. In particolare, le operazioni sulle viste di raccolta non influiscono sull’ordine di iterazione della mappa di supporto.

Il metodo removeEldestEntry (Map.Entry) può essere sovrascritto per imporre un criterio per la rimozione automatica dei mapping stantii quando vengono aggiunti nuovi mapping alla mappa.

Utilizzando una pila e una HashMap:

 import java.util.HashMap; import java.util.Stack; public class LRU { private HashMap lruList; private Stack stackOrder; private int capacity; LRU(int capacity){ this.capacity = capacity; this.lruList = new HashMap(capacity); this.stackOrder = new Stack(); } public void put(String key, Object value){ if(lruList.containsKey(key) || this.capacity < lruList.size() + 1) { if(lruList.containsKey(key)){ String remove = key; }else{ String remove = this.stackOrder.firstElement(); } this.stackOrder.removeElement(remove); this.lruList.remove(remove); } this.lruList.put(key, value); this.stackOrder.add(key); } public Stack get(){ return this.stackOrder; } public Object get(String key){ Object value = lruList.get(key); put(key, value); return value; } } public static void main(String[] args) { LRU lru = new LRU(3); lru.put("k1","v1"); lru.put("k2","v2"); lru.put("k3","v3"); System.out.println(lru.get()); lru.get("k1"); System.out.println(lru.get()); lru.put("k4","v4"); System.out.println(lru.get()); } 

Produzione:

[k1, k2, k3]

[k2, k3, k1]

[k3, k1, k4]

 /*Java implementation using Deque and HashMap */ interface Cache { V get(K key) ; void set(K key, V value); } class Node { K key; V value; public Node (K key, V value) { this.key = key; this.value = value; } } public class LRUCache  implements Cache{ Deque> dq = new LinkedList<>(); Map> map = new HashMap<>(); static int SIZE; public LRUCache(int size) { this.SIZE = size; } public V get(K key) { Node result = map.get(key); if(result != null) { dq.remove(result); dq.addFirst(result); System.out.println("Get " +key +" : " +result.value); return result.value; } else { System.out.println("Cache miss"); return null; } } public void set(K key, V value) { System.out.println("Set " +key +" : " +value); Node result = map.get(key); if(result != null) { result.value = value; map.put(key, result); dq.remove(result); dq.addFirst(result); System.out.println("Updated frame " +key+" as " + value); } else { if(dq.size() == SIZE) { Node toRemove = dq.removeLast(); map.remove(toRemove); System.out.println("Frame removed " +toRemove.key +" : " +toRemove.value); } Node newNode = new Node(key, value); dq.addFirst(newNode); map.put(key, newNode); System.out.println("Frame added " + key + " : " +value); } } public static void main(String[] args) { Cache lru = new LRUCache<>(5); lru.get(2); lru.set(1, 11); lru.set(2, 22); lru.get(2); lru.set(3, 33); lru.set(4, 44); lru.set(5, 55); lru.get(2); lru.get(1); lru.set(6, 66); } } 

@templatetypedef

 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 

accessOrder – la modalità di ordinazione – true per l’ordine di accesso, false per l’ordine di inserimento

Idea

la cache non è altro che arrayList circolare. Questa lista contiene Entry. quando vengono aggiunte nuove voci alla fine dell’elenco. Ciò significa elemento utilizzato meno di recente al primo. Supponi di riutilizzare qualsiasi elemento, quindi scollegalo dall’elenco e aggiungilo alla fine.

Al fine di ottenere qualsiasi elemento di cui abbiamo bisogno per attraversare la lista che richiede la complessità del tempo O (n). Per evitarlo, sto mantenendo HashMap>. Qui k è la chiave e IndexNode conterrà un puntatore alla voce nella lista. quindi possiamo ottenere la complessità del tempo O (1).

soluzione di lavoro

 package lrucache; import java.util.HashMap; public class LRUCache { private transient Entry header = new Entry(null, null, null, null); public HashMap>> indexMap = new HashMap>>(); private final int CACHE_LIMIT = 3; private int size; public LRUCache() { header.next = header.previous = header; this.size = 0; } public void put(K key,V value){ Entry newEntry = new Entry(key,value,null,null); addBefore(newEntry, header); } private void addBefore(Entry newEntry,Entry entry){ if((size+1)<(CACHE_LIMIT+1)){ newEntry.next=entry; newEntry.previous=entry.previous; IndexNode> indexNode = new IndexNode>(newEntry); indexMap.put(newEntry.key, indexNode); newEntry.previous.next=newEntry; newEntry.next.previous=newEntry; size++; }else{ Entry entryRemoved = remove(header.next); indexMap.remove(entryRemoved.key); addBefore(newEntry, entry); } } public void get(K key){ if(indexMap.containsKey(key)){ Entry newEntry = remove(indexMap.get(key).pointer); addBefore(newEntry,header); }else{ System.out.println("No such element was cached. Go and get it from Disk"); } } private Entry remove(Entry entry){ entry.previous.next=entry.next; entry.next.previous = entry.previous; size--; return entry; } public void display(){ for(Entry curr=header.next;curr!=header;curr=curr.next){ System.out.println("key : "+curr.key+" value : " + curr.value); } } private static class IndexNode{ private Entry pointer; public IndexNode(Entry pointer){ this.pointer = pointer; } } private static class Entry { K key; V value; Entry previous; Entry next; Entry(K key, V value, Entry next, Entry previous) { this.key = key; this.value = value; this.next = next; this.previous = previous; } } public static void main(String[] args) { LRUCache cache = new LRUCache(); cache.put("abc", 1); //cache.display(); cache.put("def", 2); cache.put("ghi", 3); cache.put("xyz", 4); cache.put("xab", 5); cache.put("xbc", 6); cache.get("xyz"); cache.display(); System.out.println(cache.indexMap); } } 

produzione

 key : xab value : 5 key : xbc value : 6 key : xyz value : 4 {[email protected], [email protected], [email protected]} 

possiamo usare LinkedHashMap .. ha funzionalità per rimuovere la voce più vecchia

 import java.util.LinkedHashMap; import java.util.Map; public LRUCache extends LinkedHashMap { private int cacheSize; public LRUCache(int cacheSize) { super(16, 0.75, true); this.cacheSize = cacheSize; } protected boolean removeEldestEntry(Map.Entry eldest) { return size() >= cacheSize; } } 

L’unico problema è che per impostazione predefinita l’ordine dell’elenco collegato è l’ordine di inserimento, non l’accesso. Tuttavia, uno dei costruttori espone un’opzione, usa invece l’ordine di accesso.

Scrivo solo questa soluzione generica molto semplice, anche se questa non è una Thread sicura.

LRUCacheDemo.java (class pubblica)

 import java.io.*; import java.util.*; /* We can keep two separate data structures. A HashMap with (Key,Pointer) pairs and a doubly linked list which will work as the priority queue for deletion and store the Values. From the HashMap, we can point to an element in the doubly linked list and update its' retrieval time. Because we go directly from the HashMap to the item in the list, our time complexity remains at O(1) */ public class LRUCacheDemo { public static void main(String args[]) { LRUCache lru = new LRUCache<>(3); for(int i=1; i<=9; ++i) { lru.put(i, 100*i+10*i+i); //i iii } lru.get(8); /* for(Map.Entry entry : lru.entrySet()) { System.out.printf("\n%1$-5s %2$-5s", entry.getKey(), entry.getValue()); } */ System.out.println("LRU : " + lru); } } class LRUCache extends LinkedHashMap { private final int CACHE_SIZE; //NOTE : LinkedHashMap have already given implementation for LRU, this class has just used those method //See http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedHashMap.java#LinkedHashMap // LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) // accessOrder - to maintain in order of elements from least-recently accessed to most-recently. LRUCache(final int sizeIn) { super(sizeIn, 0.75F, true); this.CACHE_SIZE = sizeIn; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > this.CACHE_SIZE; /* Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest entry each time a new one is added. This is useful if the map represents a cache. */ } } 

OPERAZIONE :

 LRU : {7=777, 9=999, 8=888} 

Ecco l’implementazione di Java con Generics e LinkedHashMap e la complessità di O (1) su get() e put() .

 import java.util.LinkedHashMap; public class LRUCache { private LinkedHashMap lruCacheMap; private final int capacity; private final boolean SORT_BY_ACCESS = true; private final float LOAD_FACTOR = 0.75F; public LRUCache(int capacity){ this.capacity = capacity; this.lruCacheMap = new LinkedHashMap<>(capacity, LOAD_FACTOR, SORT_BY_ACCESS); } public V get(K k){ return lruCacheMap.get(k); } public void put(K k, V v){ if(lruCacheMap.containsKey(k)){ lruCacheMap.remove(k); }else if(lruCacheMap.size() >= capacity){ lruCacheMap.remove(lruCacheMap.keySet().iterator().next()); } lruCacheMap.put(k, v); } public void printSequence(){ System.out.println(lruCacheMap.keySet()); } } 

Questo è il codice per testarlo:

 import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class TestLruCache { static class MyHardDrive { Map resources = new HashMap<>(); MyHardDrive(){ for(Character i='A'; i<='Z'; i++){ resources.put(i.toString(), new Object()); } } Object loadResource(String name){ return resources.get(name); } } public static void main(String[] args) { MyHardDrive hd = new MyHardDrive(); LRUCache cache = new LRUCache<>(4); for(String key: Arrays.asList("A","B","C","A","D","E","F","E","F","G","A")){ Object object = cache.get(key); if(object==null){ object = hd.loadResource(key); cache.put(key, object); } cache.printSequence(); } } } 

Ecco l’implementazione di Java

 import java.util.HashMap; import java.util.Map; import com.nadeem.app.dsa.adt.Cache; // Kind of linkedHashMap public class LRUCache  implements Cache { private int capacity; private Node head, tail; private Map> map; private static final int DEFAULT_CAPACITY = 10; public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap>(); } public LRUCache() { this(DEFAULT_CAPACITY); } @Override public V get(K key) { V result = null; Node node = this.map.get(key); if (node != null) { result = node.value; remove(node); addAsHead(node); } return result; } @Override public void set(K key, V value) { Node node = this.map.get(key); if (node == null) { Node temp = new Node(key, value); if (this.map.size() < this.capacity) { addAsHead(temp); } else { this.map.remove(this.tail.key); remove(this.tail); addAsHead(temp); } this.map.put(key, temp); } else { node.value = value; remove(node); addAsHead(node); } } private void remove(Node node) { if (node.pre == null) { this.head = node.next; } else { node.pre.next = node.next; } if (node.next == null) { this.tail = node.pre; } else { node.next.pre = node.pre; } } private void addAsHead(Node node) { if (this.head == null) { this.head = node; this.tail = node; } else { this.head.pre = node; node.next = this.head; this.head = node; } } @Override public void remove(K key) { Node node = this.map.get(key); if (node != null) { this.remove(node); } } private static class Node  { public S key; public T value; Node pre; Node next; Node(S key, T value) { this.key = key; this.value = value; } } @Override public int size() { return this.map.size(); } 

}

Ecco il test unitario

 public class LRUCacheTest { private LRUCache cache; @Before public void doBeforeEachTestCase() { this.cache = new LRUCache(2); } @Test public void setTest() { this.cache.set(1, 1); assertThat(this.cache.size(), equalTo(1)); assertThat(this.cache.get(1), equalTo(1)); this.cache.set(2, 2); assertThat(this.cache.size(), equalTo(2)); assertThat(this.cache.get(2), equalTo(2)); this.cache.set(3, 3); assertThat(this.cache.size(), equalTo(2)); assertThat(this.cache.get(3), equalTo(3)); this.cache.set(1, 3); assertThat(this.cache.size(), equalTo(2)); assertThat(this.cache.get(1), equalTo(3)); assertThat(this.cache.get(4), equalTo(null)); } 

}

 public class LeastRecentlyUsed { public static  Map leastRecentlyUsedCache(final int maxSize) { return new LinkedHashMap(maxSize , 0.7f, true) { private static final long serialVersionUID = -3588047435434569014L; @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } }; } public static void main(String[] args) { Map leastRecentlyUsed = LeastRecentlyUsed.leastRecentlyUsedCache(3); leastRecentlyUsed.put("Robert", "Raj"); leastRecentlyUsed.put("Auzi", "Aiz"); leastRecentlyUsed.put("Sandy", "S"); leastRecentlyUsed.put("Tript", "tty"); System.out.println(leastRecentlyUsed); } } 

Come K e altri hanno detto che questo può essere fatto con la class LinkedHashMap . In una compressione puoi ottenere una versione minima in 15 righe di codice.

@Ciro Santilli , perché non tagliare la definizione di class extra? Se i test usati sono simili alle altre mappe java, non dovremmo alias quel metodo con un metodo set, che in realtà ci aspetteremmo di restituire dalla mappa una sorta di set view.

 import java.utils.LinkedHashMap import java.util.Map; public class LRUCache extends LinkedHashMap { private int maxSize; // and other constructors for load factor and hashtable capacity public LRUCache(int initialCapacity, float loadFactor, int maxSize) { super(initialCapacity, loadFactor, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } // I don't like this. set should return a set put should put an item public V set(K key, V value) { put(key, value) } } 

vedere qui e nella documentazione per ulteriori informazioni.