Пещерата на програмиста Опитът да не се повтаря

Опитът за избягване на рекурсия

В Интернет темата за отхвърляне на рекурсия в алгоритмите практически не е засегната. Има много статии и книги, които обясняват какво е рекурсия, как да я използвате. Но ето как да се отървете от него - почти нищо.

Така че рекурсията е функция, която извиква сама себе си. Всеки знае алгоритъма за изчисляване на факториел, класика на книгите. Всичко е красиво и елегантно, въпреки че цикълът изглежда по-прост. И всякакви алгоритми за парсване на низ и работа с регулярни изрази. Изглежда, използвайте и се радвайте. Но не всичко е толкова просто. Дълбочината на рекурсия (колко пъти една функция може да се извика сама) е ограничена. Ограничен от размера на стека. Факт е, че преди да извикате самата функция, трябва да запазите стойностите на всички локални променливи, така че да могат да се използват след връщане. И всичко това се съхранява в стека. И докато има място в стека, можем да се задълбочим в рекурсията. По-дълбоко, по-дълбоко. Докато не изскочи грешка - Stack overflow. И това е всичко, загасете светлината. Стандартният размер на стека е около 2 MB (за Windows програми). Така че нека увеличим размера на стека с опции на компилатора, това е смисълът. И колко да се увеличи, за да не е много и да не е малко? и ако заявките растат с течение на времето, постоянно прекомпилиране? И ако имате библиотека, която използва стека на програмата, която я е извикала? И тук разбирате, че това не е нашият метод. Необходимо е по някакъв начин да се отървем от рекурсията. Това е, което срещнах в библиотеката Colorer, която поддържам. Алгоритъмът за анализиране на низ с помощта на регулярен израз беше рекурсивен. Освен това беше красиво и миришеше. Но той обичаше да пада на дълги линии. Дайте низ от 3000 символа и това е, пристигнахме. Трябваше да се направи нещо. Единственият начин, който открих за премахване на рекурсията, е да се отърва от опашкатарекурсия. Същността му е следната - ако рекурсивното извикване е последно във функцията, тогава функцията може да бъде заменена с цикъл. Факториелът е само пример за това. Но имах много рекурсивни извиквания във функцията. Част може да бъде разширена в цикъл, но това е много малка част. И между другото, кодът е създаден по такъв начин, че в зависимост от резултата от извикването (функцията върна bool стойност), функцията може да завърши или да продължи да работи по-нататък. И самата функция беше цикъл, вътре в който се превключва. Тук идва единственото останало решение - защо не репликираме рекурсивното извикване с цикъл и не запазим параметри? тези. направете всичко вместо компилатора. Какво ни трябва за това:

  1. списък с локални променливи за запазване.
  2. динамичен списък от типа стек, в който ще запазим стойностите на локалните променливи и ще ги извлечем от там
  3. действия след рекурсия или действие (не знам как да го нарека по-добре)
  4. цикъл
Да започнем с действието. Всяко рекурсивно извикване, в зависимост от резултата, доведе до връщане на true, или връщане на false, или връщане на function_result, или продължение на функцията с много редове код. защото се отървем от рекурсията в полза на цикъл, тогава този код трябва да се изпълни след края на цикъла за това извикване на рекурсия. Тези. когато цикълът дойде да се върне. Затова избираме всички подобни ситуации в един превключвател, като им задаваме собствен код за действие.

Създаваме функция, която записва локални променливи и задава нови на тяхно място (ако има параметри при извикване на рекурсия). Как да ги спасим е друга история. Имах няколко от тях и ги минах по справка. В допълнение към променливите, трябва да запишете действието (действието), което трябва да се извърши в зависимост от резултата от функцията.Тази функция замества извикването на рекурсия за нас - запазваме текущите стойности, заместваме ги с нови. След като запазим, трябва да се върнем в началото на цикъла, сякаш току-що сме въвели функцията. След това създаваме функция за проверка на нашия стек за записи и извличането им от него. Ще ни трябва, за да заменим редовете returnsomething_there. Предаваме тованещо_тамв него. И ако стекът е празен, връщаме action =something_there, в противен случай изваждаме данните от стека, актуализираме локалните променливи и връщаме действието в зависимост отsomething_there.Изпълняваме кода за това действие.Е, тогава комбинираме всичко това в един цикъл и работим.

Като цяло описанието се оказа много хаотично, неясно. Но е трудно за обяснение. По-лесно е да покажете резултата. Функцията CRegExp::lowParse беше коригирана. Преди промените файловете бяха следните cregexp.cpp, cregexp.h. След прилагане на този метод cregexp.cpp, cregexp.h .

По време на тестовете беше потвърдена стабилна работа на дълги линии. Кодът работи правилно. Но скоростта падна малко. На тестовите файлове скоростта на работа спадна с 1 секунда (на моя компютър). След анализ в профайлъра се оказа, че тясното място е работа с памет в нашия стек. Оптимизираната версия е показана по-горе като окончателна. При него спадът на скоростта вече е около 0,4 секунди. Но това вече не може да се поправи. Но ние не падаме по рекурсия.

Тази корекция ще бъде приложена в новата версия на FarColorer. И проблемът, коригиран в много доклади за грешки, най-накрая ще изчезне.