只是为了好玩,我试图比较使用朴素递归算法计算斐波那契数列的几种编程语言的堆栈性能。该代码在所有语言中基本上都是相同的,我将发布一个Java版本:

public class Fib {
 public static int fib(int n) {
  if (n < 2) return 1;
  return fib(n-1) + fib(n-2);
 }

 public static void main(String[] args) {
  System.out.println(fib(Integer.valueOf(args[0])));
 }
}

好的,关键是,将这种算法与输入40配合使用时,我得到了以下时序:
C: 2.796s
Ocaml: 2.372s
Python: 106.407s
Java: 1.336s
C#(mono): 2.956s

它们是在Ubuntu 10.04机器中使用官方存储库中可用的每种语言的版本安装在双核Intel机器上的。

我知道像ocaml这样的功能语言会因为将函数视为一阶公民而放慢速度,并且没有问题来解释CPython的运行时间,因为它是该测试中唯一的解释语言,但我对Java的运行印象深刻对于相同算法,时间是c的一半!您将其归因于JIT编译吗?

您将如何解释这些结果?

编辑:感谢您的有趣的答复!我认识到这不是一个适当的基准(永远不要说它是:P),也许我可以根据我们讨论的内容制定一个更好的基准,然后下一次发布给您:)

编辑2:我使用优化的编译器ocamlopt更新了ocaml实现的运行时。我还在https://github.com/hoheinzollern/fib-test上发布了测试平台。如果需要,可以随时对其进行添加:)

最佳答案

您可能需要提高C编译器的优化级别。使用gcc -O3,差异很大,从2.015秒减少到0.766秒,减少了大约62%。

除此之外,您还需要确保已正确测试。您应该将每个程序运行十次,删除异常值(最快和最慢),然后平均其他八个。

另外,请确保您正在测量的是CPU时间而不是时钟时间。

除此之外,我不会考虑进行像样的统计分析,它很可能会受到干扰,使您的结果毫无用处。

值得一提的是,上面的那些C计时是进行了7次运行,其中的异常值在取平均值之前被剔除。

实际上,这个问题说明了在追求高性能时算法选择的重要性。尽管递归解决方案通常很优雅,但是这种解决方案存在重复很多计算的缺点。迭代版本:

int fib(unsigned int n) {
    int t, a, b;
    if (n < 2) return 1;
    a = b = 1;
    while (n-- >= 2) {
        t = a + b;
        a = b;
        b = t;
    }
    return b;
}

进一步将花费的时间从0.766秒减少到0.078秒,与原始代码相比进一步减少了89%,并且大幅减少了96%。

并且,作为最后的尝试,您应该尝试以下操作,该操作将查找表与超出特定点的计算结合在一起:
static int fib(unsigned int n) {
    static int lookup[] = {
        1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
        610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657,
        46368, 75025, 121393, 196418, 317811, 514229, 832040,
        1346269, 2178309, 3524578, 5702887, 9227465, 14930352,
        24157817, 39088169, 63245986, 102334155, 165580141 };
    int t, a, b;

    if (n < sizeof(lookup)/sizeof(*lookup))
        return lookup[n];
    a = lookup[sizeof(lookup)/sizeof(*lookup)-2];
    b = lookup[sizeof(lookup)/sizeof(*lookup)-1];
    while (n-- >= sizeof(lookup)/sizeof(*lookup)) {
        t = a + b;
        a = b;
        b = t;
    }

    return b;
}

这再次减少了时间,但我怀疑我们正在达到返回递减的地步。

关于java - 编程语言中的堆栈性能,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/4121790/

10-08 21:58
查看更多