База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / JavaScript

Алгоритми за стек, опашка и LRU кеш

Сравни стек LIFO, опашка FIFO с два стека и LRU кеш, който при надвишаване на капацитета премахва записа, използван най-отдавна.

Версия: ECMAScript 2024 and the current web platform; runtime support varies

Синтаксис

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

Стекът (LIFO) връща първо последно добавения елемент. При масив push(value) добавя в края, а pop() премахва и връща елемент от същия край. При празен стек pop() връща undefined, както и при премахване на съхранен undefined.

Опашката (FIFO) връща първо най-рано добавения елемент. Може да използваш push() и shift(), но shift() може да наложи преместване на останалите елементи. При реализация с два стека добавяй в incoming. При извличане прехвърли всички елементи от incoming в outgoing само ако outgoing е празен, след което извикай outgoing.pop(). Прехвърлянето обръща реда. Ако операциите на стека имат амортизирана сложност O(1), това важи и за операциите на опашката, макар едно прехвърляне на k елемента да струва O(k). При празна опашка undefined има същата двусмисленост.

LRU кешът премахва най-отдавна използвания запис при надвишаване на капацитета, а не непременно първия добавен. Тук успешно четене или запис отбелязва записа като най-скоро използван; неуспешното четене не променя реда. Map се обхожда в реда на добавяне: само set() не мести съществуващ ключ, но delete(), последвано от set(), го премества в края. При надвишаване на капацитета премахни първия ключ. hit различава липсващ запис от съхранен undefined.

ECMAScript изисква средно подлинейно време за достъп до Map, но не гарантира O(1) за всяка операция на LRU кеша. Класическа алтернатива съчетава хеш таблица и двойно свързан списък: търсенето обикновено има очаквана сложност O(1), а преместването или откачането на известен възел струва O(1). Ограничението на броя записи не е ограничение в байтове и не задава срок на валидност.

Примери

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

Резултат

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

Стекът връща `B` преди `A`. Опашката връща `A`, `B`, `C`, въпреки че `C` е добавен след изваждането на `A`. Четенето прави `a` най-скоро използвания запис, затова записването на `c` премахва `b` и оставя `a,c`.

Свързани уроци

  • JavaScript · Урок 7 · Напреднало · Версия: 4

Източници