从Java中递归最快的逃脱

Question

从Java中递归最快的逃脱

bje*_*ski 14 java algorithm recursion performance

有没有办法干净利落地快速逃离Java中的递归？有一种方法可以for loop通过使用该break;语句来突破.是否存在转义递归的等效模式或方法？

我可以想到产生一个单独的线程,一旦计算出值,就可以简单地杀死一个线程,而不是冒泡出递归堆栈.有没有更好的办法？

已经有一个问题讨论如何摆脱递归:这里.

我正在寻找的是一种更快的实现方式,可能无需回过头.像一个goto或一个break声明的东西.

这里考虑的标准是:

使用此转义的重构容易
原始性能(越快越好)
实践中的长度(写入/添加越快越好)

我正在寻找的答案将解释解决方案的性能和简单性 - 这是在算法竞争的背景下提出的,因此首选需要较少重构的解决方案.

我为什么要使用它？

有时在编写某些算法竞争时,你需要从递归内部返回一个值,我想知道你是否可以通过使用这种中断更快地完成它.考虑看起来像这样的算法:

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

Run Code Online (Sandbox Code Playgroud)

Answer 1

Pau*_*aul 14

通常,解决此问题的最简单方法是使用非递归解决方案简单地替换递归.如果正确实施,这也很可能会改善性能.杀死线程的方法相当丑陋 - 我强烈建议不要使用它.但是没有办法在没有倒带堆栈的情况下突破递归.

递归:

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

    //do some stuff with i

    return rec(i);
}

Run Code Online (Sandbox Code Playgroud)

非递归:

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

Run Code Online (Sandbox Code Playgroud)

这是一个相当简单的例子,但对于更复杂的递归问题,原理是相同的.

Answer 2

gex*_*ide 13

你的问题的答案很简单:

只需按常规方式进行,即用returns 展开堆栈.为什么？因为这并不像你想象的那么慢.除非递归中的计算非常简单并且堆栈深度非常高,否则返回将永远不会显着影响算法的运行时间.

基本上,您有以下选择:

如果可能,将算法转换为迭代算法.
将您的算法转换为结束递归,并希望VM将重用堆栈帧.然后,退出递归几乎等于一个简单的返回.
抛出一个例外.但是,这将比返回更慢,因为必须构建堆栈跟踪,最终也会遍历堆栈.还必须解开堆栈以检查catches.你什么都没赢.

前两个选项是可行的,但并非总是可行.但老实说,不要考虑它.返回深堆栈并不是使算法变慢的部分.如果您的算法具有非常深的递归,那么无论如何您都会遇到问题(堆栈溢出,递归调用的成本)并且应该考虑重写算法.如果堆栈深度很低,那么无论如何这都不是问题.

这是一个简单的Java测试程序,向您展示我的意思:

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

Run Code Online (Sandbox Code Playgroud)

它计算递归函数,其堆栈深度等于输入参数.该函数计算每个堆栈框架中的平方根,以模拟一些非平凡的计算.它还以迭代方式计算相同的函数.为了预热JIT,程序首先执行9次而不打印结果; 只打印了第十个结果.这是我的结果(我必须将堆栈大小增加到1 GB -Xss1g.以下是我的机器的结果:

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

Run Code Online (Sandbox Code Playgroud)

如你所见,从一百万深度的堆栈返回需要3毫秒.较大的堆栈大小会导致更长的时间,可能是由于堆栈不再适合L3缓存.但是,如果您需要这么大的堆栈,那么无论如何都会遇到问题,如上所述.以1千兆字节的最大堆栈大小运行Java并不是最好的选择.任何低于131072的堆栈大小都无法以毫秒为单位进行测量.在一个理智的算法中,堆栈应该比这小得多,所以你应该总是很好.

如您所见,最快的解决方案是迭代解决方案,因此如果非常深的递归太慢,请完全避免它,而不是仅跳过返回.

结论

如果递归对你来说太慢,那就完全摆脱它.只是跳过回报不会产生很大的影响.

归档时间：	10 年，4 月前
查看次数：	2775 次
最近记录：	10 年，4 月前