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

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

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

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

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

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

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

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

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

Алгоритм Marker.

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

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

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

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

Докладніше: ^[en]

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

Примітки

1. Karp, Richard M. (1992). (PDF). IFIP Congress (1). 12: 416—429. Архів оригіналу (PDF) за 5 березня 2016. Процитовано 17 серпня 2015.
2. Гирш Э. Алгоритмы, работающие в реальном времени