Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / JavaScript

Algorithmes de pile, de file et de cache LRU

Comparez une pile LIFO, une file FIFO construite avec deux piles et un cache LRU qui évince l’entrée utilisée le moins récemment quand sa capacité est dépassée.

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

Une pile (LIFO) renvoie d’abord le dernier élément ajouté. Dans un tableau, push(value) ajoute en fin de tableau et pop() retire et renvoie un élément de cette même extrémité. Sur une pile vide, pop() renvoie undefined, comme si l’élément retiré était un undefined stocké.

Une file (FIFO) renvoie d’abord le premier élément ajouté. On peut utiliser push() et shift(), mais shift() peut imposer de décaler les éléments restants. Avec deux piles, ajoutez les éléments à incoming. Pour retirer un élément, transférez tout de incoming vers outgoing uniquement si outgoing est vide, puis appelez outgoing.pop(). Le transfert inverse l’ordre. Si les opérations de pile coûtent O(1) en temps amorti, celles de la file aussi, même si un transfert de k éléments coûte O(k). Une file vide présente la même ambiguïté avec undefined.

Un cache LRU évince l’entrée utilisée le moins récemment, pas forcément la première insérée, lorsque sa capacité est dépassée. Ici, une lecture réussie ou une écriture marque l’entrée comme la plus récente ; une lecture manquée ne change pas l’ordre. Map s’itère dans l’ordre d’insertion : set() seul ne déplace pas une clé existante, mais delete() suivi de set() la place en fin. En cas de dépassement, évincez la première clé. hit distingue une entrée absente d’un undefined stocké.

ECMAScript exige un temps d’accès sous-linéaire en moyenne pour Map, sans garantir O(1) pour chaque opération LRU. Une autre approche classique associe une table de hachage et une liste doublement chaînée : la recherche est généralement en O(1) en espérance, et déplacer ou détacher un nœud connu coûte O(1). Limiter le nombre d’entrées ne limite pas les octets ni la durée de vie des entrées.

Exemples

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

Résultat

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

La pile renvoie `B` avant `A`. La file renvoie `A`, `B`, `C`, même si `C` est ajouté après le retrait de `A`. La lecture de `a` le rend le plus récent : l’écriture de `c` évince donc `b` et laisse `a,c`.

Leçons associées

  • JavaScript · Leçon 7 · Avancé · Version : 4

Sources