算法效率 - 如果需要更多的比較，部分展開循環是否有效？

如何判斷是否將兩個額外的任務在迭代是，如果條件測試另一件事昂貴或設置？這裏我詳細說明。問題是生成並打印n> = 1的斐波那契數列的前n項。我用C實現是：算法效率 - 如果需要更多的比較，部分展開循環是否有效？

#include<stdio.h> 
void main() 
{ 
    int x=0,y=1,output=0,l,n; 
    printf("Enter the number of terms you need of Fibonacci Sequence ? "); 
    scanf("%d",&n); 
    printf("\n"); 
    for (l=1;l<=n;l++) 
    { 
     output=output+x; 
     x=y; 
     y=output; 
     printf("%d ",output); 
    } 
}

但是這本書的作者「如何用計算機解決它」說，這是低效的，因爲它使用了兩個額外的任務爲產生一個Fibonacci數。他建議：

a=0 
b=1 
loop: 
print a,b 
a=a+b 
b=a+b

我同意這是更有效，因爲它使a和b相關的所有的時間和一個分配生成一個號碼。但它一次打印或提供兩個斐波納契數字。假設問題是產生奇數個術語，我們會做什麼？筆者建議設置一個測試條件來檢查n是否爲奇數。我們不會因爲在每次迭代中增加if測試而失去減少分配數量的收益嗎？

來源

2011-11-17 KawaiKx

定義「高效」。它對漸近複雜性沒有任何影響，當使用優化編譯器時，它可能非常好地*無*差* *，即使它們有差別，它也會變得非常微小，並且小於（小於一萬倍） I/O開銷。 – delnan

判斷它是否「昂貴」的唯一方法是分析這兩個版本。 –

什麼可能造成可衡量的差異是它允許在一個打印語句中打印兩個數字。正如@delnan所說的那樣，與I/O成本相比，額外變量（如果編譯器不會優化這些變量）和分配（也包括檢查）的成本是微不足道的。 –

我的第一個建議呼應了其他人：首先爭取乾淨，清晰的代碼，然後優化，你知道有性能問題。（很難想象時間關鍵的斐波那契測序儀......）

然而，作爲一個在微秒系統中工作的系統工作的人來說，有一個簡單的解決方案來解決你所問的問題：如果奇怪的話，只測試一次，不在循環內。

循環展開的一般模式是

create X repetitions of the loop logic. 
    divide N by X. 
    execute the loop N/X times. 
    handle the N%X remaining items.

對於您的特定情況：

a=0; 
b=1; 
nLoops = n/2; 
while (nloops-- > 0) { 
    print a,b; 
    a=a+b; 
    b=a+b; 
} 
if (isOdd(n)) { 
    print a; 
}

（還請注意，N/2和ISODD被平凡二進制計算機上實現，並非常快。）

來源

2011-11-17 17:18:06 AShelly

沒有評論您的實際代碼：當你在學習編程，記住，小的效率改進，使代碼難於閱讀是不值得的。至少，他們直到生產應用程序的分析才顯示它是值得的。

可以由人來閱讀

編寫代碼;它會讓你的生活變得更容易，並讓維護程序員免受你和你後代的詛咒。

來源

2011-11-17 17:00:48 drdwilcox

我從筆者認爲這是非常糟糕的建議，即使在定位於初級程序員一本書提起這事。（編輯：平心而論，編程普遍更低水平比現在當書最初發表於1982年，時間）的代碼

99.9％，不需要進行優化。尤其是在非常昂貴的操作（I/O）這樣的代碼混合了非常便宜的操作（在整數運算），它的時間來優化便宜的部分完全是浪費。

微優化，這應該只是在時間要求嚴格的代碼被認爲是當需要擠壓的每一點性能的硬件。

當你確實需要它時，要知道幾個選項中哪一個最好的唯一方法是度量。即便如此，結果可能不同的處理器，平臺的內存配置更改...

來源

2011-11-17 17:12:09

+1對於初學者不好的建議（我喜歡優化）。 – phkahler

算法效率 - 如果需要更多的比較，部分展開循環是否有效？

回答

相關問題