KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / JavaScript

Algoritmen voor stacks, wachtrijen en LRU-caches

Vergelijk een LIFO-stack, een FIFO-wachtrij met twee stacks en een LRU-cache die bij overschrijding van de capaciteit het langst ongebruikte item verwijdert.

Versie: ECMAScript 2024 and the current web platform; runtime support varies

Syntax

Stack: stack.push(value); stack.pop();
Two-stack queue: incoming.push(value); if (outgoing.length === 0) { while (incoming.length > 0) outgoing.push(incoming.pop()); } outgoing.pop();
Map-backed LRU refresh: cache.delete(key); cache.set(key, value);
Map-backed LRU eviction: if (cache.size > capacity) cache.delete(cache.keys().next().value);

Een stack (LIFO) geeft het laatst toegevoegde item als eerste terug. Op een array voegt push(value) achteraan toe en verwijdert pop() aan diezelfde kant een item om het terug te geven. Op een lege stack geeft pop() undefined terug, net als bij het verwijderen van een opgeslagen undefined.

Een wachtrij (FIFO) geeft het eerst toegevoegde item als eerste terug. Dat kan met push() en shift(), maar shift() moet mogelijk de resterende items verschuiven. Gebruik je twee stacks, voeg dan toe aan incoming. Verplaats bij het uithalen alle items van incoming naar outgoing als outgoing leeg is, en roep daarna outgoing.pop() aan. De overdracht keert de volgorde om. Als stackbewerkingen geamortiseerd O(1) kosten, geldt dat ook voor wachtrijbewerkingen, al kost een overdracht van k items O(k). Een lege wachtrij geeft dezelfde dubbelzinnigheid met undefined.

Een LRU-cache verwijdert bij capaciteitsoverschrijding het item dat het langst niet is gebruikt, niet noodzakelijk het eerst ingevoegde item. Hier maakt een geslaagde leesactie of een schrijfactie een item het meest recent; een misser verandert de volgorde niet. Map itereert op invoegvolgorde: set() alleen verplaatst een bestaande sleutel niet, maar delete() gevolgd door set() zet deze achteraan. Verwijder bij overschrijding de eerste sleutel. hit onderscheidt een misser van een opgeslagen undefined.

ECMAScript vereist voor Map gemiddeld sublineaire toegangstijd, maar garandeert geen O(1) voor elke LRU-bewerking. Een klassiek alternatief combineert een hashtabel met een dubbelgekoppelde lijst: opzoeken kost doorgaans naar verwachting O(1), en een bekend knooppunt verplaatsen of loskoppelen kost O(1). Een maximumaantal items is geen limiet in bytes en stelt geen vervaltijd in.

Voorbeelden

{
  const stack = [];
  stack.push('A', 'B');
  console.log(`LIFO: ${stack.pop()}, ${stack.pop()}`);

  const incoming = [];
  const outgoing = [];
  const enqueue = value => incoming.push(value);
  function dequeue() {
    if (outgoing.length === 0) {
      while (incoming.length > 0) outgoing.push(incoming.pop());
    }
    return outgoing.pop();
  }
  enqueue('A');
  enqueue('B');
  const first = dequeue();
  enqueue('C');
  console.log(`FIFO: ${first}, ${dequeue()}, ${dequeue()}`);

  const cache = new Map();
  const capacity = 2;
  function put(key, value) {
    cache.delete(key);
    cache.set(key, value);
    if (cache.size > capacity) cache.delete(cache.keys().next().value);
  }
  function read(key) {
    if (!cache.has(key)) return { hit: false };
    const value = cache.get(key);
    put(key, value);
    return { hit: true, value };
  }
  put('a', 'A');
  put('b', 'B');
  const recent = read('a');
  put('c', 'C');
  console.log(`LRU: ${recent.value}, ${read('b').hit}, ${[...cache.keys()].join(',')}`);
}

Resultaat

LIFO: B, A
FIFO: A, B, C
LRU: A, false, a,c

De stack geeft `B` vóór `A` terug. De wachtrij geeft `A`, `B`, `C` terug, ook al wordt `C` pas toegevoegd nadat `A` is verwijderd. Lezen maakt `a` het meest recente item, dus schrijven van `c` verwijdert `b` en laat `a,c` over.

Gerelateerde lessen

  • JavaScript · Les 7 · Gevorderd · Versie: 4

Bronnen