2012-12-02 57 views
3

我有兩個Project Euler問題2的解決方案,即找到所有連平均斐波那契數小於400萬的總和。混淆求偶數斐波那契數的和運行時間

解決方法一(這需要11000毫微秒的平均值):

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(這需要14000毫微秒的平均值):

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語句? 這可以更有效地完成嗎?

+6

您的計時碼不正確;您應該在進入while循環之前在main方法中啓動計時器,而不是作爲字段初始值設定程序。 – Asik

+0

就是這樣。第一個是3400納秒,第二個是3000。這是我期待的(第二個更快) –

+0

它沒有任何價值,你沒有執行足夠的迭代來預熱JVM。這意味着你正在處理翻譯如何表現的變幻莫測。注意:可以通過使用每第三個斐波那契數爲偶數來減少數字迭代(這會將迭代次數減少三分之一) –

回答

4

運行你的算法只有一次是評估其性能的非常不可靠的方式,特別是當時間爲10ns時。你的第二種方法的確速度更快。我重寫了您的代碼,以迭代每個算法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; 
    } 
} 

結果(典型):

時間1 = 189910; sum1 = 4613732
Time2 = 35501; SUM2 = 4613732

注意,在第二算法,我改變(4*prevTerm)(prevTerm << 2),這是稍快。這使時間縮短了大約5%。每個測試中仍有很多開銷:函數調用並將結果分配給本地變量。但是,通過迭代,您在撥打System.nanoTime()時不會聽到噪音。

請注意,您的第一個代碼也使用double代替UPPER_BOUND,這會降低一點。我的代碼試圖使測試儘可能平行。

+0

用於回答問題的+1 –

+0

我應該寫一個bash腳本來運行我的代碼幾千次。有沒有更可靠的方法來查看/圖算法運行時間? –

+0

@yudhishthirsingh - 我不會使用bash腳本。這會增加開銷,因爲每次都需要加載並啓動程序。開銷越大,您嘗試測量的東西之間的區分越模糊。最好的方法是儘可能隔離要測量的內容,然後儘可能緊湊地包裝時間代碼。 –

4

第二版更快。正如評論中指出的那樣,你的計時不準確。同時計算需要幾微秒的函數也是不可靠的。您應該循環運行代碼並調整x次迭代的總時間,然後使用它計算每次迭代的平均時間。

此外,我認爲這可能是有用的,以顯示爲什麼代碼的作品。請注意,偶數會在每第三個索引處出現。

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

第二個版本只是直接計算偶數。它通過計算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) 

以下身份用於:

  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)
+0

問題不在於第二種解決方案的工作原因。這就是爲什麼執行需要更長時間。 –

+0

@TedHopp:哦,我誤解了這個問題......但我想答案仍然可能對某些人有用。 –

+0

這確實是一個很好的派生。 –