java - 对求偶数斐波那契数之和的运行时间感到困惑

Question

欧拉计划第2题我有两种解法，即求所有小于400万的斐波那契数的和。

解决方案一(平均需要 11,000 纳秒):

public class Solution {

static long startTime = System.nanoTime();
static final double UPPER_BOUND = 40e5;
static int sum = 2;

public static int generateFibNumber(int number1, int number2){
    int fibNum = number1+ number2;
    return fibNum;
}

public static void main( String args[] ) {
    int i = 2;
    int prevNum = 1;
    while(i <= UPPER_BOUND) {
        int fibNum = generateFibNumber(prevNum,i);
        prevNum = i;
        i = fibNum;
        if (fibNum%2 == 0){
            sum += fibNum;
        }
    }
    long stopTime = System.nanoTime();
    long time = stopTime - startTime;
    System.out.println("Sum: " + sum);
    System.out.println("Time: "+ time);
}

和解决方案二(平均需要 14,000 纳秒):

public class Solution2 {
static long startTime = System.nanoTime();  
final static int UPPER_BOUND = 4_000_000;
static int penultimateTerm = 2;                                         
static int prevTerm = 8;                                                
static int currentTerm = 34;                                             
static int sum = penultimateTerm+ prevTerm;                 

public static void main( String args[]) {
    while (currentTerm <= UPPER_BOUND) {
        sum+= currentTerm;
        penultimateTerm = prevTerm;
        prevTerm = currentTerm;
        currentTerm = (4*prevTerm) + penultimateTerm;
    }

    long stopTime = System.nanoTime();
    long time = stopTime - startTime;
    System.out.println("Sum: " + sum);
    System.out.println("Time: " + time);

}

当我在 while 循环中执行更少的迭代并且也没有 if 语句时，为什么解决方案 2 花费的时间更长？ 这可以更有效地完成吗？

Answer 1

仅运行您的算法一次是一种非常不可靠的评估其性能的方法，尤其是当时间大约为 10 纳秒时。你的第二种方法确实更快。我重写了您的代码，将每个算法迭代 100 次，得到的结果与您截然不同。

代码:

public class Fib {
    private static int UPPER_BOUND = 4000000;
    private static int ITERS = 100;
    public static void main(String[] args) {
        long time1, time2;
        int sum1 = 0, sum2 = 0;
        long startTime = System.nanoTime();
        for (int iter = 0; iter < ITERS; ++iter) {
            sum1 = sol1();
        }
        time1 = System.nanoTime() - startTime;

        startTime = System.nanoTime();
        for (int iter = 0; iter < ITERS; ++iter) {
            sum2 = sol2();
        }
        time2 = System.nanoTime() - startTime;
        System.out.println("Time1 = " + time1 + "; sum1 = " + sum1);
        System.out.println("Time2 = " + time2 + "; sum2 = " + sum2);
    }

    private static int sol1() {
        int sum = 2;
        int i = 2;
        int prevNum = 1;
        while(i <= UPPER_BOUND) {
            int fibNum = generateFibNumber(prevNum,i);
            prevNum = i;
            i = fibNum;
            if (fibNum%2 == 0){
                sum += fibNum;
            }
        }
        return sum;
    }

    private static int sol2() {
        int penultimateTerm = 2;
        int prevTerm = 8;
        int currentTerm = 34;
        int sum = penultimateTerm + prevTerm;
        while (currentTerm <= UPPER_BOUND) {
            sum += currentTerm;
            penultimateTerm = prevTerm;
            prevTerm = currentTerm;
            currentTerm = (prevTerm << 2) + penultimateTerm;
        }
        return sum;
    }

    private static int generateFibNumber(int number1, int number2) {
        return number1+ number2;
    }
}

结果(典型):

Time1 = 189910; sum1 = 4613732
Time2 = 35501; sum2 = 4613732

请注意，在第二个算法中，我更改了 (4*prevTerm)与 (prevTerm << 2) ，速度稍快。这将时间缩短了大约 5%。每个测试中仍然有很多开销:函数调用并将结果分配给局部变量。但是，通过迭代，您不会在对 System.nanoTime() 的调用中陷入困境。 .

请注意，您的第一个代码还使用了 double对于 UPPER_BOUND ，这会减慢它的速度。我的代码试图使测试尽可能并行。