Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / JavaScript

Algoritmi za stog, red i predmemoriju LRU

Usporedi stog LIFO, red FIFO izgrađen od dvaju stogova i predmemoriju LRU koja pri prekoračenju kapaciteta izbacuje najdavnije korišteni zapis.

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

Stog (LIFO) prvo vraća posljednji dodani element. U polju push(value) dodaje na kraj, a pop() s istog kraja uklanja i vraća element. Ako je stog prazan, pop() vraća undefined, baš kao pri uklanjanju pohranjene vrijednosti undefined.

Red (FIFO) prvo vraća najranije dodani element. Možeš koristiti push() i shift(), no shift() može zahtijevati pomicanje preostalih elemenata. U izvedbi s dva stoga dodaj na incoming. Pri uzimanju elementa prebaci sve iz incoming u outgoing samo ako je outgoing prazan, pa pozovi outgoing.pop(). Prebacivanje obrće redoslijed. Ako operacije stoga imaju amortizirani trošak O(1), vrijedi isto za operacije reda, iako prebacivanje k elemenata stoji O(k). Prazan red ima istu dvosmislenost s vrijednošću undefined.

Predmemorija LRU pri prekoračenju kapaciteta izbacuje najdavnije korišteni zapis, ne nužno onaj prvi umetnut. Ovdje uspješno čitanje ili upis čini zapis najnovije korištenim, a neuspjelo čitanje ne mijenja poredak. Map se obilazi redoslijedom umetanja: samo set() ne pomiče postojeći ključ, no delete() pa set() premješta ga na kraj. Pri prekoračenju kapaciteta izbaci prvi ključ. hit razlikuje nepostojeći zapis od pohranjenog undefined.

ECMAScript za Map zahtijeva prosječno sublinearno vrijeme pristupa, ali ne jamči O(1) za svaku operaciju LRU. Klasična alternativa spaja raspršenu tablicu s dvostruko povezanim popisom: pretraživanje obično ima očekivani trošak O(1), a premještanje ili odvajanje poznatog čvora stoji O(1). Ograničenje broja zapisa nije ni ograničenje u bajtovima ni pravilo o isteku.

Primjeri

{
  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

Stog vraća `B` prije `A`. Red vraća `A`, `B`, `C`, iako se `C` dodaje tek nakon uklanjanja `A`. Čitanje stavke `a` čini je posljednjom korištenom, pa upis `c` izbacuje `b` i ostavlja `a,c`.

Povezane lekcije

  • JavaScript · Lekcija 7 · Napredno · Verzija: 4

Izvori