Caché LRU en Java con operaciones genéricas y O (1)

Esta es una pregunta que surge mucho en las entrevistas de trabajo. La idea es definir una estructura de datos en lugar de usar Java incorporado en LinkedHashMap.

Un caché LRU elimina la entrada que se utilizó menos recientemente para insertar una nueva. Entonces, dado el siguiente escenario:

A - B - C - D - E 

Donde A es el elemento menos usado recientemente, si insertáramos F, debemos eliminar A.

Esto se puede implementar fácilmente si mantenemos un HashMap con las entradas de caché por (clave, valor) y una lista separada que contiene la clave de los elementos y el tiempo de uso. Sin embargo, deberíamos consultar la lista para encontrar el elemento menos usado recientemente, con una complejidad potencial de tiempo O (n).

¿Cómo se puede implementar esta estructura en Java para objetos generics y operaciones O (1)?

Esto es diferente del posible duplicado en que se enfoca en la eficiencia (O (1) operaciones) y en la implementación de la estructura de datos en sí, no en la extensión de Java.

A partir de la pregunta en sí, podemos ver que el problema de las operaciones O (n) surge al consultar la lista vinculada. Por lo tanto, necesitamos una estructura de datos alternativa. Necesitamos poder actualizar el último tiempo de acceso de los elementos desde HashMap sin buscar.

Podemos mantener dos estructuras de datos separadas. Un HashMap con (clave, puntero) pares y una lista doblemente enlazada que funcionará como la cola de prioridad para eliminar y almacenar los valores. Desde el HashMap, podemos apuntar a un elemento en la lista doblemente enlazada y actualizar su tiempo de recuperación. Como pasamos directamente del HashMap al elemento de la lista, nuestra complejidad de tiempo permanece en O (1)

Por ejemplo, nuestra lista doblemente enlazada puede verse como:

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

Necesitamos mantener un puntero a los elementos LRU y MRU. Los valores de las entradas se almacenarán en la lista y cuando consultemos el HashMap, obtendremos un puntero a la lista. En get (), debemos colocar el elemento en el lado más a la derecha de la lista. En la colocación (clave, valor), si la memoria caché está llena, debemos eliminar el elemento del extremo izquierdo de la lista tanto de la lista como del HashMap.

El siguiente es un ejemplo de implementación en 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++; } } } 

La implementación que pasa las pruebas de la pregunta de leetcode + pruebas de unidad simples sigue.

Hice una solicitud de extracción con esto en: 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 () implementación alternativa

No estoy seguro de que valga la pena, ya que se necesita el mismo número de líneas, pero aquí hay que completarlo:

 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); } } 

El LinkedHashMap diseñado con eso en mente

De los javadocs:

Se proporciona un constructor especial para crear un mapa hash vinculado cuyo orden de iteración es el orden en el que se accedió por última vez a sus entradas, desde el que se accedió por última vez hasta el más reciente (orden de acceso). Este tipo de mapa es adecuado para construir memorias caché LRU. Al invocar los métodos put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent o merge se obtiene un acceso a la entrada correspondiente (suponiendo que exista después de que finalice la invocación). Los métodos de reemplazo solo dan como resultado un acceso a la entrada si se reemplaza el valor. El método putAll genera un acceso de entrada para cada asignación en el mapa especificado, en el orden en que las asignaciones de clave-valor son proporcionadas por el iterador del conjunto de entrada del mapa especificado. Ningún otro método genera accesos de entrada. En particular, las operaciones en vistas de colección no afectan el orden de iteración del mapa de respaldo.

El método removeEldestEntry (Map.Entry) puede anularse para imponer una política para eliminar mapeos obsoletos automáticamente cuando se agregan nuevas asignaciones al mapa.

Usando una Pila y un 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()); } 

Salida:

[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 – el modo de ordenamiento – true para access-order, false para insertion-order

Idea

caché no es más que circular arrayList. Esta lista contiene entrada. cuando lleguen nuevas entradas, agregue al final de la lista. Eso significa que el elemento menos usado recientemente en el primero. Supongamos que si está reutilizando un elemento, desvinculalo de la lista y lo agrega al final.

Para obtener cualquier elemento necesitamos atravesar la lista que toma la complejidad del tiempo O (n). Para evitar esto, estoy manteniendo HashMap>. Aquí k es la clave e IndexNode contendrá un puntero a la entrada en la lista. para que podamos obtener la complejidad del tiempo O (1).

solución de trabajo

 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); } } 

salida

 key : xab value : 5 key : xbc value : 6 key : xyz value : 4 {xab=lrucache.LRUCache$IndexNode@c3d9ac, xbc=lrucache.LRUCache$IndexNode@7d8bb, xyz=lrucache.LRUCache$IndexNode@125ee71} 

podemos usar LinkedHashMap … tiene una función para eliminar la entrada más antigua

 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; } } 

El único problema es que, por defecto, el orden de la lista enlazada es el orden de inserción, no el acceso. Sin embargo, uno de los constructores expone una opción utiliza la orden de acceso en su lugar.

Acabo de escribir esta solución genérica muy simple, aunque esta no es segura para Thread .

LRUCacheDemo.java (clase pública)

 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. */ } } 

O / P:

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

Aquí está la implementación de Java con Generics y LinkedHashMap , y la complejidad de O (1) en get() y 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()); } } 

Este es el código para probarlo:

 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(); } } } 

Aquí está la implementación de 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(); } 

}

Aquí está la prueba de unidad

 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); } } 

Como K y Otros han dicho, esto se puede hacer con la clase LinkedHashMap . En un apretón puede obtener una versión mínima en 15 líneas de código.

@Ciro Santilli , ¿por qué no cortar la definición de clase adicional? Si las pruebas utilizadas se colocan como otros mapas de Java, no tendríamos que aliar ese método con un método de conjunto, que en realidad esperaríamos devolver algún tipo de vista de conjunto del mapa.

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

Ver aquí y en los documentos para más.

    Intereting Posts