Онлайн алгоритм

Онлайн алгоритм (англ. online algorithm) — алгоритми, що може обробляти дані в міру їх надходження, не маючи загального доступу до всіх даних з самого початку.

На відміну від нього, офлайн алгоритм (англ. offline algorithm) може працювати з усіма даними від самого початку. Розділ в дослідженні операцій, який займається розробкою онлайн алгоритмів називається онлайн оптимізацією.

Для прикладу розглянемо два алгоритми сортування: сортування вибором та сортування вставкою. Сортування вибором послідовно вибирає мінімальний елемент з невідсортованого залишку та розміщує його спереду, що потребує доступу до всіх входових даних; тобто, це буде офлайн алгоритм. На відміну від нього, сортування вставкою за одну ітерацію бере один входовий елемент і отримує частковий розв'язок без урахування майбутніх елементів. Таким чином, сортування вставкою — це онлайн алгоритм.

Зверніть увагу, що кінцевий результат сортування вставкою є оптимальним, тобто, це правильно відсортований список. Для багатьох задач онлайн алгоритми не можуть мати таку ж швидкодію, як офлайн алгоритми. Якщо співвідношення швидкодії онлайн алгоритму до оптимального офлайн-алгоритму є обмеженим, то онлайн алгоритм називається конкурентним.

Очевидно, що не кожен офлайн алгоритм має ефективний онлайн відповідник.

Задача кешування (Paging Problem)

Є два види пам'яті — дискова, більша за об'ємом, але повільна, і кеш, швидка, але дуже мала. Вся пам'ять розбита на блоки. Нехай в кеш-пам'яті k блоків, а на диску, відповідно, набагато більше. До нас поступають запити на ті чи інші блоки, і ми повинні відразу ж їх обробити. Є два варіанти: або цей блок вже є в кеші, або його там немає. Якщо він в кеші є, то в цьому випадку ми майже не витрачаємо час. I тоді час роботи алгоритму можна вимірювати кількістю звернень до вінчестера. Алгоритми відрізняються один від одного реакцією на запити відсутніх в кеші блоків. Зрозуміло, що ми повинні блок, на який йде запит довантажити в кеш, не зрозуміло тільки, який з уже присутніх там блоків ми повинні для цього вивантажити. Звичайно, хотілося б вивантажити «непотрібний» блок, але оскільки ми обробляємо запити в реальному часі, ми не знаємо, який блок нам буде потрібний в подальшому. Постає й інше питання: як порівняти, який алгоритм найкращий.

Нехай ${\mbox{A}}$ — алгоритм, а ${\mbox{r}}$ — послідовність запитів. Час обробки послідовності запитів алгоритмів ${\mbox{cost}}_{\mathrm {A} }(r)$ — це кількість звернень до диску. Нехай ${\mbox{opt}}$ — якийсь оптимальний алгоритм. Тоді алгоритм ${\mbox{A}}$ називається ${\mbox{c}}$-оптимальним (c-competitive), якщо для будь-якого ${\mbox{r}}$: ${\mbox{cost}}_{\mathrm {A} }(r)$ $\leq$ $c\cdot {\mbox{cost}}_{\mathrm {otp} }(r)+c_{1}$. Де, ${\mbox{c}}$ — константа відносно ${\mbox{r}}$, але вона може залежати від k інших параметрів. Але це виконується — для детермінованих алгоритмів, для ймовірнісних, розглядається не час, а її математичне очікування. Будемо розглядати випадок, коли ${\mbox{A}}$ — ймовірнісний online алгоритм, а ${\mbox{opt}}$ — детермінований offline алгоритм («oblivious adversary»), тобто він заздалегідь всю знає послідовність запитів ${\mbox{r}}$.

Алгоритм Marker.

Елементи кешу позначаються 0 або 1. Час роботи поділяється на періоди. На початку кожного періоду всі елементи кешу позначені 0. Приходить запит. Якщо це запит на блок, який вже є в кеші, то він позначається 1. Якщо запитують елемент, якого немає в кеші, то ми випадковим чином вибираємо з непомічених (тобто помічених 0) блок, куди ми будемо довантажувати необхідний. Довантаживши, ми помічаємо його 1. Рано чи пізно у нас не залишиться блоків, помічених 0. У цьому стані ми можемо працювати, поки у нас запитують блоки, що знаходяться в кеші. Як тільки надійде запит на елемент, що не міститься в кеші, ми обнулив всі позначки і почнемо новий період.

Алгоритм Work Function Algorithm.

Припустимо, що в даний момент наша система знаходиться в стані ${\mbox{X}}$ і до нас приходить запит ${\mbox{r}}$. Тоді ми вибираємо новий стан ${\mbox{X'}}$, яке містить ${\mbox{r}}$ і мінімізує наступну функцію від $~X':{\mbox{W}}_{\mathrm {\rho r} }(X')+{\mbox{D}}(X,X')$, де $\rho$ — це послідовність запитів, які ми вже обробили, а ${\mbox{D}}(X,X')$ — це вартість (оптимального) переходу зі стану ${\mbox{X}}$ в ${\mbox{X'}}$ .

Задача про $k$ офіціантів (k-server problem)

Узагальнимо задачу кешування. Нехай у нас є деякий метричний простір з метрикою ${d}$, точки якого ми будемо розглядати як столики, і ${k}$ офіціантів, тобто деяка підмножина $k$ точок цього простору. Час від часу зі столиків надходять замовлення. Формально, замовлення — це координати столика. Замовлення потрібно обслуговувати, тобто треба вибрати одного з офіціантів і перемістити його в дану точку простору. Довжиною такого переміщення буде відстань між вихідною та кінцевою його точками. Кожен офіціант в кожен момент часу знаходиться біля якогось столика, і стан (конфігурація) системи описується множиною координат столиків, біля яких в даний момент знаходяться офіціанти. Тобто стан ${X}$ — це мультимножина (множина з кратними елементами), яка складається з ${k}$ точок простору. Назавжди зафіксуємо початковий стан ${A}_{0}$ нашої системи. Нехай ${r}$ = ${r}_{1},{r}_{2},...,{r}_{n}$ — послідовність замовлень. Тоді робоча функція ${W}_{r}$, що зіставляє стану ${X}$, найменшу відстань обслуговування ${r}$ з початкового стану ${A}_{0}$, в стан ${X}$. (Відстань обслуговування — це сума відстаней, пройдених всіма офіціантами, причому найменший шлях визначається за допомогою оптимального offline алгоритму, якому відоме $r$).