LRU-Cache-Implementierung mit Javascript

Einführung

LRU steht für „Least Recent Used“. Ein LRU-Cache ist eine Art Cache, bei dem die zuletzt verwendeten Einträge entfernt werden, wenn der Cache seine Kapazität erreicht.

• Der Hauptgrund für die Verwendung eines LRU-Cache besteht darin, die Leistung beim Datenzugriff zu verbessern. Der Zugriff auf Daten aus einem Cache ist in der Regel schneller als das Abrufen aus dem Hauptspeicher oder einem Remote-Server.
• Durch die Speicherung der zuletzt verwendeten Daten im Cache erhöht sich die Wahrscheinlichkeit eines Cache-Treffers, was wiederum die Geschwindigkeit des Datenabrufs verbessert.

Zu Ihrer Information:

• Eine Kartendatenstruktur wird verwendet, um das Verhalten einer Hash-Tabelle nachzuahmen. Dies ermöglicht effiziente Such-, Einfüge- und Löschvorgänge.
• Eine doppelt verknüpfte Liste ist implementiert, um eine einfache Bewegung zwischen Elementen zu ermöglichen. Dies bietet die Möglichkeit, sich in beide Richtungen (vorwärts und rückwärts) zu bewegen und zeitkonstante Einfügungen und Löschungen durchzuführen.
• Die Kombination dieser beiden Datenstrukturen ermöglicht effiziente Vorgänge und nutzt die Vorteile von Hash-Tabellen und doppelt verknüpften Listen.

Hier ist ein einfaches Beispiel dafür, wie ein LRU-Cache in JavaScript implementiert werden könnte:

// Why we need this LRU
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

//Least Recently used
class LRU {
    constructor() {
     this.head = this.tail = null;
     this.map = new Map();
     this.size = 0; // Why I added size, because may be in future we can say if capacity reach to the size, we will remove the tail first and then insert.
    }

    get(key) {
        if (this.map.has(key)) {
            const node = this.map.get(key);

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        }

        return -1;
    }

    update(key, value) {
        if (this.map.has(key)) {
            let node = this.map.get(key);
            node.value = value;

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        } else {
            console.log('Key not found'); 
            // Here we can check for capacity if available we can call insert
            // if capacity is not available we will remove the tail and then insert.
        }
    }

    remove(node) {
        if (node === this.tail) {
            this.tail = this.tail.prev;
        }

        const prevNode = node.prev;
        const nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    insert(key, value) {
        const newNode = new Node(key, value);
        this.map.set(key, newNode);
        if (this.head === null) {
            this.head = this.tail = newNode;
            this.size = 1;
            return;
        }
        // We need to insert at the Begining
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head= newNode;
        this.size++;
        return;
    }
}

const test = new LRU();
test.insert('A', 20);
test.insert('B', 10);
test.insert('C', 5);
test.insert('D', 7);

console.log(test);
console.log('------------------');
console.log('C ---> ', test.get('C'));
console.log('D ---> ', test.get('D'));

console.log('D ---> ', test.update('B', 100));

/*
LRU {
  tail: <ref *1> Node {
    key: 'A',
    value: 20,
    next: null,
    prev: Node { key: 'B', value: 10, next: [Circular *1], prev: [Node] }
  },
  head: <ref *2> Node {
    key: 'D',
    value: 7,
    next: Node { key: 'C', value: 5, next: [Node], prev: [Circular *2] },
    prev: null
  },
  map: Map(4) {
    'A' => <ref *1> Node {
      key: 'A',
      value: 20,
      next: null,
      prev: [Node]
    },
    'B' => Node { key: 'B', value: 10, next: [Node], prev: [Node] },
    'C' => Node { key: 'C', value: 5, next: [Node], prev: [Node] },
    'D' => <ref *2> Node {
      key: 'D',
      value: 7,
      next: [Node],
      prev: null
    }
  },
  size: 4
}
------------------
C --->  5
D --->  7
D --->  100
B --->  100
*/

Wenn Sie Bedenken haben, können Sie sich gerne an mich wenden.

Das obige ist der detaillierte Inhalt vonLRU-Cache-Implementierung mit Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!