Чи може рекурсивний алгоритм працювати швидше ніж ітеративний
Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Всім привіт! Мене звати Кирило, я розробник програмного забезпечення та у вільний час вирішую алгоритмічні задачі на leetcode. Саме тому мене зацікавила стаття, написана by Sergiy Morenets про те, як по-різному оптимізувати алгоритми в Java. Сергій на прикладі однієї алгоритмічної проблеми представляє декілька алгоритмів та пояснює переваги та недоліки кожного. Я ніколи не писав на Java, але концептуально підходи до оптимізації та алгоритми є language-agnostic, тобто такими, що можуть бути використані незалежно від мови програмування.
Я прочитав статтю та мене в ній здивувало лише одне — відсутність рекурсивного алгоритму для вирішення задачі. І в цій статті я хотів би показати, як рекурсивний алгоритм може вирішити проблему та випадки, коли він може працювати краще ніж ітеративний.
TL;DR
Так, рекурсивний алгоритм може працювати швидше ніж ітеративний за певних умов.
Проблема
Для демонстрації переваг та недоліків алгоритмів я буду використовувати ту саму проблему, що і Сергій у зазначеній вище статті.
Опис проблеми
Написати функцію, що
- приймає на вхід рядок, що складається лише з 4 символів: A, B, C, D;
- видаляє всі комбінації AB, BA, CD, DC;
- повертає новий рядок, що не містить подібних комбінацій.
Використані алгоритми
Одразу хочу наголосити, що всі використанні алгоритми є в публічному доступі. За бажання ви можете завантажити проєкт та спробувати їх самі локально. Так само ви можете спробувати написати інші алгоритми та порівняти їх з тими, що написав я.
Ітеративні алгоритми
Перший ітеративний алгоритм
Цей алгоритм являє собою один ітеративний цикл. В цьому алгоритмі я використав додатковий контейнер — зв’язаний список — для того, щоб зберігати літери, котрі не створюють комбінації.
Таким чином на кожній ітерації ми перевіряємо, чи створюється комбінація з останнім елементом у зв’язаному списку разом з літерою, котру перевіряємо у початковому рядку.
Якщо комбінація є, то ми видаляємо останній елемент зі зв’язаного списку та йдемо далі. Якщо комбінації немає, то ми додаємо цей елемент до зв’язаного списку в кінець. Після того, як ітерація закінчується, перетворюємо зв’язаний список на вихідний рядок.
Runtime complexity
O(n), де n — розмір вхідного рядка. Не залежить від контенту.
Переваги
Простота реалізації та, як наслідок, дебагу.
Недоліки
- Використання додаткового контейнера, що теоретично може збільшити використання пам’яті в 2 рази.
- Хоча runtime complexity цього алгоритму O(n), в реальності швидкість цього алгоритму буде деградувати саме через зв’язаний список. Теоретично всі додані елементи до зв’язаного списку можуть видалитись — це час. Також будемо витрачати час на перетворення зв’язаного списку на рядок.
Другий ітеративний алгоритм
Цей алгоритм дуже схожий на перший. Ключова відмінність від першого — це те, що видалення знайдених комбінацій відбувається лише в кінці, а взагалі все це відбувається у початковому рядку.
Щоб швидко знаходити комбінації, які можуть з’явитись після «видалення», використовуємо стек, в якому зберігаємо індекси елементів, котрі потрібно перевіряти на наявність комбінацій.
Runtime complexity
O(n), де n — розмір вхідного рядка. Не залежить від контенту.
Переваги
- Простота реалізації та, як наслідок, дебагу.
- Швидкий.
Недоліки
- Використання додаткового контейнера може збільшити використання пам’яті, в найгіршому випадку — у 2 рази. Але саме розмір збільшення залежить від платформи.
Рекурсивні алгоритми
Перший рекурсивний алгоритм
Перший рекурсивний алгоритм у цьому випадку є максимально простим. Ми ділимо вхідний рядок на дві половини та запускаємо той самий алгоритм для двох половин. Результат для лівої половини та правої половини вже не мають комбінацій, котрі мають бути видаленими. Але комбінації можуть бути, якщо ті дві половини з’єднати.
Використовуємо two pointers підхід, щоб «видалити» комбінації після з’єднання результатів від двох рекурсивних колів. Комбінації на стику видаляються простим з’єднанням результату лівої половини та правої половини (зменшеної, якщо потрібно).
Послідовність викликів з поясненням
- f(ABCDABBACD) ділить навпіл, викликає функцію для лівої половини спершу, а потім для правої. З’єднує результати в один та повертає потім пустий рядок.
- f(ABCDA) ділить навпіл, викликає функцію так само для лівої половини, потім для правої. З’єднує результати та повертає рядок, що містить A.
- f(AB) повертає пустий рядок, оскільки це base case рекурсивного алгоритму.
- f(CDA) ділить навпіл, викликає f(
С
), а потім f(DA) та з’єднує результати. Повертає C. - f(
С
) повертає рядок з літерою C — base case. - f(DA) повертає пустий рядок — base case.
- f(BBACD) ділить навпіл, викликає f(BB), f(ACD) та з’єднує результати. Повертає рядок з літерою B.
- f(BB) повертає рядок BB — base case.
- f(ACD) ділить навпіл, викликає f(A), f(CD) та з’єднує результати. Повертає рядок з літерою A.
- f(A) повертає A — base case.
- f(CD) повертає пустий рядок — base case.
Runtime complexity
Складність рекурсивних алгоритмів важче рахувати, бо тут немає звичних циклів, за якими проводиш розрахунок. Складність цього алгоритму буде O(n * n) через те, що ми проходимо увесь інпут та копіюємо рядки для кожного рекурсивного колу.
Переваги
Немає. Але допомагає краще розібратись з рекурсивними алгоритмами.
Недоліки
Дуже повільний. В тестах використовуватись не буде.
Другий рекурсивний алгоритм. Модифікація першого.
Цей алгоритм є модифікацією першого рекурсивного. Я додав до алгоритму memoization для вхідних рядків розміром менше або рівним 8 байт. Memoization — це оптимізаційний підхід, коли алгоритм зберігає результат для певного інпуту.
В нашому випадку ми будемо зберігати результат алгоритму для інпуту розміром 8 та менше байт. Рядок з 8 символів може створювати 65,536 різних комбінацій.Таким чином ми можемо ще мінімізувати витрати на рахування хешу рядка, котрий може ніколи не трапитись.
Послідовність викликів
Підхід memoization добре працює, якщо вхідний рядок не дуже рандомізований, тому лише для прикладу я наведу діаграму рекурсивних колів на ідеальному інпуті — 8 пар AB.
- f(ABA...AB) ділить навпіл, викликає функцію для лівої половини, а потім для правої та з’єднує. В цьому випадку поверне пустий рядок.
- f(ABABABAB) ділить навпіл, викликає функцію для лівої половини, а потім для правої та з’єднує. В цьому випадку поверне пустий рядок. Зберігає результат для цього інпуту.
- f(ABAB) ділить навпіл, викликає функцію для лівої половини, для правої та з’єднує. В цьому випадку повертає пустий рядок та зберігає результат.
- f(AB) повертає пустий рядок — base case.
- f(AB) те саме, що і 4.
- f(ABAB) в цьому випадку функція відпрацює так само як і в base case. Поверне збережний результат — пустий рядок. Особливість в тому, що наступний поділ та виклик функції для інших половин не буде відбуватись взагалі.
- Виклик не відбувається.
- Виклик не відбувається.
- f(ABABABAB) відправить збережений результат — пустий рядок. Інші виклики не відбуваються взагалі.
- Виклик не відбувається.
- Виклик не відбувається.
- Виклик не відбувається.
- Виклик не відбувається.
- Виклик не відбувається.
Runtime complexity
Це порахувати стає ще складніше. На рандомізованому рядку подібних збігів буде не дуже багато. Тільки якщо розмір інпуту не збільшиться значно. І навіть в цьому випадку на великому інпуті оптимізація спрацює лише на трьох найнижчих рівнях.
У загальному випадку складність буде O(n * n), тому що ми все ще копіюємо всі рядки та на великих даних оптимізація найнижчих трьох рівнів буде нівелюватись. У найкращому випадку складність може досягати O(n * logn), тому що ми не проходимо увесь інпут повністю. Але все одно буде деградувати до O(n * n) навіть на найкращому інпуті у випадку збільшення довжини рядка.
Переваги
Може працювати швидше ніж перший рекурсивний алгоритм в деяких випадках, але все одно повільніше ніж ітеративний.
Недоліки
Повільний. В тестах використовуватись не буде.
Третій рекурсивний алгоритм
Якщо попередній алгоритм може працювати O(n * logn) у найкращому випадку, то чому ми не можемо зняти обмеження у 8 байт для memoization? Можемо зняти та цей алгоритм буде працювати O(n * logn) у найкращому випадку незалежно від довжини рядка. Але варто зауважити, що якщо ми не маємо обмежень на довжину рядку, алгоритм буде деградувати до O(n * n * n) через копіювання, прохід по всьому інпуту та вирішення колізій у хеш мапі. І на дійсно великому інпуті (та особливо рандомному) memoization буде проблемою ніж оптимізацією.
Переваги
Ніяких. Реально. Лише як навчальний приклад
Недоліки
- Повільний.
- Працює швидше ніж попередній алгоритм ЛИШЕ у випадку інпуту, котрий складається з якихось повторюваних простих комбінацій.
- Якщо інпут хоч трохи рандомізований, деградує у O(n * n * n) на великих даних.
Рекурсивні алгоритми in place
Як ми вже могли помітити рекурсивні алгоритми досі повільні, якщо порівнювати runtime complexity. Дуже значний вплив на перформанс є копіювання інпуту між викликами. Цього можна уникнути, якщо використаємо рекурсивний алгоритм, котрий змінює вхідний інпут замість того, щоб копіювати його.
Перший рекурсивний алгоритм in place
Рекурсивний алгоритм in place приймає посилання на інпут та індекси, які позначають проміжок, в якому потрібно працювати. Повертає рекурсивний алгоритм in place так само індекси. Але ті вже можуть бути іншими, в залежності від того, як саме змінився інпут. Цей алгоритм складається з декількох частин:
- base case — якщо проміжок складає 2 та менше.
- Якщо елементи в тому проміжку складають комбінацію, котру потрібно видалити, замінюємо значення елементів на х або будь-який інший маркер та повертаємо { first, first }. Таким чином ми будемо знати, що для такого інпуту функція повертає пустий рядок.
- Якщо нема комбінації, просто повертаємо { first, last }, вхідний рядок залишився без змін.
- Знаходимо середній індекс та викликаємо функцію для лівої половини та правої.
- «З’єднуємо» результати обох викликів. Для цього ми просто в циклі звужуємо два ренджи, ставимо маркери там, де були знайдені комбінації, допоки ці комбінації є.
- Копіюємо результат з правої половини до лівої, якщо ліва взагалі змінилась якось.
- Ставимо маркери від останнього скопійованого елемента до індексу last.
- Повертаємо новий рендж, дійсний.
Runtime complexity
O(n) незалежно від інпуту
Переваги
- Швидший ніж всі попередні рекурсивні алгоритми.
- Може бути оптимізований.
Недоліки
- Складніший ніж ітеративний алгоритм.
- Повільніший ніж ітеративний алгоритм.
Другий рекурсивний алгоритм in place
Це є модифікація першого рекурсивного алгоритму in place. До нього так само доданий memoization на рядок у 8 байт. Таким чином трошки змінюється base case. Тепер ми не просто повертаємо пустий рендж, а і копіюємо результат з збережених даних до вхідного рядка.
Runtime complexity
Runtime complexity цього алгоритму залежить саме від контенту. У випадку рандомних даних та даних типу AAAAAAAA + BBBBBBBB complexity буде на рівні із ітеративним алгоритмом — O(n). Це буде підтверджено на тестах, результати котрих є в кінці. У випадку найкращих даних типу ABABABAB... цей алгоритм відпрацьовує швидше ніж ітеративний. Але можу з упевненістю сказати, що на великих даних цей алгоритм не буде мати O(logn) complexity, тому що як ми бачили розгалуження перестають працювати лише на нижчих трьох рівнях із memoization рівному 8 байт.
Переваги
- Може працювати швидше за ітеративний алгоритм на певному інпуті (рандомізованому аж до 40 %).
- Може бути оптимізований згідно інпуту.
Недоліки
- В певних випадках може бути повільнішим за ітеративний алгоритм.
- Складніший ніж ітеративний алгоритм.
Третій рекурсивний алгоритм in place
Відрізняється від другого лише тим, що не має обмежень на інпут для memoization оптимізації.
Runtime complexity
Так само як і третій звичайний рекурсивний алгоритм на великих, хоч і трохи рандомних даних, цей алгоритм дуже сильно деградує performance-wise. Єдиний випадок, де він працює дуже швидко, — це на ДУЖЕ однорідному інпуті ABABABAB чи AAAAAAA...
Переваги
Дуже швидкий на однорідному інпуті.
Недоліки
● Дуже швидкий ЛИШЕ на однорідному інпуті.
● Дуже повільний, якщо інпут хоч трохи рандомізований.
Порівняння
Для порівняння алгоритмів я використовував декілька різних інпутів розміром від 1 000 до 1 000 000. Один інпут тестувався на кожному алгоритмі 20 разів для запобігання шуму. Середнє значення на 20 ітераціях буде давати похибку у 5%. Як ми побачимо, різниця в результатах набагато більше ніж 5%.
Worst case data
Опис даних
Найгіршим випадком даних вважається n/2 кількість літер А, потім така сама кількість літер B. Таким чином будь-який рекурсивний алгоритм втрачає бенефіти рекурсивного та починає працювати як ітеративний.
Результат
Перший рекурсивний алгоритм in place (w/o memoization) дуже сильно деградує performance-wise.
Інші рекурсивні алгоритми in place працюють приблизно так само, як і ітеративний алгоритм. Без особливих змін.
Random data
Перший рекурсивний алгоритм in place починає працювати помітно гірше зі збільшенням інпуту.
Другий рекурсивний алгоритм in place на деяких проміжках працює швидше, на деяких — повільніше ніж ітеративний.
60% of random data
Як і тоді, коли маємо повністю рандомний інпут, тут є проміжки, де рекурсивний алгоритм працює повільніше, ніж ітеративний. Так само є проміжки, де він працює швидше.
40% of random data
На цих даних ми вже можемо побачити, що рекурсивний алгоритм з фіксованим memoization працює швидше ніж ітеративний. На даних з меншою рандомізацією ця крива буде ще знижуватись.
10% of random data
Тут ми можемо побачити, як різниця між ітеративним та рекурсивним алгоритмом ще збільшується. Можна також побачити, як рекурсивний алгоритм, навіть без memoization, починає працювати швидше ніж ітеративний в деяких проміжках часу.
Best case scenario data
Опис даних
Найкращим випадком даних вважається n/2 кількість пар, котра перетвориться на пустий рядок — типу ABABABAB. Варто зауважити, що це найкращий випадок саме для алгоритмів з memoization.
Результат
Ми бачимо, як рекурсивні алгоритми з мемоізацією працюють швидше ніж ітеративний алгоритм.
1000 to 4M A letters
Цей набір даних я використав лише для того, щоб показати, як швидкість певних алгоритмів може бути як дуже повільною, так і дуже швидкою в залежності від інпуту. Цей той випадок, коли рекурсивний алгоритм з мемоізацією без лімітів працює набагато швидше ніж будь-які інші алгоритми, використані в цьому проєкті.
Висновки
Як можна побачити з графіків, швидкість алгоритмів може значно відрізнятися від інпуту. Ми побачили як один і той самий алгоритм може бути як дуже повільним, так і дуже швидким в залежності від інпуту.
Тож варто звертати увагу на те, який інпут планується для певного алгоритму. Від цього може залежати його швидкість і, як результат, це може коштувати компанії менше (або більше) грошей.
Не варто також забувати про memoization — підхід, котрий дуже часто використовується для оптимізації рекурсивних алгоритмів. Якщо не використовувати memoization, то нащо тоді взагалі писати рекурсивні алгоритми?
І таки відповідь на запитання: чи може рекурсивний алгоритм працювати швидше ніж ітеративний? Так, може, за певних умов.
Апдейт #1
Дуже дякую за коментарі та пропозиції інших алгоритмів. Протестув ще один ітеративний алгоритм із лише двома ітераторами. Та отримав дані.
Two pointers linear algo
Алгоритм максимально простий та стрейтфорвард. Використовуємо два ітератори: insert та check. Як виходить із назви, один ітератор використовуємо для того, щоб вставляти літери, котрі були перевірені, другий — для того, щоб перевіряти, чи не буде тут комбінації, котру потрібно буде видалити.
Результати
Якщо дуже коротко, то цей алгоритм відпрацьовує найшвидше в усіх випадках, крім одного — де не потрібно видаляти ніякі символи. Лише в цьому кейсі рекурсивний алгоритм відпрацьовує швидше. Думаю, що це відбувається від того, як саме імплементований рекурсивний алгоритм. Припускаю, що перформанс дроп у рекурсивних алгоритмів навіть на 10 % рандомізованому інпуті відбувається через те, як копіюються вже відомі результати. Очікую, що можна отримати кращі результати, якщо копіювати вже прораховані результати цілим ренджем. Отже графіки.
22 коментарі
Додати коментар Підписатись на коментаріВідписатись від коментарів