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