CKTIS / JavaScript
Zbirke: sklad, vrsta in algoritem LRU
Sklad obdeluje elemente po načelu LIFO, vrsta po načelu FIFO, predpomnilnik LRU pa odstrani najdlje neuporabljen vnos. V JavaScriptu jih lahko sestavimo z Array in Map, vendar moramo zavestno obravnavati vrstni red, stroške operacij in manjkajoče vrednosti.
Različica: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Sintaksa
stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().valueSklad, vrsta in LRU so pravila za upravljanje zbirk, ne imena vgrajenih konstruktorjev. Sklad deluje po načelu LIFO: zadnji dodani element se odstrani prvi. Za preprost sklad zadošča polje z push() in pop(). Vrsta deluje po načelu FIFO: prvi dodani element se odstrani prvi; preprosta različica uporablja push() in shift().
shift() lahko zahteva premikanje indeksiranih lastnosti, zato ne predpostavljajte, da je odstranjevanje z začetka konstantno drago. Pri veliki vrsti razmislite o krožnem medpomnilniku ali začetnem indeksu z občasnim zgoščevanjem; sprostite sklice na porabljene objekte. pop() in shift() pri praznem polju vrneta undefined, zato prazne zbirke ni mogoče razlikovati od zbirke, ki vsebuje vrednost undefined.
LRU (least recently used) ob preseženi kapaciteti odstrani najdlje neuporabljen vnos. Map ohranja vrstni red vstavljanja, vendar niti get() niti set() za obstoječi ključ ne osveži njegovega položaja. Ob uspešnem branju in pri pisanju vnos izbrišite ter znova vstavite; prvi ključ iz keys() je nato kandidat za odstranitev. Primer ima fiksno kapaciteto 2; parametrizirana različica bi morala preveriti, ali je kapaciteta pozitivno celo število.
V primeru has() razlikuje manjkajoči ključ od vnosa z vrednostjo undefined, čeprav javni get() v obeh primerih vrne undefined. Specifikacija za Map zahteva povprečen podlinearen dostop, ne zagotavlja pa O(1). Koda uporablja sintakso in funkcije, ki so na voljo v ECMAScript 2015, ter ne potrebuje brskalniških spletnih API-jev. Izvedba v Node ne dokazuje združljivosti s ciljnim brskalnikom.
Primeri
const stack = [];
stack.push('a', 'b');
console.log(stack.pop());
const queue = [];
queue.push('a', 'b');
console.log(queue.shift());
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 get(key) {
if (!cache.has(key)) return undefined;
const value = cache.get(key);
cache.delete(key);
cache.set(key, value);
return value;
}
put('a', 1);
put('b', 2);
console.log(get('a'));
put('c', 3);
console.log(cache.has('b'));
console.log([...cache.keys()].join(','));Rezultat
b a 1 false a,c
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.