Плъзгащ прозорец
Накратко: Плъзгащият прозорец смята нещо за всеки последователен интервал, като на всяка стъпка добавя новия елемент и маха стария: O(n) вместо O(n · k).
Проблем
Оборотът за последните 365 дни
Таблото на магазина показва за всеки ден оборота за последните 365 дни. Историята е 10 години: 3650 дни. Кодът смята всеки прозорец наново: за всеки ден събира 365-те дни преди него.
adds = 0
def recompute(sales, k): global adds sums = [] for start in range(len(sales) - k + 1): total = 0 for d in range(start, start + k): adds += 1 total += sales[d] sums.append(total) return sumssales = [(d * 37) % 101 * 10 + 500 for d in range(3650)]sums = recompute(sales, 365)print(f"Прозорци: {len(sums)}")print(f"Събирания: {adds}")print(f"Най-добрите 365 дни: {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.
def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) return sumssales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850]sums = slide(sales, 7)for d, total in enumerate(sums): print(f"Дни {d + 1}–{d + 7}: {total} €")Дни 1–7: 5430 €Дни 2–8: 5500 €Дни 3–9: 5470 €Дни 4–10: 5540 €Дни 5–11: 5560 €Дни 6–12: 5830 €def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) 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.
total, не в sum: sum е вградена функция. Списъкът със сумите расте с append.Пробвай
Предвиди
Продажбите за пет дни и прозорец от 3 дни. Какво печата програмата?
def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) return sums
sales = [820, 640, 910, 700, 580]sums = slide(sales, 3)print(sums[-1])Първият прозорец е 820 + 640 + 910 = 2370. После +700 −820 = 2250, после +580 −640 = 2190. Последната сума е за дни 3–5: 910 + 700 + 580 = 2190.
Пробвай
Попълни
Ден i влиза в прозореца. Кой ден излиза?
def slide(sales, k):
total = 0
for i in range(k):
total += sales[i]
sums = [total]
for i in range(k, len(sales)):
total += sales[i]
total -= sales[]
sums.append(total)
return sumsПрозорецът, който свършва в ден i, е от i - k + 1 до i. Предишният е от i - k до i - 1. Разликата е денят i - k: той излиза.
Пробвай
Намери грешката
Първата сума е вярна, а след нея числата скачат нагоре и надолу:
sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850]sums = slide(sales, 7)for d, total in enumerate(sums): print(f"Дни {d + 1}–{d + 7}: {total} €")Дни 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 дни, а функцията брои събиранията и изважданията:
ops = 0
def slide(sales, k): global ops total = 0 for i in range(k): ops += 1 total += sales[i] sums = [total] for i in range(k, len(sales)): ops += 1 total += sales[i] ops += 1 total -= sales[i - k] sums.append(total) return sumssales = [(d * 37) % 101 * 10 + 500 for d in range(3650)]sums = slide(sales, 365)print(f"Прозорци: {len(sums)}")print(f"Операции: {ops}")print(f"Най-добрите 365 дни: {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 |
def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) return sumsДвете криви са успоредни: прозорецът е винаги 365 дни, затова и двете растат с n. Разликата е множителят. Наново струва k на ден, плъзгането струва 2 на ден, колкото и да е голям прозорецът. При прозорец от 30 дни плъзгането е 15 пъти по-бързо, при 365 дни около 180 пъти.
Идеята
Прозорец с променлива дължина
Маркетингът пита: кой е най-дългият период от поредни дни, в който разходът за реклама е общо до 400 €? Сега дължината на прозореца не е дадена. Тя е отговорът.
Прозорецът има два края, left и right:
rightвърви напред и добавя нов ден;- ако сумата мине бюджета,
leftвърви напред и маха дни отляво, докато сумата пак е до бюджета; - след това прозорецът е допустим, и дължината му е кандидат за най-дълга.
def longest_within(spend, budget): best = 0 total = 0 left = 0 for right in range(len(spend)): total += spend[right] while total > budget: total -= spend[left] left += 1 best = max(best, right - left + 1) return bestspend = [120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60]print(f"Най-дълъг период до 400 €: {longest_within(spend, 400)} дни")Най-дълъг период до 400 €: 5 дниВътре има цикъл в цикъла, но това е O(n), не O(n²). left никога не се връща назад: всеки ден влиза в прозореца веднъж и излиза най-много веднъж. Общо най-много 2n премествания.
Това работи, защото разходите не са отрицателни: по-дълъг прозорец никога не е по-евтин. Ако има връщания (отрицателни числа), махането на ден отляво може да увеличи сумата и правилото „свий, докато стане до бюджета“ вече не е вярно.
Виж го
Без повторен знак: прозорец с множество
Друг прозорец с променлива дължина: най-дългото парче от ред в лога, в което никой знак не се повтаря. Такива парчета издават случайни токени, които не бива да стоят в лога. Прозорецът пази знаците си в множество. Когато новият знак вече е вътре, left маха знаци отляво, докато повторението изчезне:
def longest_unique(line): seen = set() best_start = 0 best_len = 0 left = 0 for right, c in enumerate(line): while c in seen: seen.remove(line[left]) left += 1 seen.add(c) if right - left + 1 > best_len: best_len = right - left + 1 best_start = left return line[best_start:best_start + best_len]line = "GET /cart?token=x9Kq2Lm7Pz&page=2"part = longest_unique(line)print(f"Без повторен знак: {part} ({len(part)})")Без повторен знак: ?token=x9Kq2Lm7Pz&pag (21)Проверката „има ли го“ в множеството е O(1) средно, с hash таблица. Затова и тук общото е O(n).
for right, c in enumerate(line) дава и номера, и знака.По-точно, за любопитните
Какво е „знак“. В Java, C# и JavaScript низът е от 16-битови единици (UTF-16). Емоджи като 🛒 е две такива единици, и прозорецът ще ги брои поотделно. В Python низът е от code points, и 🛒 е един знак. Лог с латиница и цифри е еднакъв на четирите езика.
Сумата да не прелее. В Python целите числа нямат горна граница, сумата не прелива. В 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 минути колко различни клиенти има? Пази в речник колко поръчки има всеки клиент в прозореца.
Тест