Зсувне Вікно Мінімального Значення через Монотонну Очікувану Чергу

Як працює монотонна черга

Основна ідея полягає в утриманні черги індексів (а не просто значень) з потоку даних, яка підтримується в порядку, де відповідні значення зростають від переднього кінця до заднього. Коли надходить новий елемент, виконується послідовність двох операцій. По-перше, алгоритм переглядає задній кінець черги та повторно видаляє елементи, значення яких більші або рівні новому елементу. Цей крок є серцем техніки: якщо новий елемент менший за щось, що вже зберігається, старіший, більший елемент більше ніколи не буде повідомлятися як мінімум вікна, поки новий елемент залишається всередині вікна, оскільки новий елемент також менший і більш свіжий, тому він все ще буде дійсним після того, як старий буде виведений. Просто немає сценарію, в якому видалений елемент був би корисним, тому його видалення безпечне. По-друге, індекс нового елемента записується на задній кінець черги. На цьому етапі черга знову повністю монотонна: зростає від переднього кінця до заднього. Третє, перш ніж читати мінімум, алгоритм перевіряє передній кінець черги. Якщо індекс, що зберігається там, випав за межі поточного вікна (його положення більше на K кроків позаду найновішого елемента), він видаляється з переднього кінця, оскільки він більше не є частиною вікна, хоча його значення все ще може бути малим. Після цих кроків значення на передньому індексі гарантовано є мінімумом поточного вікна. Воно вижило в усіх порівняннях із меншими новими прибульцями і ще не вийшло за межі діапазону, тому ніщо інше в черзі не може його перемогти.

Чому це амортизований постійний час

На перший погляд, вихід з задньої частини "while" умова виконується може здаватися, що він працює протягом тривалого часу на одному кроці, роблячи алгоритм таким, що іноді коштує O(K) роботи. Уві скрученій формі петля, зовнішній цикл по потоку та внутрішній цикл по вилученнях, здається, загрожують постійному гарантованому часу. Рішення полягає в амортизованому аналізі, який вивчає загальну вартість усього набору операцій, а не найгірший випадок будь-якої окремої операції. Ключовим моментом є те, що кожен індекс відсувається з черги рівно один раз, коли він вперше приходить із потоку. З цього моменту вперед індекс може бути видалений лише двічі протягом свого всього життя: один раз з задньої частини, якщо пізніше менший елемент викликає його вилучення, або один раз спереду, якщо він виходить із вікна, але ніколи не обидва, оскільки після того, як він був вилучений, він зник. У всьому потоці n елементів є щонайбільше n відсувків і щонайбільше n вилучень у загальному, незалежно від того, як розподіляються вилучення на окремих кроках. Деякі кроки можуть бачити кілька вилучень назад поспіль, що здається дорогим, але ці вилучення «оплачуються» відсувками, які відбулися раніше та ще не були зараховані до будь-якого вилучення. Підсумовуючи загальну роботу, відсувки плюс вилучення, у всьому потоці, це щонайбільше 2n операцій, тому середній вартість кожного елемента потоку становить O(1), незважаючи на те, що вартість будь-якого окремого кроку може змінюватися. Це суть амортизованого O(1) на крок: не те, що кожен окремий крок дешевий, а те, що загальна вартість, поділена на кількість кроків, обмежена сталою.

Максимум замість Мініма

Однакова техніка безперешкодно переходить для відстеження максимума вікна замість мінімума. Єдину зміну потрібно зробити – напрямок порівняння: замість видалення елементів, які більші або рівні новоприбулому, алгоритм видаляє елементи, менші або рівні йому, підтримуючи чергу монотонно спадною від початку до кінця. Логіка є симетричною: старіший, менший елемент ніколи не може стати максимумом після того, як приєднано більший, новіший елемент у вікно, тому його безпечно викинути. Все інше залишається незмінним. Індекси все ще додаються в кінець після видалення домінованих записів, передній елемент обрізається, коли він випадає за межі вікна, і передній елемент черги все ще дає відповідь за постійний час. Деякі реалізації навіть відстежують одночасно міні-чергу та макси-чергу, що корисно для обчислення діапазону (максимум мінус мінімум) кожного вікна, що є поширеною вимогою в обробці сигналів та виявленні аномалій. Варто зазначити, що черга не зберігає кожне значення у вікні, лише підпослідовність значень, які могли б потенційно стати відповіддю в майбутньому. У найгіршому випадку (строго монотонний потік) черга може містити до K записів, але в найкращому випадку, наприклад, коли потік постійно зменшується, вона може містити лише один запис. Це адаптивна розмірність є причиною того, що ця техніка перевершує наївний повний ресерч, який завжди оглядає всі K елементи незалежно від їх відношення.

Порівняння з альтернативними підходами

Перш ніж монотонний де́к стала стандартним інструментом, задачі про мінімальне вікно вирішувалися менш ефективними структурами. Наївний сканування перераховує мінімум по всіх K елементах кожного разу, коли змінюється вікно, що дає загальний час O(n·K), який стає дуже повільним для великих вікон або довгих потоків даних. Збалансоване бінарне дерево пошуку або куча з ледачою видаленими записами також можуть відстежувати мінімум вікна, підтримуючи вставки та видалення за O(log K) часу кожне. Це правильно і досить швидко, і це узагальнюється до проблем, де потрібно знайти k-те найменше значення замість просто мінімального, але це несе логарифмічний фактор і більший постійний накладний витрат, а також складність обробки застарілих записів, які вийшли з вікна. Монотонний де́к досягає того ж результату лише з амортизованим O(1) на елемент та значно простішою реалізацією: один масив або зв’язаний список, що використовуються як подвійні кінцеві черги, без порівнянь за межами простих перевірок «більше ніж» або «менше ніж». Його обмеження полягає в тому, що він відповідає лише на запит про мінімум або максимум, а не на запити про будь-який ранг, отже, якщо задача потребує медіану або k-те найменше значення у вікні, дерево чи структура на основі кучі залишаються необхідними. Однак для конкретної та дуже поширеної задачі відстеження поточного мінімума або максимума, монотонний де́к є найшвидшим і найпростішим інструментом, який доступний, що пояснює його широке використання в інтерв’ю з програмістами та у виробничих потокових системах.

Практичне застосування

Зсувне вікно мінімального значення та максимального значення проявляється в багатьох сферах, які обробляють безперервні або великі послідовні дані. У аналізі цін на фондовій біржі трейдери та алгоритми часто потребують найнижчої або найвищої ціни за проміжок часу, наприклад, за останні 30 торгових днів, щоб обчислювати індикатори, такі як канали Дончіана, або виявляти прориви; перерахунок цього з нуля при кожному новому тику був би набагато повільнішим для високочастотних даних, але монотонний де́к (deque) оновлює його миттєво, коли надходить нова ціна. У панелях моніторингу в реальному часі системи, які відстежують показники, такі як затримка сервера, температури датчиків або пропускна здатність мережі, часто відображають мінімальне або максимальне значення за останні N вибірок для виявлення аномалій або підкреслення нещодавніх екстремумів. Оскільки ці панелі вводуть безперервний потік показників, омотувана O(1) оновлення на вибірку дозволяє системі залишатися чуйною навіть за високих швидкостей даних, де наївний метод пересканування міг відставати. У операціях згортки та агрегації, які використовуються в обробці зображень і згорткових нейронних мережах, шар максимального фільтрування обчислює найбільше значення у вікні ковзання над зображенням або карткою ознак, часто переміщуючи це вікно по двох вимірах. Хоча повне двовимірне максимальне фільтрування розширює цю ідею ще далі, монотонний де́к є будівельним блоком: застосування його рядками, а потім колонками дозволяє реалізувати ефективний обчислення максимальних значень у двох вимірах, що має велике значення при обробці великих зображень або високорозмірних карт ознак повторно під час навчання. Крім цих прикладів, такий же шаблон зустрічається в аналізі мережевих пакетів, скануванні геномних послідовностей та будь-якій ситуації, коли потрібно багаторазово запитувати обмежений історичний вікно, коли надходять нові дані безперервно.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Sliding Window Minimum via Monotonic Deque і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.