Najszybsza ucieczka od rekursji w Javie

Question

Czy istnieje sposób na łatwe i szybkie wyjście z rekursji w Javie? Istnieje sposób na wyrwanie się z for loop za pomocą instrukcji break;. Czy istnieje równoważny wzorzec lub metoda unikania rekursji?

Mogę myśleć o stworzeniu osobnego wątku, a po obliczeniu wartości, po prostu zabijanie wątku zamiast bulgotania stosu rekursji. Czy istnieje lepszy sposób?

Istnieje już pytanie, które omawia, w jaki sposób można wykluczyć rekurencję: here.

To, czego szukam, to szybsza metoda osiągnięcia tego celu, prawdopodobnie bez przechodzenia przez stos. Coś takiego jak instrukcja goto lub instrukcja .

kryteriami branymi pod uwagę są tu:

• Łatwość refaktoringu używać tej ucieczki
• Smoły wydajność (im szybciej tym lepiej)
• Długość w praktyce (szybciej pisać/add tym lepiej)

Odpowiedź, której szukam, wyjaśni zarówno wydajność, jak i prostotę rozwiązania - jest to zadawane w kontekście konkurencji algorytmicznej, więc rozwiązanie Wymagane są ns, które wymagają mniejszej liczby refaktoryzacji.

Dlaczego miałbym go używać?

Czasami podczas kodowania niektórych konkurencji algorytmicznej, musisz zwrócić wartość z wewnątrz rekursji i zastanawiam się, czy możesz to zrobić szybciej, używając tego rodzaju przerwy. Pomyśl o algorytm, który wygląda następująco:

public static MyClass myFunct(MyClass c, int x){ 
    myFunct(c, c.valueA); 
    myFunct(c, c.valueB); 
    //do some work - that modifies class c 
    if(c.valueE == 7){ 
     //finished work, can return without unwinding the whole recursion 
     //No more modifications to class c 
    } 
    myFunct(c, c.valueC); 
    myFunct(c, c.valueD); 
    return c; 
} 

Answer 1

Odpowiedź na to pytanie jest dość prosta:

prostu zrób to zwykły sposób, czyli odwracanie stosie się z return s. Czemu? Ponieważ nie jest to tak powolne, jak mogłoby się wydawać. O ile obliczenia w rekurencji nie są bardzo trywialne, a głębokość stosu jest bardzo wysoka, to powrót nigdy nie wpłynie znacząco na działanie twojego algorytmu.

Zasadniczo masz następujące opcje:

• jeśli to możliwe, przekształcić swój algorytm iteracyjny jeden.
• Przekształć algorytm tak, aby zakończył się rekursywnie i mam nadzieję, że maszyna wirtualna ponownie użyje ramki stosu. Następnie powrót z rekursji jest praktycznie równy jednemu prostemu powrotowi.
• Zgłaszanie wyjątków. Będzie to jednak wolniejsze niż powracanie, ponieważ należy zbudować ślad stosu, który również przechodzi przez stos. Również stos musi zostać rozwinięty, aby sprawdzić, czy jest on objęty catch. Nic nie wygrywasz.

Poprzednie dwie opcje są opłacalne, ale nie zawsze są możliwe. Ale szczerze mówiąc, nie myśl o tym. Powrót z głębokiego stosu nie jest tą czynnością, która powoduje spowolnienie twojego algorytmu. Jeśli masz algorytm z bardzo głęboką rekurencją, to i tak masz problem (przepełnienie stosu, koszty wywołań rekursywnych) i powinieneś rozważyć przepisanie swojego algorytmu. Jeśli głębokość stosu jest niska, to i tak nie jest to problem.

Oto prosty program testowy Java, aby pokazać, co mam na myśli:

import java.io.ByteArrayOutputStream; 
import java.io.PrintStream; 

public class DeepRecursion { 

    private long returnStartTime; 

    public int recurse(int i) { 
     int r = (int)Math.sqrt((double)i); // Some non-trivial computation 
     if(i == 0) { 
      returnStartTime = System.currentTimeMillis(); 
      return r; 
     } 
     return r + recurse(i-1); 
    } 

    public void testRecursion(int i, PrintStream p) { 
     long startTime = System.currentTimeMillis(); 
     int result = recurse(i); 
     long endTime = System.currentTimeMillis(); 

     p.println(
       "Recursion depth: " + i + " Result: " + result + "\n" + 
       "Time for recursion" + (returnStartTime - startTime) + "\n" + 
       "Time for return " + (endTime - returnStartTime) + "\n" 
       ); 
    } 

    public void testIteration(int i, PrintStream p) { 
     long startTime = System.currentTimeMillis(); 
     int result = 0; 
     for(int k = 0; k <= i; k++) { 
      int r = (int)Math.sqrt((double)k); // Some non-trivial computation 
      result += r; 
     } 
     long endTime = System.currentTimeMillis(); 
     p.println("Iteration length: " + i + " Result: " + result + "\nTime: " + (endTime - startTime)); 
    } 

    public static void main(String[] args) { 
     DeepRecursion r = new DeepRecursion(); 
     PrintStream nullStream = new PrintStream(new ByteArrayOutputStream()); 

     for(int k = 0; k < 10; k++) { 
      // Test stack depths from 1024 to 33554432 
      for(int i = 10; i < 26; i++) { 
       r.testIteration(1 << i, k == 9 ? System.out : nullStream); 
       r.testRecursion(1 << i, k == 9 ? System.out : nullStream); 
      } 
     } 
    } 
} 

Oblicza rekurencyjną funkcję, która będzie mieć głębokość stosu równą parametru wejściowego. Funkcja oblicza pierwiastek kwadratowy w każdym układzie stosu, aby zasymulować pewne nietrywialne obliczenia.Oblicza również tę samą funkcję w sposób iteracyjny. Aby ogrzać JIT, program jest najpierw wykonywany 9 razy bez drukowania wyniku; drukowany jest tylko dziesiąty wynik. Oto moje wyniki (musiałem zwiększyć rozmiar stosu do 1 gigabajta z -Xss1g Oto wyniki z mojego komputera.

Iteration length: 1024 Result: 21360 
Time for iteration: 0 
Recursion depth: 1024 Result: 21360 
Time for recursion 0 
Time for return 0 

Iteration length: 2048 Result: 60810 
Time for iteration: 0 
Recursion depth: 2048 Result: 60810 
Time for recursion 0 
Time for return 0 

Iteration length: 4096 Result: 172768 
Time for iteration: 0 
Recursion depth: 4096 Result: 172768 
Time for recursion 0 
Time for return 0 

Iteration length: 8192 Result: 490305 
Time for iteration: 0 
Recursion depth: 8192 Result: 490305 
Time for recursion 0 
Time for return 0 

Iteration length: 16384 Result: 1390016 
Time for iteration: 0 
Recursion depth: 16384 Result: 1390016 
Time for recursion 0 
Time for return 0 

Iteration length: 32768 Result: 3938198 
Time for iteration: 0 
Recursion depth: 32768 Result: 3938198 
Time for recursion 0 
Time for return 0 

Iteration length: 65536 Result: 11152256 
Time for iteration: 0 
Recursion depth: 65536 Result: 11152256 
Time for recursion 1 
Time for return 0 

Iteration length: 131072 Result: 31570201 
Time for iteration: 0 
Recursion depth: 131072 Result: 31570201 
Time for recursion 1 
Time for return 0 

Iteration length: 262144 Result: 89347840 
Time for iteration: 2 
Recursion depth: 262144 Result: 89347840 
Time for recursion 1 
Time for return 1 

Iteration length: 524288 Result: 252821886 
Time for iteration: 2 
Recursion depth: 524288 Result: 252821886 
Time for recursion 4 
Time for return 1 

Iteration length: 1048576 Result: 715304448 
Time for iteration: 5 
Recursion depth: 1048576 Result: 715304448 
Time for recursion 7 
Time for return 3 

Iteration length: 2097152 Result: 2023619820 
Time for iteration: 9 
Recursion depth: 2097152 Result: 2023619820 
Time for recursion 14 
Time for return 4 

Iteration length: 4194304 Result: 1429560320 
Time for iteration: 18 
Recursion depth: 4194304 Result: 1429560320 
Time for recursion 29 
Time for return 12 

Iteration length: 8388608 Result: -986724456 
Time for iteration: 36 
Recursion depth: 8388608 Result: -986724456 
Time for recursion 56 
Time for return 28 

Iteration length: 16777216 Result: -1440040960 
Time for iteration: 72 
Recursion depth: 16777216 Result: -1440040960 
Time for recursion 112 
Time for return 61 

Iteration length: 33554432 Result: 712898096 
Time for iteration: 145 
Recursion depth: 33554432 Result: 712898096 
Time for recursion 223 
Time for return 123 

Jak widać, trwa 3 milisekundy do powrotu ze stosu głębokości jednego miliona Większe rozmiary stosu powodują dłuższe czasy, prawdopodobnie z powodu braku dopasowania stosu do pamięci podręcznej L3.Jednakże, jeśli potrzebujesz tak dużych stosów, i tak masz problem, jak opisano powyżej. Uruchomienie Javy z maksymalnym rozmiarem stosu 1 gigabajta nie jest Najlepszym pomysłem jest, aby każdy stack o wielkości poniżej 131072 nie był nawet mierzalny w milisekundach W rozsądnym algorytmie stos powinien być znacznie mniejszy, więc zawsze powinieneś być w porządku

Jak widać, najszybszy rozwiązanie jest iteracyjne, więc jeśli bardzo głęboka rekursja jest zbyt wolna, unikaj jej całkowicie, zamiast tylko pomijać powrót.

Wnioski

Jeśli rekurencja jest zbyt powolne dla ciebie, pozbyć się go całkowicie. Pominięcie zwrotu nie zrobi dużej różnicy.

Answer 2

Ogólnie najprostsze podejście do tego problemu byłoby po prostu zastąpić rekursji z non-rekurencyjne rozwiązania. To również najprawdopodobniej poprawi wydajność, jeśli zostanie właściwie wdrożone. Podejście polegające na zabijaniu wątku jest dość brzydkie - zdecydowanie nie polecam tego. Ale nie ma sposobu na wyrwanie rekursji bez przewijania stosu.

Recursion:

int rec(int i){ 
    if(i == condition) 
     return i; 

    //do some stuff with i 

    return rec(i); 
} 

nierekursywnych:

int nonrec(int i){ 
    Stack<Integer> stack = new Stack<>(); 
    stack.push(i); 

    while(!stack.isEmpty()) 
    { 
     Integer v = stack.pop(); 

     //same as above, but no bubbling through the stack 
     if(v == condition) 
      return v; 

     //do some stuff with v 

     stack.push(v); 
    } 

    //undefined, the algorithm hasn't found a solution 
    return -1; 
} 

Jest to dość prosty przykład, ale zasada jest taka sama dla bardziej złożonych problemów rekurencyjnych.

Answer 3

Powiedzmy, że masz jakąś wewnętrzną, powtarzającego rekursji, jak ten kod nie tak jawnego:

public A f(B b) { 
    C c = new C(); 
    return recf(b, c); 
} 

private A recf(B b, C c) { 
    ... 
    A a = recf(b2, c2); 
    if (a != null) { // found 
     return a; 
    } 
    ... 
    return recf(b3, c3); 
} 

To przyniesie sekwencji zwrotów kiedy znaleziono (a != null).

Analogicznie do break jest Throwable.

public A f(B b) { 
    C c = new C(); 
    try (
     recf(b, c); 
     return null; // not found 
    } catch (ResultFoundException<A> e) { 
     return e.getResult(); 
    } 
} 

private void recf(B b, C c) throws ResultFoundException<A> { 
    ... 
} 

public class ResultFoundException<A> implements RuntimeException { 
    ... 

    /** Speed-up thanks to James_pic. */ 
    @Override 
    public Throwable fillInStackTrace() { } 
} 

Answer 4

Jeśli zmienisz algorytm, aby utrzymać swój własny stos zamiast używać stosu procesora systemu można po prostu wyrzucić stos.

Answer 5

Jak zostało wskazane przez inne osoby, stos musi zostać zwinięty.

Posiadanie kolejnego wątku jest brzydkie i prawdopodobnie wolniejsze niż odrzucanie wyjątku.

Chciałbym znaleźć podejście nierekurencyjne lub wykonać normalną rekursję z odpowiednimi zwrotami. Może, jeśli podasz przykład tego, co próbujesz zrobić, ludzie mogą wskazać ci właściwy kierunek.

Gdybym musiał to zrobić rozpaczliwie, potrzebowałbym metody przechwytywania, która wychwyci wyjątek wyrzucony przez funkcję rekursywną.

Zastrzeżenie: Nie próbowałem tego więc nie może nawet skompilować :)

class GotAResultException extends Exception { 
    private Object theResult; 
    public GotAResultException(Object theResult) { 
    this.theResult = theResult; 
    } 
    public Object getResult() { 
    return theResult; 
    } 
} 

Object wrapperMethod(Object blaParameters) { 
    try { 
    recursiveMethod(blaParameters); 
    } catch (GotAResultException e) { 
    return e.getResult(); 
    } 
    // maybe return null if no exception was thrown? 
    // Your call 
    return null; 
} 

void recursiveMethod(Object blaParameters) throws GotAResultException { 
    // lots of magical code 
    // that calls recursiveMethod recursivelly 
    // ... 
    // And then we found the solution! 
    throw new GotAResultException("this is the result"); 
} 

Answer 6

Szeroko dobrze przyjęte design - nawet może to zależeć od konkretnych okoliczności - jest za pomocą Java Future <T> (lub podobny). Jeśli zamierzasz używać wątków, pamiętaj, że anulowanie wątku wymaga bezpiecznej i czystej polityki. Istnieje bardzo dobra literatura na te tematy, np. Współbieżność Java w praktyce.

Answer 7

Jedną z opcji jest, aby ustawić flagę na MyClass i zwrot w oparciu o które:

public static MyClass myFunct(MyClass c, int x){ 
    if (c.isDoneCalculating) { 
     return c; 
    } 
    myFunct(c, c.valueA); 
    myFunct(c, c.valueB); 
    //do some work - that modifies class c 
    if(c.valueE == 7){ 
     c.isDoneCalculating = true; 
     //finished work, can return without unwinding the whole recursion 
     //No more modifications to class c 
    } 
    myFunct(c, c.valueC); 
    myFunct(c, c.valueD); 
    return c; 
}