Optimizare ciudată de recursiune de către java

I came across some weird results when I was trying to answer this question: How to improve the performance of the recursive method?

Dar nu trebuie să citiți acel post. Voi da contextul relevant aici. Acest lucru poate părea lung, dar într-adevăr nu este atât de complicat dacă citiți o dată. Sper că va fi interesant pentru toți. Pentru context,

syra(n) = { 1 if n=1; 
            n + syra(n/2) if n is even; și 
            n + syra(3n+1) if n is odd
          }

și

syralen(n) = No. of steps to calculate syra (n)

e.g, syralen(1)=1, syralen(2)=2 since we need to go two steps. syra(10) = 10 + syra(5) = 15 + syra(16) = 31 + syra(8) = 39 + syra(4) = 43 + syra(2) = 45 + syra(1) = 46. So syra(10) needed 7 steps. Therefore syralen(10)=7

și finally,

lengths(n) = syralen(1)+syralen(2)+...+syralen(n)

The question poster there is trying to calculate lengths(n)

Întrebarea mea este despre soluția recursivă pe care Op a trimis-o (care este al doilea fragment din această întrebare). O voi reposta aici:

public class SyraLengths{

        int total=1;
        public int syraLength(long n) {
            if (n < 1)
                throw new IllegalArgumentException();
            if (n == 1) {
                int temp=total;
                total=1;
                return temp;
            }
            else if (n % 2 == 0) {
                total++;
                return syraLength(n/2);
            }
            else {
                total++;
                return syraLength(n * 3 + 1);
            }
        }

        public int lengths(int n){
            if(n<1){
                throw new IllegalArgumentException();
            }
            int total=0;
            for(int i=1;i<=n;i++){
                total+=syraLength(i);
            }

            return total;
        }

        public static void main(String[] args){
            System.out.println(new SyraLengths().lengths(5000000));
        }
       }

Surely an unusual (și probably not recommended) way of doing it recursively, but it does calculate the right thing, I have verified that. I tried to write a more usual recursive version of the same:

public class SyraSlow {

    public long lengths(int n) {
        long total = 0;
        for (int i = 1; i <= n; ++i) {
            total += syraLen(i);
        }
        return total;
    }

    private long syraLen(int i) {
        if (i == 1)
            return 1;
        return 1 + ((i % 2 == 0) ? syraLen(i/2) : syraLen(i * 3 + 1));
    }

Acum iată partea ciudată - am încercat să testez performanța ambelor versiuni de mai sus, cum ar fi:

public static void main(String[] args){
            long t1=0,t2=0;
            int TEST_VAL=50000;

            t1 = System.currentTimeMillis();
            System.out.println(new SyraLengths().lengths(TEST_VAL));
            t2 = System.currentTimeMillis();
            System.out.println("SyraLengths time taken: " + (t2-t1));

            t1 = System.currentTimeMillis();
            System.out.println(new SyraSlow().lengths(TEST_VAL));
            t2 = System.currentTimeMillis();
            System.out.println("SyraSlow time taken: " + (t2-t1));
        }

Pentru TEST_VAL = 50000 , rezultatul este:

5075114
SyraLengths time taken: 44
5075114
SyraSlow time taken: 31

As expected (I guess) the plain recursion is slightly better. But when I go one step further și use TEST_VAL=500000, the output is:

62634795
SyraLengths time taken: 378
Exception in thread "main" java.lang.StackOverflowError
    at SyraSlow.syraLen(SyraSlow.java:15)
    at SyraSlow.syraLen(SyraSlow.java:15)
    at SyraSlow.syraLen(SyraSlow.java:15)

Why is it? What kind of optimization is being done by Java here that the SyraLengths version doesn't hit StackOverflow (It works even at TEST_VAL=5000000)? I even tried using an accumulator-based recursive version just in case my JVM was doing some tail-call optimization:

private long syraLenAcc(int i, long acc) {
        if (i == 1) return acc;
    if(i%2==0) {
        return syraLenAcc(i/2,acc+1);
    }
    return syraLenAcc(i * 3 + 1, acc+1);
    }

But I still got the same result (thus there is no tail-call optimization here). So then, what's happening here?

P.S: Modificați-vă la un titlu mai bun dacă vă puteți gândi la orice.

0

2 răspunsuri

Se pare că există o explicație simplă:

I am using long syraLen(int n) as the method signature. But the value of n can actually be much larger than Integer.MAX_VALUE. So syraLen gets negative inputs and therein lies the problem. If I change it to long syraLen(long n), everything works perfectly! I wish I had also put the if(n < 1) throw new IllegalArgumentException(); like the original poster. Would have saved me some time.

0
adăugat

Cu versiunea originală, a fost posibilă optimizarea recursivității cozii (în cadrul JIT). Deși nu sa întâmplat de fapt sau nu, totuși. Dar este posibil ca versiunea originală să fie doar puțin mai eficientă cu folosirea stivei. (Sau poate exista o diferență funcțională care nu a fost evidentă la examinarea sumară.)

0
adăugat
Dar am încercat cea de-a doua versiune cu un acumulator, dacă se întâmplă optimizarea apelurilor de coadă, ar fi trebuit să ajute și la asta
adăugat autor Hari Menon, sursa
@ Xeon .. exact .. de aceea nu pot înțelege acest lucru.
adăugat autor Hari Menon, sursa
@HotLicks .. Am încercat cu obișnuit dacă ... altceva prea ... nu a ajutat
adăugat autor Hari Menon, sursa
Eu folosesc Sun's Hotspot JVM .. Sunt destul de sigur că nu face tail-call optimizare. Nu ar trebui să existe nicio diferență între versiunea if/else și fragmentul 1 într-adevăr .. Vă voi posta și versiunea if/else
adăugat autor Hari Menon, sursa
Utilizarea stivei. Hopa ...
adăugat autor Hot Licks, sursa
Instrucțiunea ? ar confunda probabil chestia din optimizator și va determina renunțarea la optimizarea recursivității cozii.
adăugat autor Hot Licks, sursa
@Xeon - Presupunând că folosește Sun/Oracle JVM - IBM JVMs a avut o optimizare a recursivității coada de 5 ani în urmă.
adăugat autor Hot Licks, sursa
@ Raze2dust - Dacă ați încercat-o dacă/else și acumulatorul ar fi avut versiunea originală. Mergeți pas cu pas pentru a vedea ce sparge acest lucru.
adăugat autor Hot Licks, sursa
folosirea pe heap sau folosirea stivei?
adăugat autor UmNyobe, sursa
Cu siguranță folosiți stivă. Recaderea coticii împiedică utilizarea masivă a stivei dacă ultima declarație a unei funcții este o chemare la sine. În acest caz, apelul poate fi înlocuit cu un salt, aproximativ vorbind. Funcția este în general înfășurată într-un fel de buclă transformând recursiunea în iterație. (Nu striga la mine, știu că este un pic de prea-simplificare.)
adăugat autor Wormbo, sursa
În conformitate cu aceasta: openjdk.java.net/projects/mlvm/subprojects.html și acest lucru: bugs.sun.com/bugdatabase/view_bug.do?bug_id= 6804517 optimizarea coada nu există încă. Uită-te la Apeluri de coadă și recursiune coadă . Uită-te și aici: stackoverflow.com/a/105897/639753
adăugat autor Xeon, sursa