如何在Java中比较两种方法？

Question

我在Java中有两种方法（例如阶乘计算），我必须测试这两种方法，以找出哪一种更快。我将这个代码分别实现为递归和循环：

它们都在同一个类数据中。

    public long FakultaetRekursiv( int n){
        if(n == 1){
        return 1;
        }
        else{
        return FakultaetRekursiv(n-1) * n;
        }
    }


    public long Fakultaet( int n){
        int x=1;
        for(int i=1; i<=n; i++){
            x= x*i;
        }
        return x;       
    }

我听说currentTimeMillis()可以帮助一点，但我不知道具体怎么做。 谢谢。

- altank52

---

你应该通过在存储所有可能值的数组中查找结果来实现它。这几乎可以确定是 Fakultaet 最快的实现方式。 - MrSmith42

这两种方法都不会运行足够长的时间以进行优化或产生影响。 - Peter Lawrey

你应该将递归实现中的检查条件从 n==1 改为 n==0，因为根据定义 0! == 1。同时，对于负数的 n 值，可以抛出异常。 - MrSmith42

Answer 1

微基准测试很难，使用正确的工具，例如Caliper。以下是一个适用于您的示例：

import com.google.caliper.SimpleBenchmark;

public class Benchmark extends SimpleBenchmark {

    @Param({"1", "10", "100"}) private int arg;

    public void timeFakultaet(int reps) {
        for (int i = 0; i < reps; ++i) {
            Fakultaet(arg);
        }
    }

    public void timeFakultaetRekursiv(int reps) {
        for (int i = 0; i < reps; ++i) {
            FakultaetRekursiv(arg);
        }
    }

}

该框架将会多次运行您的time*()方法，并且注入不同的arg值以便分别进行基准测试。

- Tomasz Nurkiewicz

---

确保不要忽略测试方法的结果。我曾经遇到这种情况，因为在测试循环中从未使用结果，导致整个方法似乎被优化删除了。 - MrSmith42

@MrSmith42：+1。这个问题在卡尺文档中有描述，卡尺甚至试图发现它。我想让例子简短明了。 - Tomasz Nurkiewicz

非常感谢你们的评论。我从中学到了很多东西。但是有一点小问题，我应该使用currentTimeMillis()来比较循环或递归方式哪个更快。有什么想法吗？ - altank52

Answer 2

始终坚持基础！只需使用此方法查找每个函数的执行时间。

long startTime = System.nanoTime();
methodToTime();
long endTime = System.nanoTime();

long duration = endTime - startTime;

- Aakash Anuj

---

如果我尝试用我的代码修改它，我会得到一个“无法访问的语句”编译器错误。我该如何修改？ - altank52

Answer 3

long start = System.currentTimeMillis();

// 在这里放置你的代码

System.out.println(System.currentTimeMillis() - start + "ms");

- isvforall

---

@altank52 也许你是在 return 语句之后粘贴了代码。请展示你的代码。 - isvforall

在return之前粘贴System.out.println(System.currentTimeMillis() - getLastRuntime() + "ms");。 - isvforall

当我将该代码粘贴到return语句之前时，整个循环返回的时间是0毫秒 :( - altank52

@altank52 试一下这个代码： long start = System.currentTimeMillis(); //在这里调用 FakultaetRekursiv System.out.println(System.currentTimeMillis() - start + "毫秒"); - isvforall

我们现在正在处理类，而不是演示程序。我相信您的建议适用于普通的主程序（我尝试过了，它能够工作）。但是在包含方法的类程序中，我总是遇到问题。 - altank52

Answer 4

你也可以手动完成:

第一种方法可以用一个递归关系描述为 F(x) = F(x-1) * x，它生成了这个模式...

F(x) = F(x-1) * x
= F(x-2)*x*(x-1)
= F(x-3)*x*(x-1)*(x-2)
. . .
= k*n

这是O(n)。

显然，第二种方法也可以用O(n)来描述，这意味着它们处于相同的上限。但在实施计时解决方案之前，可以将其用作快速检查。

- sdasdadas

---

@MrSmith42 编辑：你是对的！我搞糟了我的大O符号。 - sdasdadas