CKTIS / JavaScript
Algoritmy zásobníka, frontu a vyrovnávacej pamäte LRU
Porovnaj zásobník LIFO, front FIFO z dvoch zásobníkov a vyrovnávaciu pamäť LRU, ktorá pri prekročení kapacity vyradí najdlhšie nepoužitú položku.
Verzia: 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);Zásobník (LIFO) vráti najskôr naposledy pridanú položku. V poli push(value) pridáva na koniec a pop() z rovnakého konca položku odstráni a vráti. Pri prázdnom zásobníku vráti pop() undefined, rovnako ako pri odobratí uloženej hodnoty undefined.
Front (FIFO) vráti najskôr položku pridanú ako prvú. Dá sa použiť push() a shift(), ale shift() môže vyžadovať posunutie zvyšných položiek. Pri použití dvoch zásobníkov pridávaj do incoming. Pri odoberaní presuň všetko z incoming do outgoing len vtedy, keď je outgoing prázdny, a potom zavolaj outgoing.pop(). Presun obráti poradie. Ak operácie zásobníka majú amortizovanú zložitosť O(1), platí to aj pre operácie frontu, hoci presun k položiek stojí O(k). Prázdny front má rovnakú nejednoznačnosť s undefined.
Vyrovnávacia pamäť LRU po prekročení kapacity vyradí najdlhšie nepoužitú položku, nie nevyhnutne tú vloženú ako prvú. V tomto variante úspešné čítanie alebo zápis označí položku za naposledy použitú; neúspešné čítanie poradie nemení. Map sa prechádza v poradí vloženia: samotné set() existujúci kľúč neposunie, ale delete() nasledované set() ho presunie na koniec. Pri prekročení kapacity odstráň prvý kľúč. hit odlíši chýbajúcu položku od uloženého undefined.
ECMAScript vyžaduje pre Map priemerne sublineárny čas prístupu, ale nezaručuje O(1) pre každú operáciu LRU. Klasická alternatíva spája hašovaciu tabuľku s obojsmerne viazaným zoznamom: vyhľadanie má zvyčajne očakávanú zložitosť O(1) a presun či odpojenie známeho uzla stojí O(1). Limit počtu položiek neurčuje limit v bajtoch ani čas platnosti.
Prí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ýsledok
LIFO: B, A FIFO: A, B, C LRU: A, false, a,c
Zásobník vráti `B` pred `A`. Front vráti `A`, `B`, `C`, aj keď sa `C` pridá až po odobratí `A`. Čítanie označí `a` za naposledy použitú položku, takže zápis `c` vyradí `b` a ponechá `a,c`.
Súvisiace lekcie
- JavaScript · Lekcia 7 · Pokročilá · Verzia: 4