3

谁能解释为什么以下递归方法比迭代方法更快（两者都在进行字符串连接）？迭代方法不是要打败递归方法吗？加上每个递归调用都会在堆栈顶部添加一个新层，这可能会非常低效。

    private static void string_concat(StringBuilder sb, int count){
        if(count >= 9999) return;
        string_concat(sb.append(count), count+1);
    }
    public static void main(String [] arg){

        long s = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 9999; i++){
            sb.append(i);
        }
        System.out.println(System.currentTimeMillis()-s);
        s = System.currentTimeMillis();
        string_concat(new StringBuilder(),0);
        System.out.println(System.currentTimeMillis()-s);

    }

我多次运行程序，递归的总是比迭代的快 3-4 倍。导致迭代速度变慢的主要原因可能是什么？

4

1 回答 1

8

见我的评论。

确保您学习如何正确地进行微基准测试。您应该为这两者的多次迭代计时，并为您的时间平均这些迭代。除此之外，您应该确保虚拟机不会通过不编译第一个来给第二个带来不公平的优势。

事实上，默认的 HotSpot 编译阈值（可通过 配置-XX:CompileThreshold）是 10,000 次调用，这可能解释了您在此处看到的结果。HotSpot 并没有真正做任何尾部优化，所以递归解决方案更快是很奇怪的。StringBuilder.append主要是为了递归解决方案而编译为本机代码是很合理的。

我决定重写基准测试并亲自查看结果。

public final class AppendMicrobenchmark {

  static void recursive(final StringBuilder builder, final int n) {
    if (n > 0) {
      recursive(builder.append(n), n - 1);
    }
  }

  static void iterative(final StringBuilder builder) {
    for (int i = 10000; i >= 0; --i) {
      builder.append(i);
    }
  }

  public static void main(final String[] argv) {
    /* warm-up */
    for (int i = 200000; i >= 0; --i) {
      new StringBuilder().append(i);
    }

    /* recursive benchmark */
    long start = System.nanoTime();
    for (int i = 1000; i >= 0; --i) {
      recursive(new StringBuilder(), 10000);
    }
    System.out.printf("recursive: %.2fus\n", (System.nanoTime() - start) / 1000000D);

    /* iterative benchmark */
    start = System.nanoTime();
    for (int i = 1000; i >= 0; --i) {
      iterative(new StringBuilder());
    }
    System.out.printf("iterative: %.2fus\n", (System.nanoTime() - start) / 1000000D);
  }
}

这是我的结果...

C:\dev\scrap>java AppendMicrobenchmark
recursive: 405.41us
iterative: 313.20us

C:\dev\scrap>java -server AppendMicrobenchmark
recursive: 397.43us
iterative: 312.14us

这些是每种方法平均超过 1000 次试验的时间。

从本质上讲，您的基准测试的问题在于它不会在多次试验（大数定律）中取平均值，并且它高度依赖于各个基准测试的顺序。我给你的原始结果：

C:\dev\scrap>java StringBuilderBenchmark
80
41

这对我来说意义不大。HotSpot VM 上的递归很可能不会像迭代那样快，因为到目前为止它还没有实现任何类型的尾部优化，你可能会发现它用于函数式语言。

现在，这里发生的有趣的事情是默认的 HotSpot JIT 编译阈值为 10,000 次调用。您的迭代基准测试很可能在编译之前 大部分时间都在执行。append另一方面，您的递归方法应该相对较快，因为它很可能会在编译append 后使用。为了消除这种影响结果，我通过-XX:CompileThreshold=0并发现......

C:\dev\scrap>java -XX:CompileThreshold=0 StringBuilderBenchmark
8
8

因此，归根结底，它们的速度大致相等。但是请注意，如果您以更高的精度进行平均，迭代似乎会更快一些。顺序也可能对我的基准测试产生影响，因为后一个基准测试将具有 VM 为其动态优化收集更多统计数据的优势。

于 2012-09-05T03:34:48.657 回答