LRU-Cache-Implementierung in Javascript

Question

Java hat LinkedHashMap die gets you 99% there to an LRU cache.

Gibt es eine JavaScript-Implementierung eines LRU-Cache, vorzugsweise aus einer seriösen Quelle, das heißt:

1. verständlich
2. effizient (amortisiert O (1) erhalten/put/Löschen)

? Ich habe im Internet gesucht, konnte aber keins finden. Ich dachte, ich fand einen auf Ajax Design Patterns, aber es glänzt über die sendToTail() Methode und hat O (n) Leistung (vermutlich, da die Warteschlange und assoziative Array aufgeteilt sind).

Ich glaube, ich könnte meine eigenen schreiben, aber ich habe auf die harte Weise gelernt, dass das Rad für Kern Algorithmen neu zu erfinden die Gesundheit zu einer gefährlich sein kann:/

Answer 1

Dieses:

https://github.com/monsur/jscache

scheint zu passen, obwohl setItem (dh Put) ist O (N) im schlimmsten Fall, das passiert, wenn der Cache beim Einfügen gefüllt ist. In diesem Fall wird der Cache durchsucht, um abgelaufene Elemente oder zuletzt verwendete Elemente zu löschen. getItem ist O (1) und der Ablauf wird auf der Operation getItem behandelt (d. H. Wenn das abgerufene Element abgelaufen ist, entfernt es es und gibt null zurück).

Der Code ist kompakt genug, um leicht verstanden zu werden.

P.S. Es könnte sinnvoll sein, dem Konstruktor die Option fillFactor hinzuzufügen, die auf 0,75 festgelegt ist (dh, wenn der Cache gelöscht wird, wird die Größe auf mindestens 3/4 der maximalen Größe reduziert)

Answer 2

Es ist nicht ein LRU-Cache, aber ich habe my own linked map implementation. Da es JS-Objekte als Speicher verwendet, hat es ähnliche Leistungsmerkmale (die Wrapper-Objekte und die Hash-Funktion verursachen eine Leistungseinbuße).

Derzeit ist die Dokumentation basically non-existant, aber es gibt eine related SO answer.

Die Methode each() übergibt den aktuellen Schlüssel, den aktuellen Wert und einen booleschen Wert, der angibt, ob mehr Elemente als Argumente für die Callback-Funktion vorhanden sind.

Alternativ kann Looping manuell über

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

Answer 3

erfolgen Die monsur.com Implementierung O (n) beim Einsetzen nur, weil es Elemente hat, die tatsächlich auf realen Welt Zeit abläuft. Es ist kein einfaches LRU. Wenn es Ihnen nur darum geht, die zuletzt verwendeten Objekte ohne Berücksichtigung der realen Zeit zu pflegen, kann dies in O (1) erfolgen. Eine Warteschlange, die als doppelt verkettete Liste implementiert ist, ist O (1) zum Einfügen oder Löschen vom Ende, und das ist alles was Sie für einen Cache benötigen sollten. Was das Nachschlagen angeht, sollte eine Hash-Map, die javascript pathetisch einfach macht, für fast O (1) Lookup gut sein (vorausgesetzt, die Javascript-Engine verwendet eine gute hashmap, das ist natürlich implementierungsabhängig). Sie haben also eine verknüpfte Liste von Elementen mit einer Hash-Map, die auf die Elemente zeigt. Manipulieren Sie die Enden der verknüpften Liste nach Bedarf, um neue Elemente und angeforderte Elemente an einem Ende einzufügen und alte Elemente vom anderen Ende zu entfernen.

Answer 4

Ich bin mir bewusst, dass dies eine alte Frage ist, aber einen Link für zukünftige Referenz hinzufügen. Auschecken https://github.com/monmohan/dsjslib. Dies hat eine LRU-Cache-Implementierung zusätzlich zu einigen anderen Datenstrukturen. Solche Caches (und auch diese) behalten eine doppelt verknüpfte Liste von Cache-Einträgen in LRU-Reihenfolge bei, d. H. Einträge bewegen sich beim Zugriff auf den Kopf und werden vom Ende entfernt, wenn sie zurückgewonnen werden (z. B. durch Ablauf oder weil das Größenlimit erreicht wurde). Es ist O (1), da es nur eine konstante Anzahl von Zeigermanipulationen beinhaltet.

Answer 5

Dies ist eine Erwähnung wert: https://github.com/rsms/js-lru

Der Kernsatz von Funktionen sind O (1) und der Code stark kommentiert wird

Answer 6

Dies, da Sie nicht so effizient ist (mit ASCII-Kunst auch!) wollen, aber es macht es in Einfachheit und Lesbarkeit aus. Und in vielen Fällen wird es schnell gehen.

Ich brauchte einen einfachen LRU-Cache für eine kleine Anzahl von teuren Operationen (1 Sekunde). Ich fühlte mich besser beim Kopieren-Einfügen etwas kleinen Code, anstatt etwas extern einzuführen, aber da ich es nicht gefunden habe, schrieb ich es:

Update: Dies ist jetzt viel effizienter (sowohl Platz und Zeit) seit Ich habe das Array entfernt, weil Map die Reihenfolge der Anzeigen beibehält.

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

Verbrauch:

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