函数的开始和停止时间一直返回 0 或 1

Question

我正在做家庭作业，我们正在使用 10 位素数测试运行几个算法（最大公约数或 GCD）的时间。

我们要以毫秒为单位捕获运行时间，我使用 System.currentTimeMillis().

捕获该时间

我这样做的方法是有一个开始时间变量和一个停止时间变量，然后在另一个变量中找出这两者之间的差异。

到目前为止，它对一种方法非常有效，但 returns 0 或 1 对于另一种方法。

我检查了调试器，它似乎工作正常，但是当我运行它时，它 returns 0 或 1。

这是我使用的变量和主要方法。注释掉的行按预期工作，但 fastgcd 方法是 returns 0 或 1.

的方法

public class GCD {

    public static long startTime;
    public static long stopTime;
    public static long elapsedTime;

    public GCD(){

    }

    public static void main(String[] args){
        startTime = System.currentTimeMillis();

        //System.out.println(gcd(3267000013L, 1500450271L));
        System.out.println(fastgcd(3267000013L, 1500450271L));

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println(Long.toString(elapsedTime));
    }

这是有效的方法：

public static String gcd(long a, long b) {
        long n = Long.min(a, b);
        for (long i = n; i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                return "Done";
            }
        }
        // If error
        return null;
    }

下面是不起作用的方法：

public static String fastgcd(long a, long b){
        if(b == 0){
            return "Done";
        }
        else{
            return fastgcd(b, a%b);
        }
    }

因此对于有效的方法，对于 10 位数字，我将在 12000 到 12500 毫秒之间的某处。

fastgcd方法returns0或1毫秒，这是不对的，尤其是10位素数。

不知道哪里出了问题...

Answer 1

您的代码没有问题（就获取时间而言），并且您获取的值是 "correct"。您正在测量的是挂钟时间（参见 here），它本质上有点不准确，而且不够精细，无法像 fastgcd 方法一样快速地测量运行的代码.

为了高精度测量经过的时间，请使用 System.nanoTime() 而不是 System.currentTimeMillis()。

Answer 2

如果您运行您的方法并检查递归计数，它将被递归调用仅 19 次。对于这些现代编译器和机器来说，这并不是什么大操作。所以在 1 毫秒内完成它是完全合理的。如果您使用 System.nanoTime() 以纳秒为单位检查它，fastgcd 在我的 Windows 机器 Java 8、32 GB RAM 和第 8 代核心上花费了大约 280675 纳秒I7。所以这里没有问题。

函数的开始和停止时间一直返回 0 或 1

Start and Stop time of a function keeps returning 0 or 1

java

recursion

runtime