logo标签列表

在Java中最快的递归跳出方法

javaalgorithmperformancerecursion
15

有没有一种干净快速的方法在Java中逃离递归？使用 break; 语句可以从 for loop 中跳出。那么是否有等效的模式或方法可以从递归中逃脱？

我能想到的是生成一个单独的线程，一旦计算完成后，简单地杀死线程而不是沿着递归堆栈往回冒泡。还有更好的方法吗？

已经有一个讨论如何打断递归的问题：here。

我想要的是更快地实现它的方法，可能不需要回溯整个堆栈。类似于 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;
}
2
这里有一个不错的讨论：https://dev59.com/X3RA5IYBdhLWcg3wtwSe - Andrea Iacono
28
throw new ResultFoundException(...); 尽管我不会冒险将其作为答案返回，以免被踩。 :) （注：该句代码中的异常类名 "ResultFoundException" 可能需要根据上下文进行调整翻译） - Joop Eggen
3
我认为这实际上是与第一个评论中链接的问题重复了，但我一直犹豫是否关闭或使用"dupehammer"（重复问题锤）... - Marco13
1
通常是递归方法决定是递归还是计算出一个值，因此 break 会是 return <value>; 而不是 return recur(...);。如果你正在遍历一棵树，通常会搜索下一个子节点，如果当前节点没有得到答案。也许你可以举出一个这种方法行不通的例子？ - Sylwester
在您添加的示例中，是否应该写成MyClass v = myFunct(c.valueB); //做一些工作 if (v.valueE == 7) {？（您可能需要添加一个参数来控制接下来的两个递归调用并不完全相同，而且需要避免从独立的深度/间接嵌套调用中逃脱时产生不良副作用。） - greybeard
显示剩余5条评论
7个回答
13

通常解决这个问题最简单的方法是将递归替换为非递归解决方案。如果实现得当，这很可能会改善性能。杀死线程的方法相当丑陋 - 我强烈建议不要使用这种方法。但是没有其他方法可以在不回溯栈的情况下跳出递归。

递归：

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

    //do some stuff with i

    return rec(i);
}

非递归：

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

这是一个相当简单的例子，但对于更复杂的递归问题，原则是相同的。
我同意这是最明智的选择，但有时候需要付出很多努力。我更关注写作速度 - 编程比赛之类的东西。 - bjedrzejewski
1
@jedrus07，实际上这不应该是太多的工作，因为你所需要做的就是使用自己的堆栈而不是系统堆栈。即使在方法中有多个递归调用，这也可以很容易且快速地实现。我会编辑帖子来演示。 - user4668606
在你的演示中，实际上你根本不需要使用堆栈，因为你的 rec 函数是尾递归的 :-) - Bergi
13

回答你的问题非常简单：

通常情况下，采用传统方式，也就是使用return手动展开堆栈。为什么？因为这并不像你想象的那样慢。除非递归计算非常琐碎且堆栈深度非常非常高，否则返回将不会明显影响算法的运行时间。

基本上，你有以下几个选择：

  • 如果可能，将算法转换为迭代算法。
  • 将算法转换为尾递归，并希望虚拟机能够重用堆栈帧。然后，从递归中返回实际上等同于一个简单的return。
  • 抛出异常。然而，这比返回甚至更慢，因为必须构建堆栈跟踪，它最终也要遍历堆栈。还必须展开堆栈以检查catch。你什么也没赢得到。

前两个选项是可行的，但并非总是可行的。但老实说，请不要考虑这个问题。从深度堆栈返回并不是使您的算法变慢的原因。如果您有一个非常深的递归算法，则无论如何都存在问题（堆栈溢出，递归调用的成本），应该考虑重写您的算法。如果堆栈深度很低，则这不是问题。

这里有一个简单的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);
            }
        }
    }
}

它计算一个递归函数，其堆栈深度将等于输入参数。该函数在每个堆栈帧中计算平方根以模拟一些非平凡的计算。它还以迭代方式计算相同的函数。为了热身JIT，在仅打印第十个结果之前，程序首先执行9次而不打印结果。这是我的结果（我必须使用-Xss1g增加堆栈大小到1 GB）。这是来自我的机器的结果：

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

如您所见，从深度为一百万的栈返回需要3毫秒。更大的栈大小会导致更长的时间，可能是由于栈不再适合L3缓存。但是，如果你需要这么大的栈，你已经有了一个问题，就像上面所描述的那样。在Java中使用1GB的最大堆栈大小并不是最好的选择。任何小于131072的堆栈大小无法测量毫秒级别。在一个健康的算法中，堆栈应该比这个小得多，所以你应该总是没问题。

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

结论

如果递归对您来说太慢了，请完全摒弃它。仅仅跳过返回不会有太大的差异。

将您的算法转换为尾递归，并希望虚拟机会重用堆栈帧。这种情况真的会发生吗？您有相关来源吗？ - nanny
@nanny：这当然取决于你使用的编程语言。C/C++肯定可以做到。我的JVM不支持，我刚测试过了。Scala编译器在编译期间会进行优化（https://dev59.com/YXI-5IYBdhLWcg3wxrqQ）。 - gexicide
Java确实不执行尾调用优化（来源：http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044），而它的表亲C#则执行（来源：http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx）。 - Roy T.
4

如果你改变算法，让它维护自己的栈而不是使用系统CPU栈，那么你可以直接丢弃这个栈。

4

假设你有一些内部重复的递归，就像这段不太合理的代码：

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

当找到 (a != null) 时，这将产生一系列返回。

与 break 的类比是 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() { }
}
你知道它是否实际上比较快吗？我听说异常处理很耗费资源。 - bjedrzejewski
异常会成为规则（在找到结果的情况下），并且会进行堆栈回溯，这会稍微慢一些。然而，一系列的返回+检查也可能会变慢，这取决于递归深度。我不知道对热点编译器的影响。使用大数据来衡量它。 - Joop Eggen
2
在 HotSpot 上，您可以通过覆盖 ResultFoundException 中的 fillInStackTrace 为 return this; 来显著提高性能。大部分异常开销都是填充堆栈跟踪的 JNI 调用造成的。 - James_pic
2
正如其他人指出的那样，堆栈必须被重置。

拥有另一个线程是丑陋的，而且可能比抛出异常慢得多。

我会尝试找到非递归方法或使用正常的递归并进行适当返回。也许如果你提供一个正在尝试做什么的示例，人们可以指引你走向正确的方向。

如果我迫切需要这样做，我会有一个包装方法来捕获递归函数抛出的异常。

免责声明：我没有尝试过这个，所以它甚至可能无法编译 :)

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");
}
2
وˆ‘ه»؛è®®ه°†GotAResultExceptionو”¹ن¸؛EverythingIsFineExceptionم€‚ - Marco13
1
我会投票支持 AllIsWellException，因为它更加简洁（并且增加了混淆;-)（取决于字体））。 - Hulk
0
一个被广泛接受的设计 - 即使它可能取决于您的特定情况 - 是使用Java Future<T>（或类似物）。如果您要使用线程，请记住，线程取消需要安全和清洁的策略。关于这些主题有非常好的文献，例如Java Concurrency In Practice。
0

一种选择是在MyClass上设置一个标志，并根据该标志返回：

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;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接