Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / JavaScript

Algorytmy stosu, kolejki i pamięci podręcznej LRU

Porównaj stos LIFO, kolejkę FIFO z dwóch stosów i pamięć podręczną LRU, która po przekroczeniu pojemności usuwa wpis używany najdawniej.

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

Składnia

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

Stos (LIFO) najpierw zwraca ostatnio dodany element. W tablicy push(value) dodaje na końcu, a pop() usuwa i zwraca element z tego samego końca. Pusty stos zwraca undefined, co nie odróżnia pustki od zapisanego undefined.

Kolejka (FIFO) najpierw zwraca najwcześniej dodany element. Można użyć push() i shift(), ale shift() może wymagać przesunięcia pozostałych elementów. W kolejce z dwóch stosów dodawaj do incoming. Przy pobieraniu przełóż wszystkie elementy z incoming do outgoing tylko wtedy, gdy outgoing jest pusty, a potem wykonaj outgoing.pop(). Przełożenie odwraca kolejność. Przy założeniu amortyzowanego kosztu O(1) operacji stosu koszt operacji kolejki wynosi amortyzowane O(1), choć pojedyncze przełożenie k elementów kosztuje O(k). Pusta kolejka ma tę samą niejednoznaczność undefined.

Pamięć podręczna LRU po przekroczeniu pojemności usuwa wpis używany najdawniej, niekoniecznie dodany najwcześniej. W tym wariancie udany odczyt i zapis odświeżają pozycję wpisu, a nieudany odczyt nie zmienia kolejności. Map iteruje według kolejności wstawiania: samo set() dla istniejącego klucza nie przesuwa go, ale delete() przed set() przenosi go na koniec. Przy nadmiarze usuń pierwszy klucz. Pole hit odróżnia brak wpisu od zapisanej wartości undefined.

ECMAScript wymaga średnio podliniowego czasu dostępu do Map, nie gwarantuje O(1) dla każdej operacji LRU. Klasyczna alternatywa łączy tablicę mieszającą z listą dwukierunkową: wyszukiwanie jest zwykle oczekiwane w O(1), a przeniesienie lub odpięcie znanego węzła kosztuje O(1). Limit wpisów nie oznacza limitu pamięci w bajtach ani wygasania po czasie.

Przykłady

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

Wynik

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

Stos zwraca `B` przed `A`. Kolejka zwraca `A`, `B`, `C`, mimo że `C` dodano po pobraniu `A`. Odczyt `a` odświeża jego pozycję, więc zapis `c` usuwa `b` i pozostawia klucze `a,c`.

Powiązane lekcje

  • JavaScript · Lekcja 7 · Zaawansowany · Wersja: 4

Źródła