Implementación de caché LRU en Javascript

algorithm caching

Question

Java tiene LinkedHashMap que lo lleva 99% a un LRU caché .

¿Hay una implementación de JavaScript de un caché de LRU, preferiblemente de una fuente acreditada, que es:

1. comprensible
2. eficiente (O (1) amortizado get / put / delete)

? He estado buscando en la web pero no he podido encontrar uno; Pensé que había encontrado uno en Ajax Design Patterns pero pasa por alto el método sendToTail() y tiene un rendimiento O (n) (presumiblemente, dado que la cola y el conjunto asociativo están divididos).

Supongo que podría escribir la mía, pero he aprendido de la peor manera que reinventar la rueda para los algoritmos básicos puede ser peligroso para la salud:

Answer 1

La implementación de monsur.com es O (n) en la inserción solo porque tiene elementos que realmente caducan en el tiempo real. No es un LRU simple. Si solo te preocupa mantener los artículos usados ​​más recientemente sin importar el tiempo real del mundo, esto se puede hacer en O (1). Una cola, implementada como una lista doblemente enlazada, es O (1) para inserción o eliminación desde el final, y esto es todo lo que necesita para un caché. En cuanto a la búsqueda, un hash map, que javascript hace patéticamente fácil, debería ser bueno para casi O (1) búsqueda (suponiendo que el motor de javascript utiliza un buen hashmap, eso depende de la implementación, por supuesto). Por lo tanto, tiene una lista vinculada de elementos con un mapa hash que apunta a los elementos. Manipule los extremos de la lista vinculada según sea necesario para colocar nuevos elementos y elementos solicitados en un extremo y eliminar elementos antiguos del otro extremo.

Answer 2

Esta:

https://github.com/monsur/jscache

parece ajustarse a su caso, aunque setItem (es decir, put) es O (N) en el peor de los casos, eso sucede si la memoria caché se llena en la inserción. En este caso, se busca la caché para purgar los elementos caducados o los elementos utilizados menos recientemente. getItem es O (1) y el vencimiento se maneja en la operación getItem (es decir, si el elemento que se está buscando está vencido, lo elimina y devuelve nulo).

El código es lo suficientemente compacto para que se entienda fácilmente.

PD: Puede ser útil agregar al constructor la opción para especificar el fillFactor , que se fija en 0,75 (lo que significa que cuando se purga el caché, su tamaño se reduce al menos a fillFactor del tamaño máximo)

Answer 3

Soy consciente de que esta es una pregunta antigua pero agrego un enlace para futuras referencias. Consulte https://github.com/monmohan/dsjslib . Esto tiene una implementación LRU Cache además de algunas otras estructuras de datos. Dichas cachés (y esta también) mantienen una lista doblemente enlazada de entradas de caché en orden LRU, es decir, las entradas se mueven a la cabeza a medida que se acceden y se eliminan de la cola cuando se recuperan (por ejemplo por vencimiento o porque se alcanzó el límite de tamaño). Es O (1) ya que solo involucra un número constante de manipulaciones de puntero.

Answer 4

Vale la pena mencionar esto: https://github.com/rsms/js-lru

El conjunto principal de funciones es O (1) y el código está fuertemente comentado (¡con arte ASCII también!)

Answer 5

No es un caché LRU, pero tengo mi propia implementación de mapa vinculado . Como utiliza un objeto JS como almacén, tendrá características de rendimiento similares (los objetos de envoltura y la función hash imparten una penalización de rendimiento).

Actualmente, la documentación es básicamente inexistente , pero hay una respuesta SO relacionada .

El método each() pasará la clave actual, el valor actual y un booleano que indica si hay más elementos como argumentos para la función de devolución de llamada.

Alternativamente, el bucle se puede hacer manualmente a través de

for(var i = map.size; i--; map.next()) {
    var currentKey = map.key();
    var currentValue = map.value();
}

Answer 6

Esto no es tan eficiente como usted desea, pero lo compensa con simplicidad y legibilidad. Y para muchos casos, será bastante rápido.

Necesitaba un simple caché LRU para un pequeño número de operaciones costosas (1 segundo). Me sentí mejor al copiar y pegar un código pequeño en lugar de introducir algo externo, pero como no lo encontré lo escribí:

Actualización : ahora es mucho más eficiente (espacio y tiempo) desde que eliminé la matriz, porque Map mantiene el orden de inserción.

class LRU {
    constructor(max=10) {
        this.max = max;
        this.cache = new Map();
    }
    get(key) {
        let item = this.cache.get(key);
        if (item) // refresh key
        {
            this.cache.delete(key);
            this.cache.set(key, item);
        }
        return item;
    }
    set(key, val) {
        if (this.cache.has(key)) // refresh key
            this.cache.delete(key);
        else if (this.cache.size == this.max) // evict oldest
            this.cache.delete(this._first());
        this.cache.set(key, val);
    }
    _first(){
        return this.cache.keys().next().value;
    }
}

Uso:

> let cache = new LRU(3)
> [1, 2, 3, 4, 5].forEach(v => cache.set(v, ''v:''+v))
> cache.get(2)
undefined
> cache.get(3)
"v:3"
> cache.set(6, 6)
> cache.get(4)
undefined
> cache.get(3)
"v:3"