Implementazione della cache LRU in Javascript

Question

Java ha LinkedHashMap che gets you 99% there to an LRU cache.

c'è un'implementazione di JavaScript una cache LRU, preferibilmente da una fonte affidabile, vale a dire:

1. comprensibile
2. efficiente (O ammortizzato (1) get/put/delete)

? Ho cercato sul web ma non sono riuscito a trovarne uno; Ho pensato di averne trovato uno su Ajax Design Patterns, ma si glissa sul metodo sendToTail() e ha prestazioni O (n) (presumibilmente, dal momento che la coda e l'array associativo sono suddivisi).

Suppongo che potrei scrivere il mio, ma ho imparato nel modo più duro che reinventare la ruota per gli algoritmi di base può essere pericoloso per la salute:/

Answer 1

questo:

https://github.com/monsur/jscache

sembra adattarsi al tuo caso sebbene setItem (cioè put) sia O (N) nel peggiore dei casi, ciò accade se la cache viene riempita al momento dell'inserimento. In questo caso, la ricerca della cache viene effettuata per eliminare gli elementi scaduti o gli elementi utilizzati meno di recente. getItem è O (1) e la scadenza viene gestita sull'operazione getItem (ad esempio se l'elemento da recuperare è scaduto, lo rimuove e restituisce null).

Il codice è sufficientemente compatto per essere facilmente compreso.

P.S. Potrebbe essere utile aggiungere al costruttore l'opzione per specificare il fillFactor, che è fissato a 0,75 (significa che quando la cache viene eliminata la sua dimensione viene ridotta almeno a 3/4 della dimensione massima)

Answer 2

Non è una cache LRU, ma ho my own linked map implementation. Poiché utilizza oggetti JS come archivio, avrà caratteristiche di prestazioni simili (gli oggetti wrapper e la funzione hash impartiscono una penalizzazione delle prestazioni).

Attualmente la documentazione è basically non-existant, ma c'è un related SO answer.

Il metodo each() passerà la chiave corrente, il valore corrente e un valore booleano che indica se ci sono più elementi come argomenti per la funzione di callback.

alternativa, loop può essere fatto manualmente tramite

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

Answer 3

L'attuazione monsur.com è O (n) all'inserimento solo perché ha articoli che effettivamente scadono il tempo reale. Non è una semplice LRU. Se ti interessa solo mantenere gli oggetti usati più di recente senza riguardo al tempo reale, questo può essere fatto in O (1). Una coda, implementata come lista doppiamente collegata, è O (1) per l'inserimento o la cancellazione dalla fine, e questo è tutto ciò che serve per una cache. Per quanto riguarda la ricerca, una mappa hash, che javascript rende pateticamente facile, dovrebbe essere utile per quasi la ricerca O (1) (supponendo che il motore javascript usi una buona hashmap, ovviamente dipende dall'implementazione). Quindi hai un elenco collegato di elementi con una mappa hash che punta agli oggetti. Manipolare le estremità dell'elenco collegato come necessario per inserire nuovi elementi e elementi richiesti su un'estremità e rimuovere vecchi elementi dall'altra estremità.

Answer 4

Sono consapevole che questa è una vecchia domanda, ma aggiungendo un collegamento per il futuro refrence. Check out https://github.com/monmohan/dsjslib. Questo ha un'implementazione di LRU Cache oltre ad altre strutture di dati. Tali cache (e anche questa) mantengono l'elenco doppiamente collegato delle voci della cache nell'ordine LRU, in cui le voci si spostano in testa non appena sono accessibili e vengono rimosse dalla coda quando vengono recuperate (ad esempio per scadenza o perché è stato raggiunto il limite di dimensioni). La sua O (1) poiché coinvolge solo un numero costante di manipolazioni del puntatore.

Answer 5

Questo merita una menzione: https://github.com/rsms/js-lru

Il nucleo di funzioni sono O (1) e il codice è pesantemente commentato

Answer 6

Questo non è così efficiente come si (con l'arte ASCII troppo!) voglio, ma compensa in semplicità e leggibilità. E per molti casi sarà molto veloce.

Avevo bisogno di una cache LRU semplice per un piccolo numero di operazioni costose (1 secondo). Mi sentivo meglio con copia-incollare qualche piccolo codice, piuttosto che l'introduzione di qualcosa di esterno, ma dal momento che non ho trovato che ho scritto:

Aggiornamento: Questo è ora molto più efficiente (spazio e nel tempo) dal Ho rimosso l'array, perché la mappa mantiene l'ordine di inserimento.

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

Usage:

> 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"