Алгоритм з виконанням на місці

В інформатиці алгоритм на місці — це алгоритм, який працює безпосередньо над вхідною структурою даних, не вимагаючи додаткової пам'яті, пропорційної розміру вхідних даних. Інакше кажучи, він змінює вхідні дані на місці, не створюючи окремої копії структури даних. Алгоритм, який виконується не на місці, звуть алгоритмом з виконанням не на місці або поза місцем.

"Виконання на місці" може мати дещо інші значення. У найстрогішому варіанті це позначає алгоритм, що може мати лише сталу кількість додаткової пам'яті, враховуючи все, включно з викликами функцій і вказівниками. Однак цей варіант визначення – дуже обмежений, оскільки простий індекс масиву з довжиною $n$ вимагає $O (log n)$ бітів. У ширшому сенсі «виконання на місці» означає, що алгоритм не використовує додаткову пам'ять для роботи з вхідними даними, але може потребувати невелику, проте непостійну додаткову ділянку пам'яті для своєї роботи. Зазвичай ця ділянка має розмір $O (log n)$ , хоча іноді допускається будь-що в межах $o (n)$ . Зауважте, що складність за пам'яттю також має різноманітні варіанти щодо того, рахувати чи ні довжини індексів як частину використаної пам'яті. Нерідко складність за пам'яттю задається відносно кількості необхідних індексів або вказівників, ігноруючи їх розрядність. Ця стаття звертається до загальної складності пам'яті (Детермінованого простору), що враховує розрядності вказівників. Тому вимоги до пам'яті тут мають додатковий коефіцієнт $log n$ порівняно з аналізом, який ігнорує довжину індексів і вказівників.

Алгоритм може враховувати вхідні дані як частину використання пам'яті. Оскільки алгоритми на місці зазвичай перезаписують вхідні дані вихідними, додаткова пам'ять не потрібна. Коли запис виводу відбувається в пам’ять, доступну лише для запису, або в потік, можливо, доречніше враховувати лише робочу пам'ять алгоритму. У теоретичних застосуваннях, таких як скорочення лог-простору, більш типово ігнорувати вихідну пам'ять (у таких випадках більш важливо, щоб вихідна пам'ять була доступна лише для запису).

Приклади

Дано масив a з $n$ елементів; припустімо, що потрібен масив, який містить ті самі елементи у зворотному порядку, а вихідний масив – усунути. Один, здавалося б, простий спосіб зробити це — створити новий масив такого ж розміру, заповнити його копіями з a у відповідному порядку, а потім видалити a.

функція розвернути(a[0..n - 1])
   виділити b[0..n - 1]
   для i від 0 до n - 1
     b[n − 1 − i] := a[i]
   повернути b

На жаль, це вимагає $O (n)$ додаткової пам'яті для того, щоб масиви a і b були доступними одночасно. Крім того, виділення та звільнення пам'яті нерідко є повільними операціями. Оскільки масив a більше не потрібен, його можна перезаписати його власним реверсом за допомогою алгоритму на місці, якому знадобиться лише постійне число (2) цілих чисел для допоміжних змінних i та tmp, незалежно від того, наскільки великим є масив.

функція розвернути_на_місці(a[0..n-1])
   для i від 0 до округлити((n-2)/2)
     tmp := a[i]
     a[i] := a[n − 1 − i]
     a[n − 1 − i] := tmp

Як інший приклад, чимало алгоритмів сортування змінює порядок у масивах на відсортований на місці, серед них: бульбашкове сортування, гребінчасте сортування , ⁣сортування вибіркою, сортування вставлянням, сортування купою та сортування Шелла. Ці алгоритми потребують лише кілька вказівників, тому їх складність за пам'яттю – $O (log n)$ . ^[1]

Швидке сортування працює з даними, які потрібно відсортувати, на місці. Однак воно потребує $O (log n)$ місця на стеку для вказівників, щоб відстежувати підмасиви у стратегії «розділяй і володарюй». Отже, швидке сортування потребує $O (log 2 n)$ додаткової пам'яті. Попри те, що ця ділянка несталого розміру технічно виводить швидке сортування з категорії алгоритмів з виконанням на місці, швидке сортування та інші алгоритми, які потребують лише $O (log n)$ додаткових вказівників, зазвичай вважаються алгоритмами на місці.

Більшість алгоритмів пошуку також є алгоритмами з виконанням на місці, хоч деякі з них значно змінюють вхідний масив у процесі пошуку кінцевого результату постійного розміру.

Деякі алгоритми обробки тексту, такі як обрізання та розвертання, можуть виконуватися на місці.

У теорії обчислювальної складності

У теорії складності обчислень строге визначення алгоритмів на місці включає всі алгоритми зі складністю за пам'яттю $O (1)$ , клас DSPACE (1). Цей клас дуже обмежений; це дорівнює регулярним мовам. ^[2] Фактично, він навіть не вміщає жодного з перерахованих вище прикладів.

Алгоритми зазвичай розглядаються в L, класі проблем, які потребують $O (log n)$ додаткової пам'яті, щоб бути алгоритмами з виконанням на місці. Цей клас більше відповідає практичному визначенню, оскільки допускає числа розміром $n$ – вказівники чи індекси. Однак це розширене визначення все одно виключає швидке сортування — через його рекурсивні виклики.

Визначення алгоритмів з виконанням на місці за класом L має деякі цікаві наслідки; наприклад, це означає, що існує (досить складний) алгоритм на місці, призначений для визначення того, чи існує шлях між двома вузлами в неорієнтованому графі ^[3], — це проблема, яка вимагає $O (n)$ додаткової пам'яті з використанням типових алгоритмів, таких як пошук у глибину (біт відвідування для кожного вузла). Це, своєю чергою, веде до алгоритмів з виконанням на місці для таких проблем, як з'ясування того, чи є граф двочастковим, або перевірка того, чи два графи мають однакову кількість компонент зв'язності.

Роль випадковості

У багатьох випадках вимоги до пам'яті для алгоритму можна суттєво скоротити за допомогою рандомізованого алгоритму. Наприклад, якщо хтось хоче знати, чи дві вершини в графі з $n$ вершин знаходяться в одній компоненті зв'язності графа, не існує відомого простого детермінованого алгоритму на місці для визначення цього. А проте, якщо просто почати з однієї вершини й виконати випадкове блукання з близько $20 n 3$ кроків, то ймовірність того, що зустрінеться друга вершина, за умови, що вона знаходиться в тій же компоненті, дуже висока. Подібним чином, є прості рандомізовані алгоритми на місці для перевірки простоти, такі як тест на простоту Міллера-Рабіна, а також є прості алгоритми випадкового факторування на місці, такі як P-алгоритм Поларда.

У функційному програмуванні

Функційні мови програмування нерідко не заохочують або не підтримують явні алгоритми на місці, які перезаписують дані, оскільки це різновид побічного ефекту; натомість вони дозволяють лише створювати нові дані. Проте добрі компілятори функційної мови нерідко розуміють, коли створюється об’єкт, дуже схожий на наявний, а потім старий викидається, і оптимізують це до внесення простих змін «за лаштунками».

Зауважте, що в принципі можливо створювати алгоритми з виконанням на місці, які не змінюють дані (якщо тільки ці дані більше ніде не використовуються), але це рідко робиться на практиці.

Посилання

↑ Вимоги до бітового розміру вказівника – $O (log n)$ , але розмір вказівника може вважатися сталою для більшості сортувальних застосувань.
↑ Maciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. Structure in Complexity Theory Conference, pp. 64-78. 1994. Online: p. 3, Theorem 2.
↑ Reingold, Omer (2008), Undirected connectivity in log-space, Journal of the ACM, 55 (4): 1—24, doi:10.1145/1391289.1391291, MR 2445014, Шаблон:ECCC

[1] Вимоги до бітового розміру вказівника – $O (log n)$ , але розмір вказівника може вважатися сталою для більшості сортувальних застосувань.

[2] Maciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. Structure in Complexity Theory Conference, pp. 64-78. 1994. Online: p. 3, Theorem 2.

[3] Reingold, Omer (2008), Undirected connectivity in log-space, Journal of the ACM, 55 (4): 1—24, doi:10.1145/1391289.1391291, MR 2445014, Шаблон:ECCC

[1]

[2]

[3]