Плъзгащ прозорец в JavaScript

Проблем

Оборотът за последните 365 дни

Таблото на магазина показва за всеки ден оборота за последните 365 дни. Историята е 10 години: 3650 дни. Кодът смята всеки прозорец наново: за всеки ден събира 365-те дни преди него.

let adds = 0;

function recompute(sales, k) {
  const sums = [];
  for (let start = 0; start + k <= sales.length; start++) {
    let sum = 0;
    for (let d = start; d < start + k; d++) {
      adds++;
      sum += sales[d];
    }
    sums.push(sum);
  }
  return sums;
}

const sales = Array.from({ length: 3650 }, (_, d) => (d * 37) % 101 * 10 + 500);
const sums = recompute(sales, 365);
console.log(`Прозорци: ${sums.length}`);
console.log(`Събирания: ${adds}`);
console.log(`Най-добрите 365 дни: ${Math.max(...sums)} €`);

Прозорци: 3286
Събирания: 1199390
Най-добрите 365 дни: 366050 €

3286 прозореца по 365 събирания: 1 199 390. Това е n·k: при 1000 продукта с по една графика стават 1,2 милиарда събирания всяка нощ.

А два съседни прозореца се различават само по два дни. Останалите 364 се събират отново и отново.

Идеята

Плъзни прозореца: +нов ден, −стар ден

Сумата за дни 2–8 е сумата за дни 1–7, плюс ден 8, минус ден 1. Ден 8 влиза в прозореца, ден 1 излиза. Дните между тях не се пипат.

Затова:

първият прозорец се събира веднъж: k събирания;
всеки следващ е предишният + новият ден − най-старият: две операции, колкото и да е голям прозорецът.

Това се казва плъзгащ прозорец (sliding window): прозорец с фиксирана дължина, който се мести с един елемент, а резултатът за него се обновява от предишния. Вместо (n − k + 1) · k операции стават k + 2(n − k). Това е O(n), а не O(n·k).

Прозорецът е два указателя в една посока, като в предния урок: началото и краят му. Тук разстоянието между тях е винаги k.

Виж го

Седмицата се плъзга

Продажбите за 12 дни и сумата за всеки 7 последователни дни. Средното за седмицата е сумата, разделена на 7.

function slide(sales, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) {
    sum += sales[i];
  }
  const sums = [sum];
  for (let i = k; i < sales.length; i++) {
    sum += sales[i];
    sum -= sales[i - k];
    sums.push(sum);
  }
  return sums;
}

const sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];
const sums = slide(sales, 7);
sums.forEach((sum, d) => {
  console.log(`Дни ${d + 1}–${d + 7}: ${sum} €`);
});

Дни 1–7: 5430 €
Дни 2–8: 5500 €
Дни 3–9: 5470 €
Дни 4–10: 5540 €
Дни 5–11: 5560 €
Дни 6–12: 5830 €

function slide(sales, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) {
    sum += sales[i];
  }
  const sums = [sum];
  for (let i = k; i < sales.length; i++) {
    sum += sales[i];
    sum -= sales[i - k];
    sums.push(sum);
  }
  return sums;
}

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

Първият прозорец: дни 1–7. Седемте дни се събират един по един: 7 събирания, 5430 €.
Ден 8 влиза: +890 €. Ден 1 излиза: −820 €. Дни 2–8: 5500 €, с две операции вместо 7.
Ден 9 влиза: +610 €. Ден 2 излиза: −640 €. Дни 3–9: 5470 €, с две операции вместо 7.
Ден 10 влиза: +980 €. Ден 3 излиза: −910 €. Дни 4–10: 5540 €, с две операции вместо 7.
Ден 11 влиза: +720 €. Ден 4 излиза: −700 €. Дни 5–11: 5560 €, с две операции вместо 7.
Ден 12 влиза: +850 €. Ден 5 излиза: −580 €. Дни 6–12: 5830 €, с две операции вместо 7.
6 прозореца за 17 операции: 7 за първия и по 2 за всеки следващ. Наново всеки път биха били 6 · 7 = 42.

Списъкът със сумите расте с push, а forEach дава и сумата, и номера ѝ.

Пробвай

Предвиди

Продажбите за пет дни и прозорец от 3 дни. Какво печата програмата?

function slide(sales, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) {
    sum += sales[i];
  }
  const sums = [sum];
  for (let i = k; i < sales.length; i++) {
    sum += sales[i];
    sum -= sales[i - k];
    sums.push(sum);
  }
  return sums;
}

const sales = [820, 640, 910, 700, 580];
const sums = slide(sales, 3);
console.log(sums.at(-1));

Отговор

Пробвай

Попълни

Ден i влиза в прозореца. Кой ден излиза?

function slide(sales, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) {
    sum += sales[i];
  }
  const sums = [sum];
  for (let i = k; i < sales.length; i++) {
    sum += sales[i];
    sum -= sales[];
    sums.push(sum);
  }
  return sums;
}

Пробвай

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

Първата сума е вярна, а след нея числата скачат нагоре и надолу:

const sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];
const sums = slide(sales, 7);
sums.forEach((sum, d) => {
  console.log(`Дни ${d + 1}–${d + 7}: ${sum} €`);
});

Дни 1–7: 5430 €
Дни 2–8: 5560 €
Дни 3–9: 5280 €
Дни 4–10: 5650 €
Дни 5–11: 5390 €
Дни 6–12: 5520 €

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

Виж го

Измери: наново срещу плъзгане

Същите 10 години и прозорец от 365 дни, а функцията брои събиранията и изважданията:

let ops = 0;

function slide(sales, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) {
    ops++;
    sum += sales[i];
  }
  const sums = [sum];
  for (let i = k; i < sales.length; i++) {
    ops++;
    sum += sales[i];
    ops++;
    sum -= sales[i - k];
    sums.push(sum);
  }
  return sums;
}

const sales = Array.from({ length: 3650 }, (_, d) => (d * 37) % 101 * 10 + 500);
const sums = slide(sales, 365);
console.log(`Прозорци: ${sums.length}`);
console.log(`Операции: ${ops}`);
console.log(`Най-добрите 365 дни: ${Math.max(...sums)} €`);

Прозорци: 3286
Операции: 6935
Най-добрите 365 дни: 366050 €

6935 операции вместо 1 199 390, и най-добрите 365 дни са същите. Пусни двата начина в браузъра:

Всеки прозорец наново (K = 365) O(n)
Плъзгане: +нов −стар O(n)

Алгоритъм	n = 1000	n = 3650	n = 10 000	n = 100 000
Всеки прозорец наново (K = 365)	232 140	1 199 390	3 517 140	36 367 140
Плъзгане: +нов −стар	1635	6935	19 635	199 635

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

function slide(sales, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) {
    sum += sales[i];
  }
  const sums = [sum];
  for (let i = k; i < sales.length; i++) {
    sum += sales[i];
    sum -= sales[i - k];
    sums.push(sum);
  }
  return sums;
}

Двете криви са успоредни: прозорецът е винаги 365 дни, затова и двете растат с n. Разликата е множителят. Наново струва k на ден, плъзгането струва 2 на ден, колкото и да е голям прозорецът. При прозорец от 30 дни плъзгането е 15 пъти по-бързо, при 365 дни около 180 пъти.

Идеята

Прозорец с променлива дължина

Маркетингът пита: кой е най-дългият период от поредни дни, в който разходът за реклама е общо до 400 €? Сега дължината на прозореца не е дадена. Тя е отговорът.

Прозорецът има два края, left и right:

right върви напред и добавя нов ден;
ако сумата мине бюджета, left върви напред и маха дни отляво, докато сумата пак е до бюджета;
след това прозорецът е допустим, и дължината му е кандидат за най-дълга.

function longestWithin(spend, budget) {
  let best = 0;
  let sum = 0;
  let left = 0;
  for (let right = 0; right < spend.length; right++) {
    sum += spend[right];
    while (sum > budget) {
      sum -= spend[left];
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

const spend = [120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60];
console.log(`Най-дълъг период до 400 €: ${longestWithin(spend, 400)} дни`);

Най-дълъг период до 400 €: 5 дни

Вътре има цикъл в цикъла, но това е O(n), не O(n²). left никога не се връща назад: всеки ден влиза в прозореца веднъж и излиза най-много веднъж. Общо най-много 2n премествания.

Това работи, защото разходите не са отрицателни: по-дълъг прозорец никога не е по-евтин. Ако има връщания (отрицателни числа), махането на ден отляво може да увеличи сумата и правилото „свий, докато стане до бюджета“ вече не е вярно.

Виж го

Без повторен знак: прозорец с множество

Друг прозорец с променлива дължина: най-дългото парче от ред в лога, в което никой знак не се повтаря. Такива парчета издават случайни токени, които не бива да стоят в лога. Прозорецът пази знаците си в множество. Когато новият знак вече е вътре, left маха знаци отляво, докато повторението изчезне:

function longestUnique(line) {
  const seen = new Set();
  let bestStart = 0;
  let bestLen = 0;
  let left = 0;
  for (let right = 0; right < line.length; right++) {
    const c = line[right];
    while (seen.has(c)) {
      seen.delete(line[left]);
      left++;
    }
    seen.add(c);
    if (right - left + 1 > bestLen) {
      bestLen = right - left + 1;
      bestStart = left;
    }
  }
  return line.slice(bestStart, bestStart + bestLen);
}

const line = "GET /cart?token=x9Kq2Lm7Pz&page=2";
const part = longestUnique(line);
console.log(`Без повторен знак: ${part} (${part.length})`);

Без повторен знак: ?token=x9Kq2Lm7Pz&pag (21)

Проверката „има ли го“ в множеството е O(1) средно, с hash таблица. Затова и тук общото е O(n).

line[right] е един знак от UTF-16 текста. За текст с емоджи това е половин знак: вж. „По-точно“.

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

Какво е „знак“. В Java, C# и JavaScript низът е от 16-битови единици (UTF-16). Емоджи като 🛒 е две такива единици, и прозорецът ще ги брои поотделно. В Python низът е от code points, и 🛒 е един знак. Лог с латиница и цифри е еднакъв на четирите езика.

Сумата да не прелее. В JavaScript числата са точни до 2⁵³, сумата в центове не прелива. В Java и C# int стига до 2 147 483 647 и за оборот в центове трябва long.

Сумата да не се разкриви. Ако продажбите са в евро с центове в double, всяко +нов −стар добавя мъничка грешка от закръгляне, а грешките се трупат: след хиляди стъпки сумата на прозореца вече не е точно сумата на дните му. Пази парите в центове, като цели числа. Ако числата са с плаваща запетая по природа (температури, времена), сметни прозореца наново на всеки няколко хиляди стъпки.

Средното и най-голямото. Плъзгащото се средно е сумата, разделена на k. Най-голямата стойност в прозореца не става с +нов −стар: максимумът не може да се „извади“. За нея има плъзгащ прозорец с опашка от двата края (deque), която пази кандидатите за максимум.

Упражнение

Най-краткият период с оборот поне 3500 €

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

Най-кратък период. Продажбите за 12 дни са 820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720 и 850 €. Кой е най-краткият период от поредни дни с оборот поне 3500 €? Прозорецът расте надясно, а докато сумата е поне 3500 €, запомни дължината, ако е по-малка, и го свивай отляво.

Най-кратък период с поне 3500 €: 5 дни (от ден 1 до ден 5)

Още задачи

Най-добрата седмица. С плъзгането намери кои 7 поредни дни имат най-голям оборот и ги отпечатай.
Плъзгащо се средно. Отпечатай средните продажби за всеки 7 дни, закръглени до цент.
Различни клиенти за час. Поръчките са подредени по минута, всяка с номер на клиент. За всеки прозорец от 60 минути колко различни клиенти има? Пази в речник колко поръчки има всеки клиент в прозореца.

Тест

Провери се

1. Сумата за дни 1–7 е 5430 €. Ден 8 е 890 €, ден 1 е 820 €. Колко е сумата за дни 2–8?6320 €4610 €5500 €

2. n = 3650 дни, прозорец k = 365. Колко операции прави плъзгането?365 + 2 · 3285 = 69353286 · 365 = 1 199 3903650 · 365

3. В прозореца с бюджет лявата граница left никога не се връща назад. Колко пъти най-много се мести общо?n · k пътиn² пътиn пъти: всеки ден излиза от прозореца най-много веднъж

4. В разходите има и връщания: отрицателни числа. Работи ли още прозорецът „най-дълъг период до бюджета“?Да, ако бюджетът е отрицателенНе: махането на ден отляво вече може да увеличи сумата, затова „свий отляво, докато стане до бюджета“ не е вярноДа, без промяна

5. Сумите на прозореца са в евро с центове, в double. Защо е по-добре да пазиш центове в цяло число?Цяло число заема повече паметВсяко +нов −стар добавя мъничка грешка от закръгляне, а след хиляди стъпки тя се виждаdouble е по-бавен

Плъзгащ прозорец

Бисквитки