Плъзгащ прозорец
Накратко: Плъзгащият прозорец смята нещо за всеки последователен интервал, като на всяка стъпка добавя новия елемент и маха стария: O(n) вместо O(n · k).
Проблем
Оборотът за последните 365 дни
Таблото на магазина показва за всеки ден оборота за последните 365 дни. Историята е 10 години: 3650 дни. Кодът смята всеки прозорец наново: за всеки ден събира 365-те дни преди него.
static long adds = 0;
static int[] Recompute(int[] sales, int k){ int[] sums = new int[sales.Length - k + 1]; for (int start = 0; start + k <= sales.Length; start++) { int sum = 0; for (int d = start; d < start + k; d++) { adds++; sum += sales[d]; } sums[start] = sum; } return sums;}int[] sales = new int[3650];for (int d = 0; d < sales.Length; d++){ sales[d] = (d * 37) % 101 * 10 + 500;}int[] sums = Recompute(sales, 365);Console.WriteLine("Прозорци: " + sums.Length);Console.WriteLine("Събирания: " + adds);Console.WriteLine($"Най-добрите 365 дни: {sums.Max()} €");Прозорци: 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.
static int[] Slide(int[] sales, int k){ int[] sums = new int[sales.Length - k + 1]; int sum = 0; for (int i = 0; i < k; i++) { sum += sales[i]; } sums[0] = sum; for (int i = k; i < sales.Length; i++) { sum += sales[i]; sum -= sales[i - k]; sums[i - k + 1] = sum; } return sums;}int[] sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];int[] sums = Slide(sales, 7);for (int d = 0; d < sums.Length; d++){ Console.WriteLine($"Дни {d + 1}–{d + 7}: {sums[d]} €");}Дни 1–7: 5430 €Дни 2–8: 5500 €Дни 3–9: 5470 €Дни 4–10: 5540 €Дни 5–11: 5560 €Дни 6–12: 5830 €static int[] Slide(int[] sales, int k){ int[] sums = new int[sales.Length - k + 1]; int sum = 0; for (int i = 0; i < k; i++) { sum += sales[i]; } sums[0] = sum; for (int i = k; i < sales.Length; i++) { sum += sales[i]; sum -= sales[i - k]; sums[i - k + 1] = 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.
sales.Length - k + 1: толкова са прозорците. Прозорецът, който свършва в ден i, е на място i - k + 1.Пробвай
Предвиди
Продажбите за пет дни и прозорец от 3 дни. Какво печата програмата?
static int[] Slide(int[] sales, int k){ int[] sums = new int[sales.Length - k + 1]; int sum = 0; for (int i = 0; i < k; i++) { sum += sales[i]; } sums[0] = sum; for (int i = k; i < sales.Length; i++) { sum += sales[i]; sum -= sales[i - k]; sums[i - k + 1] = sum; } return sums;}
int[] sales = [820, 640, 910, 700, 580];int[] sums = Slide(sales, 3);Console.WriteLine(sums[^1]);Първият прозорец е 820 + 640 + 910 = 2370. После +700 −820 = 2250, после +580 −640 = 2190. Последната сума е за дни 3–5: 910 + 700 + 580 = 2190.
Пробвай
Попълни
Ден i влиза в прозореца. Кой ден излиза?
static int[] Slide(int[] sales, int k)
{
int[] sums = new int[sales.Length - k + 1];
int sum = 0;
for (int i = 0; i < k; i++)
{
sum += sales[i];
}
sums[0] = sum;
for (int i = k; i < sales.Length; i++)
{
sum += sales[i];
sum -= sales[];
sums[i - k + 1] = sum;
}
return sums;
}Прозорецът, който свършва в ден i, е от i - k + 1 до i. Предишният е от i - k до i - 1. Разликата е денят i - k: той излиза.
Пробвай
Намери грешката
Първата сума е вярна, а след нея числата скачат нагоре и надолу:
int[] sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];int[] sums = Slide(sales, 7);for (int d = 0; d < sums.Length; d++){ Console.WriteLine($"Дни {d + 1}–{d + 7}: {sums[d]} €");}Дни 1–7: 5430 €Дни 2–8: 5560 €Дни 3–9: 5280 €Дни 4–10: 5650 €Дни 5–11: 5390 €Дни 6–12: 5520 €Избери реда с грешката.
Кодът изважда вчерашния ден, sales[i - 1], а не деня, който излиза от прозореца, sales[i - k]. Вчерашният ден още е в прозореца. Затова всяка сума е грешна, освен първата: за дни 2–8 излиза 5430 + 890 − 760 = 5560, а вярното е 5500.
Виж го
Измери: наново срещу плъзгане
Същите 10 години и прозорец от 365 дни, а функцията брои събиранията и изважданията:
static long ops = 0;
static int[] Slide(int[] sales, int k){ int[] sums = new int[sales.Length - k + 1]; int sum = 0; for (int i = 0; i < k; i++) { ops++; sum += sales[i]; } sums[0] = sum; for (int i = k; i < sales.Length; i++) { ops++; sum += sales[i]; ops++; sum -= sales[i - k]; sums[i - k + 1] = sum; } return sums;}int[] sales = new int[3650];for (int d = 0; d < sales.Length; d++){ sales[d] = (d * 37) % 101 * 10 + 500;}int[] sums = Slide(sales, 365);Console.WriteLine("Прозорци: " + sums.Length);Console.WriteLine("Операции: " + ops);Console.WriteLine($"Най-добрите 365 дни: {sums.Max()} €");Прозорци: 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 |
static int[] Slide(int[] sales, int k){ int[] sums = new int[sales.Length - k + 1]; int sum = 0; for (int i = 0; i < k; i++) { sum += sales[i]; } sums[0] = sum; for (int i = k; i < sales.Length; i++) { sum += sales[i]; sum -= sales[i - k]; sums[i - k + 1] = sum; } return sums;}Двете криви са успоредни: прозорецът е винаги 365 дни, затова и двете растат с n. Разликата е множителят. Наново струва k на ден, плъзгането струва 2 на ден, колкото и да е голям прозорецът. При прозорец от 30 дни плъзгането е 15 пъти по-бързо, при 365 дни около 180 пъти.
Идеята
Прозорец с променлива дължина
Маркетингът пита: кой е най-дългият период от поредни дни, в който разходът за реклама е общо до 400 €? Сега дължината на прозореца не е дадена. Тя е отговорът.
Прозорецът има два края, left и right:
rightвърви напред и добавя нов ден;- ако сумата мине бюджета,
leftвърви напред и маха дни отляво, докато сумата пак е до бюджета; - след това прозорецът е допустим, и дължината му е кандидат за най-дълга.
static int LongestWithin(int[] spend, int budget){ int best = 0; int sum = 0; int left = 0; for (int 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;}int[] spend = [120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60];Console.WriteLine("Най-дълъг период до 400 €: " + LongestWithin(spend, 400) + " дни");Най-дълъг период до 400 €: 5 дниВътре има цикъл в цикъла, но това е O(n), не O(n²). left никога не се връща назад: всеки ден влиза в прозореца веднъж и излиза най-много веднъж. Общо най-много 2n премествания.
Това работи, защото разходите не са отрицателни: по-дълъг прозорец никога не е по-евтин. Ако има връщания (отрицателни числа), махането на ден отляво може да увеличи сумата и правилото „свий, докато стане до бюджета“ вече не е вярно.
Виж го
Без повторен знак: прозорец с множество
Друг прозорец с променлива дължина: най-дългото парче от ред в лога, в което никой знак не се повтаря. Такива парчета издават случайни токени, които не бива да стоят в лога. Прозорецът пази знаците си в множество. Когато новият знак вече е вътре, left маха знаци отляво, докато повторението изчезне:
static string LongestUnique(string line){ var seen = new HashSet<char>(); int bestStart = 0; int bestLen = 0; int left = 0; for (int right = 0; right < line.Length; right++) { char c = line[right]; while (seen.Contains(c)) { seen.Remove(line[left]); left++; } seen.Add(c); if (right - left + 1 > bestLen) { bestLen = right - left + 1; bestStart = left; } } return line.Substring(bestStart, bestLen);}string line = "GET /cart?token=x9Kq2Lm7Pz&page=2";string part = LongestUnique(line);Console.WriteLine($"Без повторен знак: {part} ({part.Length})");Без повторен знак: ?token=x9Kq2Lm7Pz&pag (21)Проверката „има ли го“ в множеството е O(1) средно, с hash таблица. Затова и тук общото е O(n).
HashSet<char> пази самите char стойности, без обвиване.По-точно, за любопитните
Какво е „знак“. В Java, C# и JavaScript низът е от 16-битови единици (UTF-16). Емоджи като 🛒 е две такива единици, и прозорецът ще ги брои поотделно. В Python низът е от code points, и 🛒 е един знак. Лог с латиница и цифри е еднакъв на четирите езика.
Сумата да не прелее. int в C# стига до 2 147 483 647. Оборот за година в центове на голяма верига го минава: тогава сумата е long. Броячите в програмите горе са 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 минути колко различни клиенти има? Пази в речник колко поръчки има всеки клиент в прозореца.
Тест