Сложност по памет в JavaScript

Проблем

Износът, който изяжда паметта

Всяка нощ услуга изнася логовете на магазина за деня в архив. За да продължи след срив оттам, докъдето е стигнала, след всеки ред тя записва checkpoint. Само че checkpoint-ът е копие на целия файл досега:

function exportLogs(logs) {
  const file = [];
  const checkpoints = [];
  for (const line of logs) {
    file.push(line);
    checkpoints.push([...file]);
  }
  let places = 0;
  for (const saved of checkpoints) {
    places += saved.length;
  }
  return places;
}

Колко места държат копията? Програмата ги брои:

for (const n of [5, 1000]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`ред ${i}`);
  }
  console.log(`${n} реда: ${exportLogs(logs)} места`);
}

5 реда: 15 места
1000 реда: 500500 места

При 1000 реда са 500 500 места. Логовете за един ден са 100 000 реда, а това са 5 000 050 000 места. Всяко място пази референция от 4 до 8 байта: между 20 и 40 GB само за копията. На теста с 1000 реда всичко минава, а нощем износът спира с JavaScript heap out of memory.

Идеята

Паметта също е цена

Досега броеше операциите. Паметта се брои по същия начин: колко места заделя алгоритъмът сам, освен входа, който получава. Това е паметта на алгоритъма (на английски space complexity). И тя се казва с Big-O:

O(1): няколко променливи, колкото и да е голям входът;
O(n): копие на входа, помощен списък, set с всички елементи;
O(n²): копие на копието при всяка стъпка, като в износа.

Входът не се брои, защото го има и без алгоритъма. Не се брои и резултатът, който задачата иска: файлът с n реда е работата на износа. Броят се копията, които той прави по пътя.

Виж го

Копията остават

const file = [];
let checkpoint = 0;
for (const line of logs) {
  file.push(line);
  checkpoint = file.length;
}

Стъпка по стъпка, с думи

file е файлът, който износът пише, а logs има 4 реда. checkpoints пази откъде да продължи след срив.
Ред 1 отива във файла. Checkpoint-ът е копие на целия файл: 1 място.
Ред 2. Новият checkpoint копира двата реда, а старият остава в списъка: 1 + 2 = 3 места.
След 4 реда паметта държи 1 + 2 + 3 + 4 = 10 места. След n реда са n(n + 1)/2: пет милиарда при 100 000 реда.
За да продължиш след срив, ти трябва само докъде си стигнал. Копията изчезват, остава едно число.
Всеки ред сменя числото: checkpoint = 4. Допълнителната памет е 1 място, колкото и да са редовете.

Всяко копие е нов списък в паметта, а старите никой не изтрива: списъкът checkpoints ги пази. Затова местата растат като 1 + 2 + 3 + … + n. За да продължи след срив, на износа му трябва само докъде е стигнал:

function exportLogs(logs) {
  const file = [];
  let checkpoint = 0;
  for (const line of logs) {
    file.push(line);
    checkpoint = file.length;
  }
  return checkpoint;
}

for (const n of [5, 1000]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`ред ${i}`);
  }
  console.log(`${n} реда, checkpoint: ${exportLogs(logs)}`);
}

5 реда, checkpoint: 5
1000 реда, checkpoint: 1000

Файлът е същият, а допълнителната памет е едно число: O(1) вместо O(n²).

Пробвай

Предвиди изхода

Износът с копията получава 6 реда. Колко места държат checkpoint-ите?

function exportLogs(logs) {
  const file = [];
  const checkpoints = [];
  for (const line of logs) {
    file.push(line);
    checkpoints.push([...file]);
  }
  let places = 0;
  for (const saved of checkpoints) {
    places += saved.length;
  }
  return places;
}

for (const n of [6]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`ред ${i}`);
  }
  console.log(`${n} реда: ${exportLogs(logs)} места`);
}

Отговор

6 реда: 21 места

6 реда: 6 места

6 реда: 36 места

Виж го

Копие или на място

Администраторът иска най-новите логове първи. Има два начина. Единият прави нов списък в обратен ред, а другият разменя елементите в самия списък: първия с последния, втория с предпоследния, докато двата края се срещнат.

function newestFirst(logs) {
  const result = [];
  for (let i = logs.length - 1; i >= 0; i--) {
    result.push(logs[i]);
  }
  return result;
}

function reverseInPlace(logs) {
  let left = 0;
  let right = logs.length - 1;
  while (left < right) {
    [logs[left], logs[right]] = [logs[right], logs[left]];
    left++;
    right--;
  }
}

const logs = ["09:00 вход", "09:05 количка", "09:07 плащане"];
const newest = newestFirst(logs);
console.log("Копие:    " + newest.join(", "));
console.log("Оригинал: " + logs.join(", "));
reverseInPlace(logs);
console.log("На място: " + logs.join(", "));

Копие:    09:07 плащане, 09:05 количка, 09:00 вход
Оригинал: 09:00 вход, 09:05 количка, 09:07 плащане
На място: 09:07 плащане, 09:05 количка, 09:00 вход

Копието иска n нови места, но оригиналът остава непокътнат. Промяната на място (in place) иска едно място за размяната, но старият ред го няма. Кое е по-добре, зависи от това дали някой друг още чете оригинала.

По-точно, за любопитните

Вградените функции правят същия избор, и името не винаги го казва:

const logs = ["09:00 вход", "09:05 количка", "09:07 плащане"];
const copy = logs.toReversed();
logs.reverse();
console.log("На място: " + logs.join(", "));
console.log("Копие:    " + copy.join(", "));

На място: 09:07 плащане, 09:05 количка, 09:00 вход
Копие:    09:07 плащане, 09:05 количка, 09:00 вход

reverse() обръща на място, а toReversed() (от 2023 г., Node 20) прави копие. slice() и [...logs] също копират: в рекурсия logs.slice(1) копира почти целия масив при всяко извикване.

Копието е плитко: новият списък пази референции към същите текстове, а не нови текстове. Затова местата се броят по едно на елемент.

Пробвай

Попълни

Довърши размяната на двата края:

[logs[left], logs[right]] = [logs[right], ];

Виж го

Рекурсията също държи памет

Списък не е единственото, което заема място. Всяко извикване на функция пази своите параметри и локални променливи в стека от извиквания, докато не върне. Ето броене на грешките в лога с рекурсия и с цикъл:

function errorsFrom(logs, i) {
  if (i === logs.length) {
    return 0;
  }
  const here = logs[i].startsWith("ERROR") ? 1 : 0;
  return here + errorsFrom(logs, i + 1);
}

function errors(logs) {
  let count = 0;
  for (const line of logs) {
    if (line.startsWith("ERROR")) {
      count++;
    }
  }
  return count;
}

const small = makeLogs(500);
const big = makeLogs(1_000_000);
console.log(`500 реда: ${errorsFrom(small, 0)} грешки`);
try {
  console.log(`1000000 реда: ${errorsFrom(big, 0)} грешки`);
} catch (e) {
  console.log(`1000000 реда: ${e.name}`);
}
console.log(`С цикъл: ${errors(big)} грешки`);

500 реда: 5 грешки
1000000 реда: RangeError
С цикъл: 10000 грешки

Рекурсията не прави нито един списък, но при n реда в стека стоят n незавършени извиквания: O(n) памет. Стекът е малък, и милион извиквания не се събират. Цикълът има една променлива count: O(1).

По-точно, за любопитните

Колко дълбоко може да стигне рекурсията, зависи от размера на стека и от големината на една рамка. В Node стекът е около 1 MB, а това са няколко хиляди до десетки хиляди извиквания според рамката. RangeError е името на грешката.

Когато рекурсивното извикване е последното действие на функцията (без here + след него), някои езици го превръщат в цикъл (tail call). Java, C#, Python и Node не го правят, затова в тях дълбочината винаги струва памет.

Идеята

Време срещу памет

Магазинът проверява дали две поръчки от деня имат един и същ номер. Първият начин сравнява всяка двойка. Вторият помни видените номера в set:

function hasDuplicateLoops(orders) {
  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      if (orders[i] === orders[j]) {
        return true;
      }
    }
  }
  return false;
}

function hasDuplicateSet(orders) {
  const seen = new Set();
  for (const order of orders) {
    if (seen.has(order)) {
      return true;
    }
    seen.add(order);
  }
  return false;
}

const today = [100512, 100513, 100514, 100512];
console.log(hasDuplicateLoops(today), hasDuplicateSet(today));

true true

Двата дават един отговор, но плащат различно:

вложените цикли: O(1) памет и O(n²) време;
set-ът: O(n) памет (до n номера) и O(n) време.

Това е честа размяна: памет срещу време. Колко сравнения и проверки правят двата, когато повторение няма (най-лошият случай):

function comparisonsLoops(orders) {
  let count = 0;
  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      count++;
      if (orders[i] === orders[j]) {
        return count;
      }
    }
  }
  return count;
}

function checksSet(orders) {
  const seen = new Set();
  let count = 0;
  for (const order of orders) {
    count++;
    if (seen.has(order)) {
      return count;
    }
    seen.add(order);
  }
  return count;
}

for (const n of [10, 1000]) {
  const orders = [];
  for (let i = 0; i < n; i++) {
    orders.push(100000 + i);
  }
  console.log(`${n} поръчки: ${comparisonsLoops(orders)} сравнения с цикли, ${checksSet(orders)} проверки със set`);
}

10 поръчки: 45 сравнения с цикли, 10 проверки със set
1000 поръчки: 499500 сравнения с цикли, 1000 проверки със set

Вложени цикли, без памет O(n²)
Set с видените номера, n места O(n)

Алгоритъм	n = 10	n = 1000	n = 100 000
Вложени цикли, без памет	45	499 500	≈ 4 995 000 000
Set с видените номера, n места	10	1000	100 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

При 100 000 поръчки циклите правят почти 5 милиарда сравнения, а set-ът 100 000 проверки и пази 100 000 номера. Когато паметта я има, set-ът печели. Когато я няма (малко устройство, огромен вход), или подреждаш номерата (тогава повторените са един до друг), или четеш на части.

По-точно, за любопитните

Една проверка в set-а броим за една операция. Тя е O(1) средно, защото set-ът е hash таблица: номерът става число, а числото казва в коя кофа да гледа. Едно място в set-а струва повече от едно число в масив: в Set около 20–40 байта според двигателя. Затова „O(n) памет“ при 10 милиона поръчки са стотици MB, не 40.

Пробвай

Намери грешката

Колегата е пренаписал проверката със set, но тя никога не намира повторение:

function hasDuplicateSet(orders) {
  for (const order of orders) {
    const seen = new Set();
    if (seen.has(order)) {
      return true;
    }
    seen.add(order);
  }
  return false;
}

const today = [100512, 100513, 100514, 100512];
console.log(hasDuplicateSet(today));

false

Номер 100512 е два пъти, а отговорът е „не“. На кой ред е грешката?

Избери реда с грешката.

Упражнение

Последните три реда

Реши задачата в редактора си.

Последните редове. Когато нещо се счупи, админът иска само последните k реда от лога. Напиши lastLines(logs, k), която ги връща, като държи в паметта най-много k реда, а не целия лог: O(k) памет. Пусни я с 1000 реда („ред 1“ … „ред 1000“) и k = 3.

ред 998
ред 999
ред 1000

Едно възможно решение

Пази опашка: всеки нов ред влиза отзад, а когато редовете станат повече от k, най-старият излиза отпред.

function lastLines(logs, k) {
  const recent = [];
  for (const line of logs) {
    recent.push(line);
    if (recent.length > k) {
      recent.shift();
    }
  }
  return recent;
}

shift() мести всички елементи с едно наляво, но те са най-много k, затова една стъпка е O(k).

Още задачи

Средната дължина без копие. Сметни средната дължина на ред в лога с O(1) допълнителна памет: без нов списък с дължините.
Грешките по час. Преброй грешките за всеки час (09, 10…). Колко памет иска твоето решение, ако часовете са 24, а редовете милион?
Повторените номера. Върни не само „има или няма“, а всички повторени номера. Колко памет иска решението със set, и може ли без него?

Тест

Провери се

1. Функция прави нов списък с n лога в обратен ред. Колко допълнителна памет иска?O(1)O(n)O(n²)

2. Износът пази след всеки ред копие на целия файл досега. Колко места държи паметта при n реда?n2nn(n + 1)/2, тоест O(n²)

3. Рекурсивна функция без нито един списък се вика 1 000 000 пъти една в друга. Колко памет иска?O(n): всяко извикване стои в стека, докато не върнеНикаква, паметта е само за обектиO(1), защото няма списъци

4. Търсиш повторен номер в 10 000 000 поръчки на сървър с няколко GB свободна памет. Кое избираш?Вложените цикли, защото не искат паметSet-а: O(n) памет, но O(n) време вместо O(n²)Все едно е

5. Кое не се брои в допълнителната памет на функцията?Стекът на рекурсията ѝВходът, който функцията получаваКопието на входа, което функцията прави

Сложност по памет

Бисквитки