Странная оптимизация рекурсии с помощью Java

Я столкнулся с некоторыми странными результатами, когда пытался ответить на этот вопрос: как улучшить производительность рекурсивного метода?

Но вам не нужно читать этот пост. Я дам соответствующий контекст здесь. Это может показаться длинным, но на самом деле не так сложно, если вы прочитаете один раз. Надеюсь это будет интересно всем. Для контекста,

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

а также

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

например,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, Поэтому syra(10) понадобилось 7 шагов. Следовательно syralen(10)=7

И наконец,

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

Постер с вопросом там пытается вычислить lengths(n)

Мой вопрос о рекурсивном решении, опубликованном Op (второй фрагмент в этом вопросе). Я отправлю это сюда:

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));
        }
       }

Конечно, необычный (и, вероятно, не рекомендуемый) способ сделать это рекурсивно, но он действительно рассчитывает правильную вещь, я это подтвердил. Я попытался написать более обычную рекурсивную версию того же самого:

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));
    }

Теперь вот странная часть - я попытался проверить производительность обеих вышеупомянутых версий как:

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));
        }

За TEST_VAL=50000, вывод:

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

Как и ожидалось (я думаю) простая рекурсия немного лучше. Но когда я иду на шаг дальше и использую TEST_VAL=500000, вывод:

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

Почему это? Какую оптимизацию выполняет Java здесь, чтобы версия SyraLengths не работала с Stackru (она работает даже при TEST_VAL=5000000)? Я даже пытался использовать рекурсивную версию на основе аккумулятора на случай, если моя JVM выполняет некоторую оптимизацию хвостового вызова:

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);
    }

Но я все еще получил тот же результат (таким образом, здесь нет оптимизации хвостового вызова). Итак, что здесь происходит?

PS: Пожалуйста, измените название на лучшее, если можете придумать.

Источник

2 ответа

Решение

Well, it turns out there is a simple explanation to it:

я использую long syraLen(int n) в качестве подписи метода. Но ценность n can actually be much larger than Integer.MAX_VALUE, Так syraLen gets negative inputs and therein lies the problem. Если я изменю это на 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.

Источник

В оригинальной версии возможна оптимизация хвостовой рекурсии (в JIT). Не знаю, произошло ли это на самом деле или нет, хотя. Но возможно, что оригинал немного более эффективен с использованием кучи (я имею в виду стек). (Или может быть функциональная разница, которая не была очевидна при беглом осмотре.)

Источник
Другие вопросы по тегам