¿Cómo implementar un caché de uso menos frecuente (LFU)?

Nuestro team de trabajo ha estado mucho tiempo buscando la solución a tus dudas, te ofrecemos la solución de modo que esperamos resultarte de mucha apoyo.

Solución:

Puede beneficiarse de la implementación LFU de ActiveMQ: LFUCache

Han proporcionado una buena funcionalidad.

Creo que la estructura de datos de LFU debe combinar la cola de prioridad (para mantener un acceso rápido al elemento lfu) y el mapa hash (para proporcionar un acceso rápido a cualquier elemento por su key); Sugeriría la siguiente definición de nodo para cada objeto almacenado en caché:

class Node 
   // access key
   private int key;
   // counter of accesses
   private int numAccesses;
   // current position in pq
   private int currentPos;
   // item itself
   private T item;
   //getters, setters, constructors go here

Necesitas key para referirse a un artículo. Necesitas numAccesses como un key para la cola de prioridad. Necesitas currentPos para poder encontrar rápidamente una posición pq del artículo key. Ahora organizas el mapa hash (key(Integer) -> nodo(Node)) para acceder rápidamente a los elementos y la cola de prioridad basada en el montón mínimo utilizando el número de accesos como prioridad. Ahora puede realizar todas las operaciones muy rápidamente (acceder, agregar un nuevo elemento, actualizar el número de accesos, eliminar lfu). Debe escribir cada operación con cuidado, de modo que mantenga todos los nodos consistentes (su número de accesos, su posición en pq y su existencia en el mapa hash). Todas las operaciones funcionarán con una complejidad de tiempo promedio constante, que es lo que espera del caché.

1. Según yo, la mejor manera de implementar un caché de objetos usados ​​más recientemente sería incluir una nueva variable como ‘latestTS’ para cada objeto. TS significa marca de tiempo.

   // A static método que devuelve la fecha y la hora actuales en milisegundos desde el 1 de enero de 1970 long latestTS = System.currentTimeMillis();

2. ConcurrentLinkedHashMap aún no está implementado en colecciones Java simultáneas. (Ref: API de recopilación simultánea de Java). Sin embargo, puede probar y usar ConcurrentHashMap y DoublyLinkedList

3. Sobre el caso a considerar: en tal caso, como dije, puede declarar la variable LatestTS, según el valor de la variable LatestTS, puede eliminar una entrada y agregar el nuevo objeto. (No olvide actualizar la frecuencia y los últimos TS del nuevo objeto agregado)

Como mencionó, puede usar LinkedHashMap ya que brinda acceso a elementos en O (1) y también obtiene el orden transversal. Por favor, busque el siguiente código para LFU Cache: (PS: El siguiente código es la respuesta a la pregunta del título, es decir, “Cómo implementar LFU Cache”).

import java.util.LinkedHashMap;
import java.util.Map;

public class LFUCache 

    class CacheEntry
    
        private String data;
        private int frequency;

        // default constructor
        private CacheEntry()
        

        public String getData() 
            return data;
        
        public void setData(String data) 
            this.data = data;
        

        public int getFrequency() 
            return frequency;
        
        public void setFrequency(int frequency) 
            this.frequency = frequency;
               

    

    private static int initialCapacity = 10;

    private static LinkedHashMap cacheMap = new LinkedHashMap();
    /* LinkedHashMap is used because it has features of both HashMap and LinkedList. 
     * Thus, we can get an entry in O(1) and also, we can iterate over it easily.
     * */

    public LFUCache(int initialCapacity)
    
        this.initialCapacity = initialCapacity;
    

    public void addCacheEntry(int key, String data)
    
        if(!isFull())
        
            CacheEntry temp = new CacheEntry();
            temp.setData(data);
            temp.setFrequency(0);

            cacheMap.put(key, temp);
        
        else
        
            int entryKeyToBeRemoved = getLFUKey();
            cacheMap.remove(entryKeyToBeRemoved);

            CacheEntry temp = new CacheEntry();
            temp.setData(data);
            temp.setFrequency(0);

            cacheMap.put(key, temp);
        
    

    public int getLFUKey()
    
        int key = 0;
        int minFreq = Integer.MAX_VALUE;

        for(Map.Entry entry : cacheMap.entrySet())
        
            if(minFreq > entry.getValue().frequency)
            
                key = entry.getKey();
                minFreq = entry.getValue().frequency;
                       
        

        return key;
    

    public String getCacheEntry(int key)
    
        if(cacheMap.containsKey(key))  // cache hit
        
            CacheEntry temp = cacheMap.get(key);
            temp.frequency++;
            cacheMap.put(key, temp);
            return temp.data;
        
        return null; // cache miss
    

    public static boolean isFull()
    
        if(cacheMap.size() == initialCapacity)
            return true;

        return false;
    

Calificaciones y comentarios

Nos encantaría que puedieras dar difusión a este escrito si te valió la pena.

---

---

Utiliza Nuestro Buscador