Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / JavaScript

Algoritmi per pile, code e cache LRU

Confronta una pila LIFO, una coda FIFO costruita con due pile e una cache LRU che espelle la voce usata meno di recente quando supera la capacità.

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

Sintassi

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

Una pila (LIFO) restituisce per primo l’ultimo elemento aggiunto. In un array push(value) aggiunge in fondo, mentre pop() rimuove e restituisce un elemento dalla stessa estremità. Su una pila vuota pop() restituisce undefined, proprio come se rimuovesse un undefined memorizzato.

Una coda (FIFO) restituisce per primo l’elemento aggiunto per primo. Si possono usare push() e shift(), ma shift() può dover spostare gli elementi rimanenti. Con due pile, aggiungi gli elementi su incoming. Per prelevare un elemento, trasferisci tutti gli elementi da incoming a outgoing solo se outgoing è vuota, poi chiama outgoing.pop(). Il trasferimento inverte l’ordine. Se le operazioni della pila costano O(1) ammortizzato, anche quelle della coda costano O(1) ammortizzato, sebbene trasferire k elementi costi O(k). Una coda vuota presenta la stessa ambiguità con undefined.

Una cache LRU espelle la voce usata meno di recente, non necessariamente la prima inserita, quando supera la capacità. Qui una lettura riuscita o una scrittura rende la voce la più recente; una lettura senza riscontro non cambia l’ordine. Map si itera in ordine di inserimento: set() da solo non sposta una chiave esistente, ma delete() seguito da set() la porta in fondo. Se si supera la capacità, espelli la prima chiave. hit distingue una voce assente da un undefined memorizzato.

ECMAScript richiede un tempo di accesso mediamente sublineare per Map, ma non garantisce O(1) per ogni operazione LRU. Un’alternativa classica abbina una tabella hash a una lista doppiamente concatenata: la ricerca ha tipicamente un costo atteso di O(1), mentre spostare o scollegare un nodo noto costa O(1). Un limite al numero di voci non è né un limite in byte né una regola di scadenza.

Esempi

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

Risultato

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

La pila restituisce `B` prima di `A`. La coda restituisce `A`, `B`, `C`, anche se `C` viene aggiunto dopo il prelievo di `A`. Leggere `a` lo rende il più recente: scrivere `c` espelle quindi `b` e lascia `a,c`.

Lezioni correlate

  • JavaScript · Lezione 7 · Avanzato · Versione: 4

Fonti