Pytanie
Jakie są możliwe sposoby rozwiązania problemu przepełnienia stosu spowodowanego przez algorytm rekurencyjny?
Przykład
Próbuję rozwiązać problem Project Euler 14 i postanowiłem spróbować z algorytmem rekurencyjnym. Jednak program zatrzymuje się z java.lang.StackOverflowError. Zrozumiały. Algorytm rzeczywiście przepełnił stos, ponieważ próbowałem wygenerować sekwencję Collatz dla bardzo dużej liczby.
Rozwiązania
Zastanawiałem się więc: jakie są standardowe sposoby rozwiązania problemu przepełnienia stosu, zakładając, że algorytm rekurencyjny został napisany poprawnie i zawsze kończy się przepełnieniem stosu? Dwie koncepcje, które przyszły mi do głowy:
- rekurencja ogona
- iteracja
Czy pomysły (1) i (2) są prawidłowe? Czy są inne opcje?
Edytować
Pomoże to zobaczyć kod, najlepiej w Javie, C #, Groovy lub Scala.
Być może nie używaj wspomnianego powyżej problemu Project Euler, aby nie zepsuć się innym, ale weź inny algorytm. Może silnia lub coś podobnego.
źródło
Odpowiedzi:
Optymalizacja wywołania ogona jest obecna w wielu językach i kompilatorach. W tej sytuacji kompilator rozpoznaje funkcję formularza:
Tutaj język jest w stanie rozpoznać, że zwracany wynik jest wynikiem innej funkcji i zmienić wywołanie funkcji z nową ramką stosu na skok.
Zrozum, że klasyczna metoda czynnikowa:
nie jest optymalizowany na podstawie ogona z powodu koniecznej kontroli po powrocie. ( Przykładowy kod źródłowy i skompilowane dane wyjściowe )
Aby zoptymalizować to połączenie z ogonem,
Kompilowanie tego kodu za pomocą
gcc -O2 -S fact.c
(-O2 jest konieczne, aby umożliwić optymalizację w kompilatorze, ale przy większej optymalizacji -O3 trudno jest odczytać człowiekowi ...)( Przykładowy kod źródłowy i skompilowane dane wyjściowe )
Widać w segmencie
.L3
,jne
a nie wcall
(który wywołuje podprogram z nową ramką stosu).Należy pamiętać, że zostało to zrobione przy użyciu C. Optymalizacja wywołania Tail w Javie jest trudna i zależy od implementacji JVM (co powiedziawszy, nie widziałem tego, ponieważ to jest trudne i implikacje wymaganego modelu bezpieczeństwa Java wymagającego ramek stosu - czego unika całkowity koszt posiadania) - rekursja ogona + Java i rekursja ogona + optymalizacja to dobre zestawy znaczników do przeglądania. Można znaleźć inne języki JVM są w stanie optymalizować rekursji ogonowej lepiej (Clojure try (co wymaga ponownie wystąpi zadzwonić ogon Optimize) lub Scala).
To mówi,
Jest pewna radość, wiedząc, że napisałeś coś dobrze - w idealny sposób, aby to zrobić.
A teraz wezmę trochę szkockiej i założę niemiecką elektronikę ...
Do ogólnego pytania dotyczącego „metod unikania przepełnienia stosu w algorytmie rekurencyjnym” ...
Innym podejściem jest włączenie licznika rekurencji. Jest to bardziej przydatne do wykrywania nieskończonych pętli spowodowanych sytuacjami, na które nie ma się wpływu (i słabym kodowaniem).
Licznik rekurencji ma postać
Za każdym razem, gdy wykonujesz połączenie, zwiększasz licznik. Jeśli licznik staje się zbyt duży, popełniasz błąd (w tym przypadku jest to tylko zwrot -1, chociaż w innych językach możesz preferować wyjątek). Chodzi o to, aby zapobiec wystąpieniu gorszych rzeczy (błędów pamięci) podczas wykonywania rekurencji, która jest znacznie głębsza niż oczekiwano i prawdopodobnie nieskończonej pętli.
Teoretycznie nie powinieneś tego potrzebować. W praktyce widziałem źle napisany kod, który go dotknął z powodu mnóstwa drobnych błędów i złych praktyk kodowania (problemy z wielowątkową współbieżnością, w których coś zmienia coś poza metodą, która powoduje, że kolejny wątek przechodzi w nieskończoną pętlę wywołań rekurencyjnych).
Użyj właściwego algorytmu i rozwiąż właściwy problem. Wydaje się, że specjalnie dla Collatz Conjecture próbujesz rozwiązać to w sposób xkcd :
Zaczynasz od liczby i przechodzisz przez drzewo. To szybko prowadzi do bardzo dużej przestrzeni wyszukiwania. Szybki bieg w celu obliczenia liczby iteracji dla poprawnej odpowiedzi daje około 500 kroków. Nie powinno to stanowić problemu w przypadku rekurencji z ramką o małym stosie.
Chociaż znajomość rozwiązania rekurencyjnego nie jest złą rzeczą, należy również zdać sobie sprawę, że wielokrotnie rozwiązanie iteracyjne jest lepsze . Wiele sposobów podejścia do konwertowania algorytmu rekurencyjnego na iteracyjny można znaleźć na stronie Przepełnienie stosu w Way, aby przejść od rekurencji do iteracji .
źródło
Należy pamiętać, że implementacja języka musi obsługiwać optymalizację rekurencji ogona. Nie sądzę, że robią to główne kompilatory Java.
Zapamiętywanie oznacza, że pamiętasz wynik obliczenia, a nie przeliczasz go za każdym razem, na przykład:
Gdy obliczasz każdą sekwencję mniejszą niż milion, na końcu sekwencji będzie dużo powtórzeń. Zapamiętywanie sprawia, że jest to szybkie wyszukiwanie tabeli skrótów dla poprzednich wartości zamiast konieczności zwiększania stosu.
źródło
Dziwi mnie, że nikt jeszcze nie wspomniał o trampolinie . Trampolina (w tym sensie) to pętla, która iteracyjnie wywołuje funkcje zwracania zagęszczeń (styl przekazywania kontynuacji) i może być używana do implementacji wywołań funkcji rekurencyjnych w języku programowania stosowego.
To pytanie StackOverflow zawiera nieco więcej szczegółów na temat różnych implementacji trampolinowania w Javie: Obsługa StackOverflow w Javie dla Trampoline
źródło
Jeśli używasz języka i kompilatora, który rozpoznaje funkcje rekurencyjne taila i odpowiednio je obsługuje (tj. „Zastępuje dzwoniącego na miejscu przez odbiorcę”), to tak, stos nie powinien wymknąć się spod kontroli. Ta optymalizacja zasadniczo redukuje metodę rekurencyjną do iteracyjnej. Nie sądzę, że Java to robi, ale wiem, że robi to Racket.
Jeśli wybierzesz podejście iteracyjne, a nie rekurencyjne, eliminujesz większość potrzeby pamiętania, skąd pochodzą połączenia, i praktycznie eliminujesz ryzyko przepełnienia stosu (w każdym razie połączeń rekurencyjnych).
Zapamiętywanie jest świetne i może zmniejszyć ogólną liczbę wywołań metod, sprawdzając wcześniej obliczone wyniki w pamięci podręcznej, biorąc pod uwagę, że ogólne obliczenia pociągną za sobą wiele mniejszych, powtarzanych obliczeń. Ten pomysł jest świetny - jest również niezależny od tego, czy używasz podejścia iteracyjnego, czy rekurencyjnego.
źródło
możesz utworzyć Wyliczenie, które zastąpi rekurencję ... oto przykład obliczania zdolności robienia tego ... (nie będzie działać dla dużych liczb, ponieważ użyłem tylko długo w przykładzie :-))
nawet jeśli nie jest to zapamiętywanie, w ten sposób unieważnisz przepełnienie stosu
EDYTOWAĆ
Przepraszam, jeśli zdenerwowałem niektórych z was. Moim jedynym zamiarem było pokazanie sposobu uniknięcia przepełnienia stosu. Prawdopodobnie powinienem był napisać pełny przykład kodu zamiast tylko małego fragmentu szybko napisanego i szorstkiego fragmentu kodu.
Poniższy kod
... umm ... jeśli go uruchomisz, upewnij się, że ustawiłeś okno powłoki poleceń tak, aby miało bufor 9999 linii ... zwykłe 300 nie wystarczy, aby przejść przez wyniki poniższego programu ...
Deklaruję * 1 zmienną statyczną „instancja” w klasie Wydziału do sklepu jako singleton. W ten sposób, dopóki twój program działa, za każdym razem, gdy „GetInstance ()” klasy otrzymujesz instancję, która zachowała wszystkie wartości już obliczone. * 1 static SortedList, która będzie przechowywać wszystkie wartości już obliczone
W konstruktorze dodaję również 2 wartości specjalne z listy 1 dla wejść 0 i 1.
źródło
Jeśli chodzi o Scalę, możesz dodać
@tailrec
adnotację do metody rekurencyjnej. W ten sposób kompilator zapewnia faktyczną optymalizację wywołania ogona:Więc to się nie skompiluje (silnia):
komunikat o błędzie to:
Z drugiej strony:
kompilacje i przeprowadzono optymalizację wywołania ogona.
źródło
Jedną z możliwości, o której jeszcze nie wspomniano, jest rekurencja, ale bez użycia stosu systemowego. Oczywiście możesz również przepełnić swoją stertę, ale jeśli twój algorytm naprawdę potrzebuje powrotu do poprzedniej wersji w takiej czy innej formie (po co w ogóle używać rekurencji?), Nie masz wyboru.
Istnieją implementacje niektórych języków bez stosów , np . Python bez stosów .
źródło
Innym rozwiązaniem byłoby symulowanie własnego stosu i nie poleganie na implementacji kompilatora + środowiska wykonawczego. To nie jest proste ani szybkie rozwiązanie, ale teoretycznie otrzymasz StackOverflow tylko wtedy, gdy brakuje Ci pamięci.
źródło