3

プロジェクトオイラーの質問2には2つの解決策があります。つまり、フィボナッチ数でさえ400万未満の合計を見つけます。

解決策1（平均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);
}

およびソリューション2（平均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に時間がかかるのはなぜですか？これをより効率的に行うことができますか？

4

2 に答える 2

4

2番目のバージョンの方が高速です。コメントで指摘されているように、タイミングが不正確です。また、数マイクロ秒かかる関数のタイミングは信頼できません。コードをループで実行し、x回の反復の合計時間を計算してから、それを使用して反復ごとの平均時間を計算する必要があります。

また、コードが機能する理由を示すことが役立つかもしれないと思いました。偶数は3つおきのインデックスで発生することに注意してください。

1  1  2  3  5  8 13 21 34
      ^        ^        ^

2番目のバージョンは、偶数のみを直接計算します。これは、F（n）とF（n-3）からF（n + 3）の値を計算することによって行われます。

F(n + 3) = F(n + 2) + F(n + 1)
         = F(n + 1) + F(n) + F(n + 1)                              [1]
         = F(n) + F(n - 1) + F(n) + F(n) + F(n - 1)                [2]
         = F(n) + F(n - 2) + F(n - 3) + F(n) + F(n) + F(n - 1)     [3]
         = F(n) + F(n) + F(n - 3) + F(n) + F(n)                    [4]
         = 4 * F(n) + F(n - 3)

次のIDが使用されます。

  1. F(n + 2) = F(n + 1) + F(n)
  2. F(n + 1) = F(n) + F(n - 1)
  3. F(n - 1) = F(n - 2) + F(n - 3)
  4. F(n) = F(n - 1) + F(n - 2)
于 2012-12-02T07:19:09.187 に答える
4

アルゴリズムを1回だけ実行することは、特に時間が10nsのオーダーである場合に、そのパフォーマンスを評価するための非常に信頼性の低い方法です。2番目の方法は、確かに高速です。各アルゴリズムを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

2番目のアルゴリズムでは、少し速いで変更(4*prevTerm)したことに注意してください。(prevTerm << 2)これにより、時間が約5％向上しました。各テストにはまだ多くのオーバーヘッドがあります。関数呼び出しと結果のローカル変数への割り当てです。ただし、繰り返すことで、への呼び出しのノイズに悩まされることはありませんSystem.nanoTime()。

最初のコードもforを使用していたdoubleためUPPER_BOUND、少し遅くなっていることに注意してください。私のコードは、テストを可能な限り並行させようとしました。

于 2012-12-02T07:54:10.063 に答える