Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / JavaScript

Algoritmy zásobníku, fronty a mezipaměti LRU

Porovnej zásobník LIFO, frontu FIFO ze dvou zásobníků a mezipaměť LRU, která po překročení kapacity vyřadí nejdéle nepoužitou položku.

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

Syntaxe

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

Zásobník (LIFO) vrací nejdřív naposledy přidanou položku. U pole push(value) přidává na konec a pop() ze stejného konce položku odebere a vrátí. U prázdného zásobníku vrátí pop() undefined, stejně jako při odebrání uložené hodnoty undefined.

Fronta (FIFO) vrací nejdřív položku přidanou jako první. Lze použít push() a shift(), ale shift() může vyžadovat posun zbývajících položek. U fronty ze dvou zásobníků přidávej na incoming. Při odebírání přesuň vše z incoming do outgoing pouze tehdy, když je outgoing prázdný, a pak zavolej outgoing.pop(). Přesun obrátí pořadí. Pokud mají zásobníkové operace amortizovanou složitost O(1), platí to i pro operace fronty, ačkoli přesun k položek stojí O(k). U prázdné fronty je undefined stejně nejednoznačné.

Mezipaměť LRU při překročení kapacity vyřadí nejdéle nepoužitou položku, nikoli nutně tu vloženou jako první. V tomto provedení úspěšné čtení nebo zápis označí položku za nejnověji použitou; neúspěšné čtení pořadí nemění. Map se prochází v pořadí vložení: samotné set() stávající klíč neposune, ale delete() následované set() ho přesune na konec. Při překročení kapacity odeber první klíč. hit odlišuje chybějící položku od uloženého undefined.

ECMAScript vyžaduje pro Map v průměru sublineární dobu přístupu, ale nezaručuje O(1) pro každou operaci LRU. Klasická alternativa spojuje hašovací tabulku s obousměrně vázaným seznamem: vyhledání obvykle trvá očekávaných O(1) a přesun či odpojení známého uzlu O(1). Limit počtu položek není ani limitem v bajtech, ani nastavením doby platnosti.

Příklady

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

Výsledek

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

Zásobník vrátí `B` před `A`. Fronta vrátí `A`, `B`, `C`, i když se `C` přidá až po odebrání `A`. Čtení označí `a` za nejnověji použitou položku, takže zápis `c` vyřadí `b` a ponechá `a,c`.

Související lekce

  • JavaScript · Lekce 7 · Pokročilá · Verze: 4

Zdroje