C程序設(shè)計(jì)教程6

1、11:39:081C+程序設(shè)計(jì)教程(第二版)Chapter 6 Performance 11:39:082n提高性能的意義： 性能對(duì)提高編程能力舉足輕重n如何提高性能？ 以合理使用資源為前提，盡快完成任務(wù)的能力稱(chēng)為效率效率影響性能，提高效率就能提高性能n學(xué)習(xí)目標(biāo)： 1. 擴(kuò)展視野，對(duì)同一問(wèn)題的不同要求，模仿各種編程技巧與空間布局策略，予以應(yīng)對(duì)從而對(duì)各種不同的問(wèn)題，亦能應(yīng)變自如 2. 掌握測(cè)試性能的方法，學(xué)會(huì)測(cè)算時(shí)/空交換的代價(jià)，客觀評(píng)估自身的編程能力11:39:083第六章內(nèi)容 內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù) ( Inline Functions ) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) ( Data Structures )

2、 算法算法 ( Algorithms ) 數(shù)值計(jì)算數(shù)值計(jì)算 ( Numerical Computation ) STL算法算法 ( STL Algorithms ) 動(dòng)態(tài)內(nèi)存動(dòng)態(tài)內(nèi)存 ( Dynamic Memory ) 低級(jí)編程低級(jí)編程 ( Lower Programming ) 11:39:0841. 內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù) ( Inline Functions )n做法：將一些反復(fù)被執(zhí)行的簡(jiǎn)單語(yǔ)句序列做成小函數(shù)n用法：在函數(shù)聲明前加上inline關(guān)鍵字n作用：不損害可讀性又能提高性能11:39:085/=#includeboolbool isDigit(charchar); / 小函數(shù)inti

3、nt main( ) forfor(charchar c; cinc & c!=n; ) ifif(isDigit(c) std:cout“Digit.n; elseelse std:cout=0 & ch=9 ? 1 : 0;/=頻繁調(diào)用的函數(shù)：用昂貴的開(kāi)銷(xiāo)換取可讀性11:39:086/=#includeintint main( ) forfor(charchar c; cinc & c!=n; ) ifif(ch=0 & ch=9 ? 1 : 0) std:cout“Digit.n; elseelse std:cout“NonDigit.n;/=內(nèi)嵌代碼：開(kāi)

4、銷(xiāo)雖少，但可讀性差11:39:087內(nèi)聯(lián)方式：開(kāi)銷(xiāo)少，可讀性也佳/=#includeninline boolinline bool isDigit(charchar); / 小函數(shù)nintint main( )n forfor(charchar c; cinc & c!=n; )n ifif(isDigit(c) n std:coutDigit.n;n elseelse n std:cout=0 & ch=9 ? 1 : 0;n/=內(nèi)聯(lián)標(biāo)記放在函數(shù)聲明的前面11:39:088內(nèi)聯(lián)函數(shù)的使用經(jīng)驗(yàn)：n函數(shù)體適當(dāng)小,且無(wú)循環(huán)或開(kāi)關(guān)語(yǔ)句，這樣就使嵌入工作容易進(jìn)行，不會(huì)破壞原調(diào)用主體如：

5、排序函數(shù)不能內(nèi)聯(lián)n程序中特別是在循環(huán)中反復(fù)執(zhí)行該函數(shù)，這樣就使嵌入的代碼利用率較高如：上例中的isDigit函數(shù)n程序并不多處出現(xiàn)該函數(shù)調(diào)用，這樣就使嵌入工作量相對(duì)較少，代碼量也不會(huì)劇增 11:39:089n/=n#includen#includenusing namespaceusing namespace std;n/-nintint calc1(intint a, intint b) returnreturn a+b; ninline intinline int calc2(intint a, intint b) returnreturn a+b; n/-nintint main()n

6、intint x1000, y1000, z1000;n clock_t t = clock();n forfor(intint i=0; i1000*1000*1000; +i)n zi = calc1(xi%1000, yi%1000);n cout(clock()-t)/CLK_TCK“without inlinen;n t = clock();n forfor(intint i=0; i1000*1000*1000; +i)n zi = calc2(xi%1000, yi%1000);n cout(clock()-t)/CLK_TCKf0605 8.281 without inline

7、2.437 with inline11:39:08112. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) ( Data Structures )n揭示：將數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)為數(shù)據(jù)類(lèi)型是編程的高級(jí)境界，STL容器就是系統(tǒng)提供的現(xiàn)成數(shù)據(jù)結(jié)構(gòu)n做法：充分和合理使用STL容器,簡(jiǎn)化復(fù)雜問(wèn)題,提高編程效率與程序性能11:39:0812問(wèn)題：有許多序列，每個(gè)序列都等待驗(yàn)證是否可從順序數(shù)列經(jīng)過(guò)棧操作而得 例如：順序數(shù)列 1,2,3,4,5 待驗(yàn)證序列 3,2,1,5,4 待驗(yàn)證序列 5,3,4,2,111:39:0813采用不同的數(shù)據(jù)結(jié)構(gòu)#include#include#include/ 棧方式： #include/ 向量方式：#inclu

8、deusing namespace std;11:39:0814棧方式/=intint main() ifstream in(rail.txt); forfor(intint n,line=0; inn & n & in.ignore(); ) cout(line+ ? n:); forfor(string s; getline(in, s) & s!=0; ) istringstream sin(s); stack st; forfor(intint last=0,coach; sincoach; st.pop() forfor(intint p=last+1; p=

9、coach; +p) st.push(p); if if(lastcoach) last=coach; if if(st.top()!=coach) break; coutn & n & in.ignore(); ) cout(line+ ? n:); forfor(string s; getline(in, s) & s!=0; ) istringstream sin(s); vector st; forfor(intint last=0,coach; sincoach; st.pop_back() forfor(intint p=last+1; p=coach; +

10、p) st.push_back(p); if if(lastcoach) last=coach; if if(st.back()!=coach) break; cout(!sin ? Yesn : Non); /=模仿棧操作11:39:0816結(jié)論n不同的數(shù)據(jù)結(jié)構(gòu)有不同的操作和性能n應(yīng)學(xué)習(xí)使用不同數(shù)據(jù)結(jié)構(gòu)的經(jīng)驗(yàn)11:39:08173. 算法算法 ( Algorithms )揭示：確定了數(shù)據(jù)結(jié)構(gòu)之后，所采用的算法將直接決定程序的性能；任何語(yǔ)言都有個(gè)性，算法的選擇使用是靈巧運(yùn)用語(yǔ)言的藝術(shù)，充分發(fā)揮語(yǔ)言的優(yōu)勢(shì)是活用算法的根本做法：培養(yǎng)經(jīng)驗(yàn)，用測(cè)試的辦法對(duì)算法進(jìn)行選擇11:39:0818問(wèn)題：已知不太

11、大的正整數(shù)n（n46），求Fibonacci數(shù)列 0 1 1 2 3 5 8 13 21 34 的第n項(xiàng)的值對(duì)于后面的四種算法： unsigned fibo1 (unsigned n); unsigned fibo2 (unsigned n); unsigned fibo3 (unsigned n); unsigned fibo4 (unsigned n);如何選擇其中之一 第0項(xiàng)第1項(xiàng)第2項(xiàng)11:39:0819算法：遞歸法 優(yōu)點(diǎn)：算法簡(jiǎn)單，容易編程 缺點(diǎn)：棧空間負(fù)擔(dān)過(guò)重，調(diào)用開(kāi)銷(xiāo)過(guò)大nunsigned fibo1 (unsigned n)nn if (n=1) return n;n retu

12、rn fibo1(n-1) + fibo1(n-2);nn=0或111:39:0820算法：迭代法 優(yōu)點(diǎn)：節(jié)省空間，節(jié)省時(shí)間缺點(diǎn)：編程相對(duì)復(fù)雜nunsigned fibo2 (unsigned n)nn int c=n;n for (int a=0,b=1,i=2; i=n; +i)n c=a+b, a=b, b=c;n return c;n11:39:0821算法3：向量迭代法 優(yōu)點(diǎn)：節(jié)省時(shí)間 缺點(diǎn)：n越大，占用堆空間越多nunsigned fibo3 (unsigned n)nn vector v(n+1, 0); n v1 = 1;n for (unsigned i=2; i=n; +i

13、)n vi = vi-1 + vi-2;n return vn;n11:39:0822算法4：直接計(jì)算法 優(yōu)點(diǎn)：節(jié)省時(shí)間 缺點(diǎn)：引入了浮點(diǎn)計(jì)算nunsigned fibo4 (unsigned n)nn return n ( pow ( (1+ sqrt ( 5.0 ) ) / 2, n)n pow ( (1 sqrt ( 5.0 ) ) / 2, n) )n / sqrt ( 5.0 ) ;n11:39:0823nfibo1：只在示意性編程中使用，但并不是否定一切遞歸法nfibo2：在講究性能的場(chǎng)合中使用，它省空間省時(shí)間，但在n很大的場(chǎng)合中，性能比不上fibo4nfibo3：可以數(shù)組代替向量

14、，提高低級(jí)編程的性能，它易編易用，還可以讀取中間項(xiàng)的值，但在一味追求性能的場(chǎng)合中，比不上fibo2nfibo4：在n不太大時(shí)，與fibo2相當(dāng)，在n趨向很大時(shí)，其性能優(yōu)勢(shì)便充分體現(xiàn)11:39:08244. 數(shù)值計(jì)算數(shù)值計(jì)算 ( Numerical Computation )揭示：在近似計(jì)算中，除了計(jì)算范圍與終止計(jì)算條件外，還涉及逼近的快慢，這與算法有很大關(guān)系，選擇成熟的算法具有決定性作用做法：了解各種數(shù)值計(jì)算算法的特點(diǎn)及使用場(chǎng)合，有的放矢解決實(shí)際問(wèn)題11:39:0825數(shù)值計(jì)算的參數(shù)描述template / T為賴(lài)以計(jì)算的數(shù)系 T method ( / method為某種算法T a, / 左邊

15、界T b, / 右邊界 const T Epsilon, / 終止條件 T ( * f ) ( T ) / 求值數(shù)學(xué)函數(shù));11:39:0826矩形法double rectangle(double a, double b, const double Eps, double (*f ) (double) ) double w=b-a, sN = w*( f (a) + f (b) ) / 2, sO=0; for ( int n=1; abs ( sN - sO ) = Eps; n*=2 ) sO = sN; sN = 0; for ( int i=0; i Eps; n+=n, h/=2.0

16、 ) In=I2n; Tn=T2n; / In老積分值 double sigma=0; for ( int k=0; kn; k+ ) sigma += f ( a+(k+0.5)*h ); T2n=(Tn+h*sigma)/2; I2n=(4*T2n-Tn)/3; / I2n新積分值 return I2n;小矩形求和辛普生處理前后兩次辛普生值的差11:39:0828性能比較求同樣的數(shù)學(xué)函數(shù)，區(qū)間和精度矩陣法比辛普生法多循環(huán)許多次11:39:08295. 標(biāo)準(zhǔn)標(biāo)準(zhǔn)+ 算法算法 ( Standard C+ Algorithms )揭示：標(biāo)準(zhǔn)C+提供了諸多算法，這些算法的組合構(gòu)成了許多問(wèn)題的解，對(duì)

17、算法的準(zhǔn)確了解是編程能力的一大體現(xiàn)做法：吃透標(biāo)準(zhǔn)+算法，靈活運(yùn)用之11:39:0830容器的區(qū)間表示vector a (10);/ 下面表示待處理的元素vector b (a.begin ()+1, a.begin ()+7 ); 0123456789首尾待處理的元素11:39:0831逐一讀入兩個(gè)字串，比較是否含有相同元素int main ( ) ifstream in ( string.txt ) ; for (string s,t; inst; ) 比較 輸出 yes 或 no 11:39:0832分別排序，直接加以字串比較是直截了當(dāng)?shù)乃悸罚篺or ( string s,t; inst;

18、 ) sort ( s.begin ( ), s.end ( ) ) ; sort ( t.begin ( ), t.end ( ) ) ; coutst; ) int s1=count(s.begin(), s.end(), 1); int s0=count(s.begin(), s.end(), 0); int t1=count(t.begin(), t.end(), 1); int t0=count(t.begin(), t.end(), 0); coutst; ) int s1=count ( s.begin(), s.end(), 1) ; int t1=count ( t.begi

19、n(), t.end(), 1) ; cout (s1=t1 & s.length()=t.length() ? yesn : non);C+標(biāo)準(zhǔn)算法11:39:08356. 動(dòng)態(tài)內(nèi)存動(dòng)態(tài)內(nèi)存 ( Dynamic Memory )揭示：許多問(wèn)題不知道數(shù)據(jù)量的大小，需要所運(yùn)用的數(shù)據(jù)結(jié)構(gòu)具有擴(kuò)容能力；許多問(wèn)題要求時(shí)間性能甚于空間占用充分利用堆空間(動(dòng)態(tài)內(nèi)存)是解決這些問(wèn)題的關(guān)鍵做法：理解堆空間的使用場(chǎng)合，學(xué)習(xí)堆空間的使用方法11:39:0836使用容器，便是自動(dòng)使用堆內(nèi)存例如，從abc.txt中讀取諸段落： ifstream in ( abc.txt ) ; vector ps ; / p

20、s.reserve(1100) ; 可以預(yù)留 for ( string s ; getline ( in, s ) ; ) ps.push_back(s) ;預(yù)留是減小頻繁擴(kuò)容造成的數(shù)據(jù)移動(dòng)開(kāi)銷(xiāo)11:39:0837若每個(gè)數(shù)據(jù)的處理，都要用到已經(jīng)處理的數(shù)據(jù)時(shí)，保存歷史數(shù)據(jù)，則可以改善時(shí)間性能例如，統(tǒng)計(jì)一億之內(nèi)的素?cái)?shù)個(gè)數(shù)(原始版)： bool isPrime(int n) int sqrtn=sqrt(n*1.0); for(int i=2; i=sqrtn; +i) if(n%i=0) return false; return true;/-int main() int num=0; for(i

21、nt i=2; i=100000000; +i) if(isPrime(i) num+; coutnumendl;/-11:39:0838空間換時(shí)間版int main() bitset* p = new bitset; p-set(); for(int i=2; itest(i) for(int j=i*i; jsize(); j+=i) p-reset(j); int num=0; for(int i=2; itest(i) num+; coutnum0 & scanf(%s,b)0) printf(%s, strlen(a)=strlen(b) & cnt(a)=cnt(b)? yesn : non);11:39:0841STL