Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 30
×

Чи може рекурсивний алгоритм працювати швидше ніж ітеративний

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Всім привіт! Мене звати Кирило, я розробник програмного забезпечення та у вільний час вирішую алгоритмічні задачі на leetcode. Саме тому мене зацікавила стаття, написана by Sergiy Morenets про те, як по-різному оптимізувати алгоритми в Java. Сергій на прикладі однієї алгоритмічної проблеми представляє декілька алгоритмів та пояснює переваги та недоліки кожного. Я ніколи не писав на Java, але концептуально підходи до оптимізації та алгоритми є language-agnostic, тобто такими, що можуть бути використані незалежно від мови програмування.

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

TL;DR

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

Проблема

Для демонстрації переваг та недоліків алгоритмів я буду використовувати ту саму проблему, що і Сергій у зазначеній вище статті.

Опис проблеми

Написати функцію, що

  • приймає на вхід рядок, що складається лише з 4 символів: A, B, C, D;
  • видаляє всі комбінації AB, BA, CD, DC;
  • повертає новий рядок, що не містить подібних комбінацій.

Використані алгоритми

Одразу хочу наголосити, що всі використанні алгоритми є в публічному доступі. За бажання ви можете завантажити проєкт та спробувати їх самі локально. Так само ви можете спробувати написати інші алгоритми та порівняти їх з тими, що написав я.

Лінк на проєкт на github.com

Ітеративні алгоритми

Перший ітеративний алгоритм

Цей алгоритм являє собою один ітеративний цикл. В цьому алгоритмі я використав додатковий контейнер — зв’язаний список — для того, щоб зберігати літери, котрі не створюють комбінації.

Таким чином на кожній ітерації ми перевіряємо, чи створюється комбінація з останнім елементом у зв’язаному списку разом з літерою, котру перевіряємо у початковому рядку.

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

Runtime complexity

O(n), де n — розмір вхідного рядка. Не залежить від контенту.

Переваги

Простота реалізації та, як наслідок, дебагу.

Недоліки

  • Використання додаткового контейнера, що теоретично може збільшити використання пам’яті в 2 рази.
  • Хоча runtime complexity цього алгоритму O(n), в реальності швидкість цього алгоритму буде деградувати саме через зв’язаний список. Теоретично всі додані елементи до зв’язаного списку можуть видалитись — це час. Також будемо витрачати час на перетворення зв’язаного списку на рядок.

Source

Другий ітеративний алгоритм

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

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

Runtime complexity

O(n), де n — розмір вхідного рядка. Не залежить від контенту.

Переваги

  • Простота реалізації та, як наслідок, дебагу.
  • Швидкий.

Недоліки

  • Використання додаткового контейнера може збільшити використання пам’яті, в найгіршому випадку — у 2 рази. Але саме розмір збільшення залежить від платформи.

Source

Рекурсивні алгоритми

Перший рекурсивний алгоритм

Перший рекурсивний алгоритм у цьому випадку є максимально простим. Ми ділимо вхідний рядок на дві половини та запускаємо той самий алгоритм для двох половин. Результат для лівої половини та правої половини вже не мають комбінацій, котрі мають бути видаленими. Але комбінації можуть бути, якщо ті дві половини з’єднати.

Використовуємо two pointers підхід, щоб «видалити» комбінації після з’єднання результатів від двох рекурсивних колів. Комбінації на стику видаляються простим з’єднанням результату лівої половини та правої половини (зменшеної, якщо потрібно).

Послідовність викликів з поясненням

  1. f(ABCDABBACD) ділить навпіл, викликає функцію для лівої половини спершу, а потім для правої. З’єднує результати в один та повертає потім пустий рядок.
  2. f(ABCDA) ділить навпіл, викликає функцію так само для лівої половини, потім для правої. З’єднує результати та повертає рядок, що містить A.
  3. f(AB) повертає пустий рядок, оскільки це base case рекурсивного алгоритму.
  4. f(CDA) ділить навпіл, викликає f(С), а потім f(DA) та з’єднує результати. Повертає C.
  5. f(С) повертає рядок з літерою C — base case.
  6. f(DA) повертає пустий рядок — base case.
  7. f(BBACD) ділить навпіл, викликає f(BB), f(ACD) та з’єднує результати. Повертає рядок з літерою B.
  8. f(BB) повертає рядок BB — base case.
  9. f(ACD) ділить навпіл, викликає f(A), f(CD) та з’єднує результати. Повертає рядок з літерою A.
  10. f(A) повертає A — base case.
  11. f(CD) повертає пустий рядок — base case.

Runtime complexity

Складність рекурсивних алгоритмів важче рахувати, бо тут немає звичних циклів, за якими проводиш розрахунок. Складність цього алгоритму буде O(n * n) через те, що ми проходимо увесь інпут та копіюємо рядки для кожного рекурсивного колу.

Переваги

Немає. Але допомагає краще розібратись з рекурсивними алгоритмами.

Недоліки

Дуже повільний. В тестах використовуватись не буде.

Source

Другий рекурсивний алгоритм. Модифікація першого.

Цей алгоритм є модифікацією першого рекурсивного. Я додав до алгоритму memoization для вхідних рядків розміром менше або рівним 8 байт. Memoization — це оптимізаційний підхід, коли алгоритм зберігає результат для певного інпуту.

В нашому випадку ми будемо зберігати результат алгоритму для інпуту розміром 8 та менше байт. Рядок з 8 символів може створювати 65,536 різних комбінацій.Таким чином ми можемо ще мінімізувати витрати на рахування хешу рядка, котрий може ніколи не трапитись.

Послідовність викликів

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

  1. f(ABA...AB) ділить навпіл, викликає функцію для лівої половини, а потім для правої та з’єднує. В цьому випадку поверне пустий рядок.
  2. f(ABABABAB) ділить навпіл, викликає функцію для лівої половини, а потім для правої та з’єднує. В цьому випадку поверне пустий рядок. Зберігає результат для цього інпуту.
  3. f(ABAB) ділить навпіл, викликає функцію для лівої половини, для правої та з’єднує. В цьому випадку повертає пустий рядок та зберігає результат.
  4. f(AB) повертає пустий рядок — base case.
  5. f(AB) те саме, що і 4.
  6. f(ABAB) в цьому випадку функція відпрацює так само як і в base case. Поверне збережний результат — пустий рядок. Особливість в тому, що наступний поділ та виклик функції для інших половин не буде відбуватись взагалі.
  7. Виклик не відбувається.
  8. Виклик не відбувається.
  9. f(ABABABAB) відправить збережений результат — пустий рядок. Інші виклики не відбуваються взагалі.
  10. Виклик не відбувається.
  11. Виклик не відбувається.
  12. Виклик не відбувається.
  13. Виклик не відбувається.
  14. Виклик не відбувається.

Runtime complexity

Це порахувати стає ще складніше. На рандомізованому рядку подібних збігів буде не дуже багато. Тільки якщо розмір інпуту не збільшиться значно. І навіть в цьому випадку на великому інпуті оптимізація спрацює лише на трьох найнижчих рівнях.

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

Переваги

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

Недоліки

Повільний. В тестах використовуватись не буде.

Source

Третій рекурсивний алгоритм

Якщо попередній алгоритм може працювати O(n * logn) у найкращому випадку, то чому ми не можемо зняти обмеження у 8 байт для memoization? Можемо зняти та цей алгоритм буде працювати O(n * logn) у найкращому випадку незалежно від довжини рядка. Але варто зауважити, що якщо ми не маємо обмежень на довжину рядку, алгоритм буде деградувати до O(n * n * n) через копіювання, прохід по всьому інпуту та вирішення колізій у хеш мапі. І на дійсно великому інпуті (та особливо рандомному) memoization буде проблемою ніж оптимізацією.

Переваги

Ніяких. Реально. Лише як навчальний приклад

Недоліки

  • Повільний.
  • Працює швидше ніж попередній алгоритм ЛИШЕ у випадку інпуту, котрий складається з якихось повторюваних простих комбінацій.
  • Якщо інпут хоч трохи рандомізований, деградує у O(n * n * n) на великих даних.

Source

Рекурсивні алгоритми in place

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

Перший рекурсивний алгоритм in place

Рекурсивний алгоритм in place приймає посилання на інпут та індекси, які позначають проміжок, в якому потрібно працювати. Повертає рекурсивний алгоритм in place так само індекси. Але ті вже можуть бути іншими, в залежності від того, як саме змінився інпут. Цей алгоритм складається з декількох частин:

  • base case — якщо проміжок складає 2 та менше.
  • Якщо елементи в тому проміжку складають комбінацію, котру потрібно видалити, замінюємо значення елементів на х або будь-який інший маркер та повертаємо { first, first }. Таким чином ми будемо знати, що для такого інпуту функція повертає пустий рядок.
  • Якщо нема комбінації, просто повертаємо { first, last }, вхідний рядок залишився без змін.
  • Знаходимо середній індекс та викликаємо функцію для лівої половини та правої.
  • «З’єднуємо» результати обох викликів. Для цього ми просто в циклі звужуємо два ренджи, ставимо маркери там, де були знайдені комбінації, допоки ці комбінації є.
  • Копіюємо результат з правої половини до лівої, якщо ліва взагалі змінилась якось.
  • Ставимо маркери від останнього скопійованого елемента до індексу last.
  • Повертаємо новий рендж, дійсний.

Runtime complexity

O(n) незалежно від інпуту

Переваги

  • Швидший ніж всі попередні рекурсивні алгоритми.
  • Може бути оптимізований.

Недоліки

  • Складніший ніж ітеративний алгоритм.
  • Повільніший ніж ітеративний алгоритм.

Source

Другий рекурсивний алгоритм in place

Це є модифікація першого рекурсивного алгоритму in place. До нього так само доданий memoization на рядок у 8 байт. Таким чином трошки змінюється base case. Тепер ми не просто повертаємо пустий рендж, а і копіюємо результат з збережених даних до вхідного рядка.

Runtime complexity

Runtime complexity цього алгоритму залежить саме від контенту. У випадку рандомних даних та даних типу AAAAAAAA + BBBBBBBB complexity буде на рівні із ітеративним алгоритмом — O(n). Це буде підтверджено на тестах, результати котрих є в кінці. У випадку найкращих даних типу ABABABAB... цей алгоритм відпрацьовує швидше ніж ітеративний. Але можу з упевненістю сказати, що на великих даних цей алгоритм не буде мати O(logn) complexity, тому що як ми бачили розгалуження перестають працювати лише на нижчих трьох рівнях із memoization рівному 8 байт.

Переваги

  • Може працювати швидше за ітеративний алгоритм на певному інпуті (рандомізованому аж до 40 %).
  • Може бути оптимізований згідно інпуту.

Недоліки

  • В певних випадках може бути повільнішим за ітеративний алгоритм.
  • Складніший ніж ітеративний алгоритм.

Source

Третій рекурсивний алгоритм in place

Відрізняється від другого лише тим, що не має обмежень на інпут для memoization оптимізації.

Runtime complexity

Так само як і третій звичайний рекурсивний алгоритм на великих, хоч і трохи рандомних даних, цей алгоритм дуже сильно деградує performance-wise. Єдиний випадок, де він працює дуже швидко, — це на ДУЖЕ однорідному інпуті ABABABAB чи AAAAAAA...

Переваги

Дуже швидкий на однорідному інпуті.

Недоліки

● Дуже швидкий ЛИШЕ на однорідному інпуті.

● Дуже повільний, якщо інпут хоч трохи рандомізований.

Source

Порівняння

Для порівняння алгоритмів я використовував декілька різних інпутів розміром від 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. Як виходить із назви, один ітератор використовуємо для того, щоб вставляти літери, котрі були перевірені, другий — для того, щоб перевіряти, чи не буде тут комбінації, котру потрібно буде видалити.

Source

Результати

Якщо дуже коротко, то цей алгоритм відпрацьовує найшвидше в усіх випадках, крім одного — де не потрібно видаляти ніякі символи. Лише в цьому кейсі рекурсивний алгоритм відпрацьовує швидше. Думаю, що це відбувається від того, як саме імплементований рекурсивний алгоритм. Припускаю, що перформанс дроп у рекурсивних алгоритмів навіть на 10 % рандомізованому інпуті відбувається через те, як копіюються вже відомі результати. Очікую, що можна отримати кращі результати, якщо копіювати вже прораховані результати цілим ренджем. Отже графіки.

Random data

10% random data

Worst case data

Best case data

👍ПодобаєтьсяСподобалось5
До обраногоВ обраному6
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Тобто я не каже, що рекурсія то погано, але з ії імплементацією треба бути набагато уважнішим, чим робити через цикли.

Рекурсія то стрьомно, бо по перше не до кінця зрозуміло як компілер буде її оптимізувати, а по друге є правило по перевірці глибини рекурсіїї.
Бо якщо не перевіряти, то воно наче все працює, але от хтось задасть специфічні данні і стеку кришу зірве (як приклад можете загуглити про проблеми з std::regex under Linux (gcc)).

Ті дві речі можна вирішити заздалегідь. І тоді це вже не так стрьомно :)

Але, імхо, специфічні дані та будь-якого роду едж кейси та ліміти потрібно перевіряти незалежно від того, який у вас алгоритм.

Коментар порушує правила спільноти і видалений модераторами.

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

Взагалі, рекурсивний алгоритм може працювати однаковий час (якщо рекурсія хвостова, то CALL заміниться на JMP). В іншому випадку ніхно не заважає будувати стек викликів руками, можливо з якимов власним алокатором, який пає поведінку аналогічну стеку задачі (той же самий alloca або навіть mmap).

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

Таким чином, рекурсивного коду меньше, він розробляється швидше, він простіший та більш читабельний. Максимум нам інколи треба змінити розмір стеку за замовчуванням, щоб не ловити stack overflow. Але не завжди оптимальний. Як це часто трапляється у житті.

Так, погоджуюсь. Мемоїзація не є унікальним атрибутом рекурсивних алгоритмів.
Імхо, унікальним атрибутом саме рекурсивних алгоритмів є можливість розділити проблему на підпроблему. В деяких випадках то може допомогти написати більш оптимальний алгоритм. ДП проблеми легше почати вирішувати з рекурсивного алгоритму, а потім просто приходити до ітеративного із масивом чи ще чимось, що зберігає проміжні результати, якщо є така можливість.

Уже в формулировании условия задачи огромная дыра. Нет условия сберечь максимальное количество символов. Т.е. АВВВВВВВВВВВВ -> А.
Что ж, ок.
Если не заботимся об оптимальном решении, то в простейшем случае решения в лоб на с++ при итеративном методе инмемори это 2 указателя. Первый — указатель на предпоследний символ в уже почищенной строке (вначале указывает на начало исходной строки) , второй — движение по строке в конец (указывает на начало непочищенной правой части, в начале указывает на смещение 2). По первому указателю switch по *(int16*)p1 (проверяемые сочетания все 2х байтные). Не нашли — инкремент 1го указателя, нашли — копируем символ *(p1+1)=*(p2++). Зиро терминейтед стринг — последний 0 тоже копируется, указывая на конец сформированной строки. Завершение при *(p2) == 0.
O(n), никаких строковых операций сравнения, память требуется аж под два указателя.

Уже в формулировании условия задачи огромная дыра. Нет условия сберечь максимальное количество символов. Т.е. АВВВВВВВВВВВВ -> А.

Ця умова не потрібна, тому що є

видаляє всі комбінації AB, BA, CD, DC;

Якщо функція поверне A для АВВВВВВВВВВВВ, то вона працює неправильно.

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

У вашому підході мапа запам’ятованих значень зберігається між запусками алгоритма? Можливо, я не розумію, що таке повторювані вхідні дані.

Ничего нигде не сохраняется. Вместо исходной строки по тому же адресу появляется очищенная при определённой трактовке условия в свою пользу по принципу разрешено всё, что не запрещено. Полностью стейтлес.
Если под повторяющимися понимаем некий патерн, который повторяется n раз в строке, либо в строках подаваемых на вход, то опять таки не будет быстрее. Даже само по себе вычисление хеша съест больше, чем описанное решение в один проход

Можно удалить А и результирующая строка BBBBBBBBBBBB отвечает условию задачи. Но почему А это неправильный ответ я не понял. В условии просят избавиться от AB. Строка А построена на базе исходной путём удаления из неё лишних символов. Всё честно

#include <iostream>

int16_t constexpr ch2case(char c1, char c2)
{
    return (c2 << 8) | c1;
}

char *clean1(char *str)
{
    if (!*str || !str[1]) return str;
    char *p1 = str, *p2 = str+2;
    do{
        switch(*((int16_t *)p1))
        {
            case ch2case('A', 'B'):
            case ch2case('B', 'A'): 
            case ch2case('C', 'D'): 
            case ch2case('D', 'C'): 
            break;    
            default: 
            p1++;
            break;
        }
        p1[1] = *p2;
    }while(*(p2++));
    return str;
}


int main(int argc, char *argv[])
{
	char str1[] = "ABBBBBBBBBBBB";
	std::cout << str1 << " -> " << clean1(str1) << std::endl;
	char str2[] = "ABCDABBACD";
	std::cout << str2 << " -> " << clean1(str2) << std::endl;
}

Код вроде нормально выложился, похоже только include iostream подпортило.
С мобильного пишу, если что

Результат:
ABBBBBBBBBBBB -> A
ABCDABBACD -> ACAAC

Вариант простого удаления пар тоже можно сделать по аналогии, удаляя не последний символ, а всю пару. Т.к. на «стыках» опять возможно возникновение пары, то по идее p1 нужно декрементить после удаления, кроме случая начальной позиции. Удаления по существу не будет, как и в предыдущем случае. Просто копирование следующего символа из р2.
Опять таки O(n) и дешёвые операции на каждом цикле.
Кода будет почти столько же

#include <iostream>

int16_t constexpr ch2case(char c1, char c2)
{
    return (c2 << 8) | c1;
}

char *clean1(char *str)
{
    if (!*str || !str[1]) return str;
    char *p1 = str, *p2 = str+2;
    do{
        switch(*((int16_t *)p1))
        {
            case ch2case('A', 'B'):
            case ch2case('B', 'A'): 
            case ch2case('C', 'D'): 
            case ch2case('D', 'C'): 
            if (p1 != str) p1--;
            else {
                 *p1 = *p2;
                  if (*p2) p2++;
            }
            break;    
            default: 
            p1++;
            break;
        }
        p1[1] = *p2;
    }while(*(p2++));
    return str;
}


int main(int argc, char *argv[])
{
	char str1[] = "ABBBBBBBBBBBB";
	std::cout << str1 << " -> " << clean1(str1) << std::endl;
	char str2[] = "ABCDABBACD";
	std::cout << str2 << " -> " << clean1(str2) << std::endl;
}

Тогда результат
ABBBBBBBBBBBB -> BBBBBBBBBBB
ABCDABBACD ->

Опять таки я срезаю углы, отдавая приоритет удалению свежесозданных пар в зоне склейки, а не более «старым» парам из правой части. Ну, вроде запрета не было.

Результат:
ABBBBBBBBBBBB -> A

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

В общем, в случаях, когда у нас есть возможность решить задачу в один проход по строке коротким окном и на каждый символ совершать считанные простые операции, рекурсивный метод очень вряд ли может быть быстрее. Вам нужно, грубо говоря, за счёт более оптимальной обработки компенсировать затраты на работу со стеком и ещё что-то выиграть. Затраты на стек это, как минимум, копирование адреса, куда вернуться, и переменных.

Може у Вас також є досвід визначення типу / формату данних для реальних прод проектів? Адеж вибрати правильний алгоритм можна лише виходячи з данних, і не завжди вони є і зрозумілі на час написання продукту

Нажаль такого досвіду не маю.
Але саме формат даних ви повинні знати заздалегідь, якщо плануєте працювати із ними. Характер даних, якщо не може бути з’ясований заздалегідь, можна вирахувати, якщо є статистика по тим даним. Впевнений, що data analyst зможе порахувати то без проблем.

Стаття про те, як знаючи особливість даних можна підібрати алгоритми їх обробки. Алн доволі часто, коли створюється система, у нас немає ще зібраних даних і ми не можемо їх проаналізувати заздалегідь

Підписатись на коментарі