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

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

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

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

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

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

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

Нехай  — алгоритм, а  — послідовність запитів. Час обробки послідовності запитів алгоритмів  — це кількість звернень до диску. Нехай  — якийсь оптимальний алгоритм. Тоді алгоритм називається -оптимальним (c-competitive), якщо для будь-якого : . Де,  — константа відносно , але вона може залежати від k інших параметрів. Але це виконується — для детермінованих алгоритмів, для ймовірнісних, розглядається не час, а її математичне очікування. Будемо розглядати випадок, коли  — ймовірнісний online алгоритм, а  — детермінований offline алгоритм («oblivious adversary»), тобто він заздалегідь всю знає послідовність запитів .

Алгоритм Marker.

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

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

Припустимо, що в даний момент наша система знаходиться в стані і до нас приходить запит . Тоді ми вибираємо новий стан , яке містить і мінімізує наступну функцію від , де  — це послідовність запитів, які ми вже обробили, а  — це вартість (оптимального) переходу зі стану в .

Докладніше: Задача про k офіціантів[en]

Узагальнимо задачу кешування. Нехай у нас є деякий метричний простір з метрикою , точки якого ми будемо розглядати як столики, і офіціантів, тобто деяка підмножина точок цього простору. Час від часу зі столиків надходять замовлення. Формально, замовлення — це координати столика. Замовлення потрібно обслуговувати, тобто треба вибрати одного з офіціантів і перемістити його в дану точку простору. Довжиною такого переміщення буде відстань між вихідною та кінцевою його точками. Кожен офіціант в кожен момент часу знаходиться біля якогось столика, і стан (конфігурація) системи описується множиною координат столиків, біля яких в даний момент знаходяться офіціанти. Тобто стан  — це мультимножина (множина з кратними елементами), яка складається з точок простору. Назавжди зафіксуємо початковий стан нашої системи. Нехай =  — послідовність замовлень. Тоді робоча функція , що зіставляє стану , найменшу відстань обслуговування з початкового стану , в стан . (Відстань обслуговування — це сума відстаней, пройдених всіма офіціантами, причому найменший шлях визначається за допомогою оптимального offline алгоритму, якому відоме ).[2]

Copyright