WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / JavaScript

Algorithmen für Stapel, Warteschlangen und LRU-Caches

Vergleiche einen LIFO-Stapel, eine FIFO-Warteschlange aus zwei Stapeln und einen LRU-Cache, der bei Überfüllung den am längsten nicht verwendeten Eintrag verdrängt.

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

Ein Stapel (LIFO) liefert das zuletzt hinzugefügte Element zuerst. Bei einem Array hängt push(value) ein Element an. pop() entfernt am selben Ende ein Element und gibt es zurück. Bei leerem Stapel liefert pop() undefined, genau wie bei einem gespeicherten undefined.

Eine Warteschlange (FIFO) liefert das zuerst hinzugefügte Element zuerst. push() und shift() funktionieren, aber shift() kann die übrigen Elemente verschieben müssen. Bei zwei Stapeln kommen neue Elemente auf incoming. Nur wenn outgoing leer ist, überträgst du vor dem Entnehmen alle Elemente von incoming nach outgoing. Anschließend rufst du outgoing.pop() auf. Die Übertragung kehrt die Reihenfolge um. Bei amortisiert O(1) pro Stapeloperation kosten Warteschlangenoperationen amortisiert O(1), obwohl eine Übertragung von k Elementen O(k) kostet. Bei leerer Warteschlange ist undefined ebenso mehrdeutig.

Ein LRU-Cache verdrängt bei Überschreiten der Kapazität den am längsten nicht verwendeten Eintrag, nicht unbedingt den zuerst eingefügten. Hier aktualisieren ein Treffer und ein Schreibzugriff die Nutzungsreihenfolge; ein Fehltreffer ändert nichts. Map iteriert in Einfügereihenfolge: set() allein verschiebt einen vorhandenen Schlüssel nicht, delete() gefolgt von set() setzt ihn ans Ende. Bei Überfüllung wird der erste Schlüssel entfernt. hit unterscheidet einen Fehltreffer von gespeichertem undefined.

ECMAScript verlangt für Map im Mittel sublineare Zugriffszeit, garantiert aber nicht O(1) für jede LRU-Operation. Eine klassische Alternative kombiniert eine Hashtabelle mit einer doppelt verketteten Liste: Die Suche kostet typischerweise erwartet O(1), das Verschieben oder Aushängen eines bekannten Knotens O(1). Ein Eintragslimit ist weder ein Byte-Limit noch eine Regel zum zeitlichen Ablauf.

Beispiele

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

Ergebnis

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

Der Stapel liefert `B` vor `A`. Die Warteschlange liefert `A`, `B`, `C`, obwohl `C` erst nach der Entnahme von `A` hinzukommt. Das Lesen von `a` macht es zum zuletzt verwendeten Eintrag. Deshalb verdrängt das Schreiben von `c` den Schlüssel `b`, und `a,c` bleiben übrig.

Zugehörige Lektionen

  • JavaScript · Lektion 7 · Fortgeschritten · Version: 4

Quellen