Cómo implementar la memoria caché utilizada más recientemente

Question

¿Cuál sería la mejor forma de implementar la memoria caché utilizada más recientemente?

Estos son los requisitos y restricciones ...

• objetos se almacenan como pares clave/valor del objeto/objeto, por lo que la interfaz sería un poco como Hashtable obtener/poner
• Una llamada a ' get 'marcaría ese objeto como el usado más recientemente.
• En cualquier momento, el objeto usado menos recientemente se puede eliminar de la caché.
• Las búsquedas y las purgas deben ser rápidas (como en Hashtable rápido)
• La cantidad de Objetos puede ser grande, por lo que las búsquedas de lista no son lo suficientemente buenas.
• La implementación debe realizarse utilizando JavaME, por lo que hay poco margen para usar código de terceros o clases de biblioteca ordenadas de las bibliotecas estándar de Java. Por esta razón, estoy buscando más respuestas algorítmicas que recomendaciones de soluciones off-the-peg.

Answer 1

Las colecciones de Java proporcionan LinkedHashMap fuera de la caja, que es muy adecuada para la construcción de cachés. Es probable que no tenga esto en Java ME, pero se puede agarrar el código fuente aquí:

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

Si usted no puede simplemente copiar y pegar, mirándolo servirán para iniciar la implementación de una para inclusión en su aplicación móvil. La idea básica es solo incluir una lista vinculada a través de los elementos del mapa. Si mantiene esta actualización cada vez que alguien ingresa u obtiene, puede realizar un seguimiento eficiente de la orden de acceso y el orden de uso.

Los documentos contienen instrucciones para construir una memoria caché MRU anulando el método .Todo lo que tienes que hacer es hacer una clase que se extiende LinkedHashMap y reemplazar el método de esta manera:

private static final int MAX_ENTRIES = 100; 

protected boolean removeEldestEntry(Map.Entry eldest) { 
    return size() > MAX_ENTRIES; 
} 

También hay un constructor que le permite especificar si desea que la clase para almacenar cosas en orden por inserción o por el uso , por lo que tiene un poco de flexibilidad para su política de desalojo, también:

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

Pass cierto para su uso-orden y falsa para la orden de inserción.

Answer 2

¿Por qué implementar algo ya implementado? Use Ehcache.

Sin embargo, si las bibliotecas de terceros están totalmente fuera de la cuestión, supongo que busca implementar una estructura de datos que se ve algo como esto:

• Básicamente es un HashMap (se extiende HashMap<Object, Object> si lo hará)
• Cada valor en el Mapa apunta a un objeto en una lista ordenada, en función de cuál es el más utilizado.
• objetos usados ​​recientemente se añaden a la cabeza de la lista - O(1)
• purga medio utilizado menos recientemente truncar el final de la lista - O(1)
• todavía da a trazar las búsquedas, pero aún mantiene los elementos usados ​​recientemente primero ...

Answer 3

Otro enfoque puede ser echar un vistazo a la sección 5.6 en Java Concurrency in Practice de Brian Goetz: "Creación de una memoria caché de resultados escalable y eficiente". Eche un vistazo al Memoizer, aunque es posible que deba personalizarlo para sus fines.

Como un aparte, lo que no puedo entender es por qué Java no tiene un ConcurrentLinkedHashMap fuera de la caja. Esta estructura de datos sería muy útil para construir un caché.

Answer 4

Un ConcurrentLinkedHashMap es difícil de construir, debido a los requisitos de bloqueo. Un LinkedHashMap con un bloqueo es sencillo, pero no siempre es efectivo. Una versión concurrente intentaría reducir la cantidad de bloqueo, ya sea mediante la división del bloqueo o idealmente haciendo operaciones CAS para hacer el bloqueo muy barato. Si las operaciones CAS alguna vez se vuelven costosas, entonces la división de cubos de manera similar puede ser útil. Como una LRU requiere escrituras para cada operación de acceso, y usa una lista doblemente vinculada, esto es muy difícil de implementar con operaciones CAS puras. Lo intenté, pero necesito continuar madurando mi algoritmo. Si busca ConcurrentLinkedHashMap, verá la página de mi proyecto ...

Si Java ME no es compatible con las operaciones CAS, lo que espero sea cierto, entonces la sincronización básica es todo lo que puede hacer. Esto es probablemente lo suficientemente bueno con un LHM, dado que solo he visto problemas de rendimiento en el alto conteo de subprocesos en el lado del servidor. Entonces +1 a las respuestas anteriores.