Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / JavaScript

Algoritmi za sklad, čakalno vrsto in predpomnilnik LRU

Primerjaj sklad LIFO, čakalno vrsto FIFO iz dveh skladov in predpomnilnik LRU, ki ob prekoračitvi zmogljivosti izloči najdlje neuporabljeni vnos.

Različica: ECMAScript 2024 and the current web platform; runtime support varies

Sintaksa

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

Sklad (LIFO) najprej vrne nazadnje dodani element. V polju push(value) doda element na konec, pop() pa ga z istega konca odstrani in vrne. Na praznem skladu pop() vrne undefined, tako kot pri odstranitvi shranjene vrednosti undefined.

Čakalna vrsta (FIFO) najprej vrne prvi dodani element. Uporabiš lahko push() in shift(), vendar bo shift() morda moral premakniti preostale elemente. Pri dveh skladih dodajaj na incoming. Ob odvzemu prenesi vse elemente iz incoming v outgoing samo, če je outgoing prazen, nato pokliči outgoing.pop(). Prenos obrne vrstni red. Če imajo operacije sklada amortizirano časovno zahtevnost O(1), to velja tudi za operacije vrste, čeprav prenos k elementov zahteva O(k). Pri prazni vrsti je undefined enako dvoumen.

Predpomnilnik LRU ob prekoračitvi zmogljivosti izloči najdlje neuporabljeni vnos, ne nujno prvega vstavljenega. Tu uspešno branje ali pisanje označi vnos kot najnovejši po uporabi; neuspešno branje ne spremeni vrstnega reda. Map pregledujemo po vrstnem redu vstavljanja: samo set() obstoječega ključa ne premakne, delete() in nato set() pa ga prestavita na konec. Ob prekoračitvi odstrani prvi ključ. hit loči manjkajoči vnos od shranjene vrednosti undefined.

ECMAScript za Map zahteva v povprečju sublinearen dostopni čas, ne zagotavlja pa O(1) za vsako operacijo LRU. Klasična alternativa združuje razpršeno tabelo in dvojno povezani seznam: pričakovana zahtevnost iskanja je običajno O(1), premik ali odklop znanega vozlišča pa zahteva O(1). Omejitev števila vnosov ni omejitev v bajtih niti pravilo o poteku veljavnosti.

Primeri

{
  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(',')}`);
}

Rezultat

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

Sklad vrne `B` pred `A`. Čakalna vrsta vrne `A`, `B`, `C`, čeprav je `C` dodan šele po odstranitvi `A`. Z branjem postane `a` nazadnje uporabljeni vnos, zato zapis `c` izloči `b` in pusti `a,c`.

Povezane lekcije

  • JavaScript · Lekcija 7 · Napredna · Različica: 4

Viri