1

I have a recursive algorithm (in three different forms) which computes the sum of the first n odd positive integers. These algorithms are for learning only, I'm aware that there are better ways of solving this problem. I've written the three variants in both Lua and Java, which I'll call Lua 1, Lua 2, Lua 3 and Java 1, Java 2 and Java 3. The first two are very similar, just rearranged.

The Lua programs are here, and the Java programs are here.

Lua 1 and 2 perform extremely well and could easily reach n = 100,000,000. Lua 3 hits a stack overflow where n > 16,000.

Java 1 could only reach n = 4000 before hitting a stack overflow while Java 2 reached 9000. Java 3 managed to get to n = 15,000 before again hitting a stack overflow.

Can anyone explain these results? Why did Java 1, 2 and 3 perform so poorly while Lua 1 and 2 performed so well?

4

2 回答 2

3

Lua 执行尾调用消除。例如，这样的函数：

function foo (n)
    if n > 0 then return foo(n - 1) end
end

n无论您调用什么值，都不会导致堆栈溢出。

在 Lua 中，只有带有表单的调用return func(args)是尾调用，就像你的前两个 Lua 程序所做的那样。但是在第三个 Lua 程序中：

return (sumOdds3(n-1)) + (2*n - 1)

Lua 在返回之前仍然需要进行计算，所以没有适当的尾调用。

于 2013-07-25T02:21:19.430 回答
1

Java 不是为递归算法设计的。特别是它不支持常见的优化，如尾调用优化。

Java 更适合使用循环，通常速度更快，而且通常使用普通循环很简单。

如果你使用迭代和双端队列，你应该没问题，几乎没有限制n

当您运行效率非常低的代码时，您往往会发现一种情况或另一种情况可以优化方式，效率低下会产生很大的不同。

一种更有效的方法

// function to compute the sum of the first n odd positive integers
public static long sumOdds(long n) {
    long sumAll = n * (n + 1)/2;
    long sumEven = n/2 * (n/2 + 1);
    return sumAll - sumEven;
}
public static void main(String[] args) throws Exception {
    sumOdds(1);

    long start = System.nanoTime();
    long l = sumOdds(Integer.MAX_VALUE);
    long time = System.nanoTime() - start;
    System.out.printf("sumOdds(%,d) took %,d ns%n", Integer.MAX_VALUE, time);
}

印刷

sumOdds(2,147,483,647) took 343 ns
于 2013-07-25T00:03:33.587 回答