14:38:371C++程序設(shè)計(jì)教程(第二版)第六章性能Chapter6

Performance

14:38:372提高性能的意義：

性能對(duì)提高編程能力舉足輕重如何提高性能？

以合理使用資源為前提，盡快完成任務(wù)的能力稱(chēng)為效率．效率影響性能，提高效率就能提高性能學(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)估自身的編程能力14:38:373第六章內(nèi)容

內(nèi)聯(lián)函數(shù)(InlineFunctions)

數(shù)據(jù)結(jié)構(gòu)(DataStructures)

算法(Algorithms)

數(shù)值計(jì)算(NumericalComputation)STL算法(STLAlgorithms)

動(dòng)態(tài)內(nèi)存(DynamicMemory)

低級(jí)編程(LowerProgramming)

14:38:3741.內(nèi)聯(lián)函數(shù)(InlineFunctions)做法：將一些反復(fù)被執(zhí)行的簡(jiǎn)單語(yǔ)句序列做成小函數(shù)用法：在函數(shù)聲明前加上inline關(guān)鍵字作用：不損害可讀性又能提高性能14:38:375//==================================#include<iostream>boolisDigit(char);//小函數(shù)intmain(){

for(charc;cin>>c&&c!='\n';)

if(isDigit(c))std::cout<<“Digit.\n";

elsestd::cout<<“NonDigit.\n";}//---------------------------------boolisDigit(charch){

returnch>='0'&&ch<='9'?1:0;}//=================================頻繁調(diào)用的函數(shù)：用昂貴的開(kāi)銷(xiāo)換取可讀性14:38:376//================================#include<iostream>intmain(){

for(charc;cin>>c&&c!='\n';)

if(ch>='0'&&ch<='9'?1:0)std::cout<<“Digit.\n";

else

std::cout<<“NonDigit.\n";}//===============================內(nèi)嵌代碼：開(kāi)銷(xiāo)雖少，但可讀性差14:38:377內(nèi)聯(lián)方式：開(kāi)銷(xiāo)少，可讀性也佳//==================================#include<iostream>inlineboolisDigit(char);//小函數(shù)intmain(){

for(charc;cin>>c&&c!='\n';)

if(isDigit(c))std::cout<<"Digit.\n";

else

std::cout<<"NonDigit.\n";}//---------------------------------boolisDigit(charch){

returnch>='0'&&ch<='9'?1:0;}//=================================內(nèi)聯(lián)標(biāo)記放在函數(shù)聲明的前面14:38:378內(nèi)聯(lián)函數(shù)的使用經(jīng)驗(yàn)：函數(shù)體適當(dāng)小,且無(wú)循環(huán)或開(kāi)關(guān)語(yǔ)句，這樣就使嵌入工作容易進(jìn)行，不會(huì)破壞原調(diào)用主體．如：排序函數(shù)不能內(nèi)聯(lián)程序中特別是在循環(huán)中反復(fù)執(zhí)行該函數(shù)，這樣就使嵌入的代碼利用率較高．如：上例中的isDigit函數(shù)程序并不多處出現(xiàn)該函數(shù)調(diào)用，這樣就使嵌入工作量相對(duì)較少，代碼量也不會(huì)劇增14:38:379//======================================#include<iostream>#include<time>usingnamespacestd;//--------------------------------------intcalc1(inta,intb){returna+b;}inlineintcalc2(inta,intb){returna+b;}//--------------------------------------intmain(){

intx[1000],y[1000],z[1000];clock_tt=clock();

for(inti=0;i<1000*1000*1000;++i)z[i]=calc1(x[i%1000],y[i%1000]);cout<<(clock()-t)/CLK_TCK<<“withoutinline\n";t=clock();

for(inti=0;i<1000*1000*1000;++i)z[i]=calc2(x[i%1000],y[i%1000]);cout<<(clock()-t)/CLK_TCK<<“withinline\n";}//=====================================性能測(cè)試初記時(shí)末記時(shí)非內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)14:38:3710結(jié)果分析：內(nèi)聯(lián)用與不用差很多結(jié)論：應(yīng)盡量將函數(shù)改造成可內(nèi)聯(lián)性質(zhì)，提高性能E:\ch06>f0605↙8.281withoutinline2.437withinline14:38:37112.數(shù)據(jù)結(jié)構(gòu)(DataStructures)揭示：將數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)為數(shù)據(jù)類(lèi)型是編程的高級(jí)境界，STL容器就是系統(tǒng)提供的現(xiàn)成數(shù)據(jù)結(jié)構(gòu)做法：充分和合理使用STL容器,簡(jiǎn)化復(fù)雜問(wèn)題,提高編程效率與程序性能14:38:3712問(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,114:38:3713采用不同的數(shù)據(jù)結(jié)構(gòu)#include<fstream>#include<iostream>#include<sstream>//棧方式：

#include<stack>//向量方式：#include<vector>usingnamespacestd;14:38:3714棧方式//=============================intmain(){ifstreamin("rail.txt");

for(intn,line=0;in>>n&&n&&in.ignore();){cout<<(line++?"\n":"");

for(strings;getline(in,s)&&s!="0";){istringstreamsin(s);stack<int>st;

for(intlast=0,coach;sin>>coach;st.pop()){

for(intp=last+1;p<=coach;++p)st.push(p);

if(last<coach)last=coach;

if(st.top()!=coach)break;}cout<<(!sin?"Yes\n":"No\n");}}}//=============================棧中若不存在讀入的元素，則應(yīng)入棧創(chuàng)建棧讀入元素不在棧頂即為失敗退棧即逐個(gè)逐個(gè)過(guò)14:38:3715向量方式//================================intmain(){ifstreamin("rail.txt");

for(intn,line=0;in>>n&&n&&in.ignore();){cout<<(line++?"\n":"");

for(strings;getline(in,s)&&s!="0";){istringstreamsin(s);vector<int>st;

for(intlast=0,coach;sin>>coach;st.pop_back())){

for(intp=last+1;p<=coach;++p)st.push_back(p);

if(last<coach)last=coach;

if(st.back()!=coach)break;}cout<<(!sin?"Yes\n":"No\n");}}}//=================================模仿棧操作14:38:3716結(jié)論不同的數(shù)據(jù)結(jié)構(gòu)有不同的操作和性能應(yīng)學(xué)習(xí)使用不同數(shù)據(jù)結(jié)構(gòu)的經(jīng)驗(yàn)14:38:37173.算法(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)行選擇14:38:3718問(wèn)題：已知不太大的正整數(shù)n（n≤46），求Fibonacci數(shù)列

0112358132134……的第n項(xiàng)的值．對(duì)于后面的四種算法：

unsignedfibo1(unsignedn);unsignedfibo2(unsignedn);unsignedfibo3(unsignedn);unsignedfibo4(unsignedn);如何選擇其中之一．第0項(xiàng)第1項(xiàng)第2項(xiàng)14:38:3719算法１：遞歸法

優(yōu)點(diǎn)：算法簡(jiǎn)單，容易編程

缺點(diǎn)：?？臻g負(fù)擔(dān)過(guò)重，調(diào)用開(kāi)銷(xiāo)過(guò)大unsignedfibo1(unsignedn){

if(n<=1)returnn;returnfibo1(n-1)+fibo1(n-2);}n=0或114:38:3720算法２：迭代法

優(yōu)點(diǎn)：節(jié)省空間，節(jié)省時(shí)間

缺點(diǎn)：編程相對(duì)復(fù)雜unsignedfibo2(unsignedn){

intc=n;

for(inta=0,b=1,i=2;i<=n;++i)c=a+b,a=b,b=c;

returnc;}14:38:3721算法3：向量迭代法

優(yōu)點(diǎn)：節(jié)省時(shí)間

缺點(diǎn)：n越大，占用堆空間越多unsignedfibo3(unsignedn){vector<unsigned>v(n+1,0);v[1]=1;

for(unsignedi=2;i<=n;++i)v[i]=v[i-1]+v[i-2];

returnv[n];}14:38:3722算法4：直接計(jì)算法

優(yōu)點(diǎn)：節(jié)省時(shí)間

缺點(diǎn)：引入了浮點(diǎn)計(jì)算unsignedfibo4(unsignedn){

return

(pow((1+sqrt(5.0))/2,n)–pow((1–sqrt(5.0))/2,n))/sqrt(5.0);}14:38:3723fibo1：只在示意性編程中使用，但并不是否定一切遞歸法fibo2：在講究性能的場(chǎng)合中使用，它省空間省時(shí)間，但在n很大的場(chǎng)合中，性能比不上fibo4fibo3：可以數(shù)組代替向量，提高低級(jí)編程的性能，它易編易用，還可以讀取中間項(xiàng)的值，但在一味追求性能的場(chǎng)合中，比不上fibo2fibo4：在n不太大時(shí)，與fibo2相當(dāng)，在n趨向很大時(shí)，其性能優(yōu)勢(shì)便充分體現(xiàn)14:38:37244.數(shù)值計(jì)算(NumericalComputation)揭示：在近似計(jì)算中，除了計(jì)算范圍與終止計(jì)算條件外，還涉及逼近的快慢，這與算法有很大關(guān)系，選擇成熟的算法具有決定性作用做法：了解各種數(shù)值計(jì)算算法的特點(diǎn)及使用場(chǎng)合，有的放矢解決實(shí)際問(wèn)題14:38:3725數(shù)值計(jì)算的參數(shù)描述template<classT>//T為賴(lài)以計(jì)算的數(shù)系

Tmethod(//method為某種算法

Ta,//左邊界

Tb,

//右邊界

constTEpsilon,//終止條件

T(*f)(T)

//求值數(shù)學(xué)函數(shù));14:38:3726矩形法doublerectangle(doublea,doubleb,constdoubleEps,double(*f)(double)){

doublew=b-a,sN=w*(f(a)+f(b))/2,sO=0;

for(intn=1;abs(sN-sO)>=Eps;n*=2){sO=sN;sN=0;

for(inti=0;i<n;++i)sN+=f(a+w*(i+0.5)/n);sN*=w/n;}

returnsN;}小矩形逐個(gè)求和前后兩次小矩形和的差14:38:3727辛普生法

doublesimpson(doublea,doubleb,

constdoubleEps,double(*f)(double)){

doubleI2n=0,h=b-a,T2n=h*(f(a)+f(b))/2,In=T2n,Tn;

for(intn=1;abs(I2n–In)>Eps;n+=n,h/=2.0){In=I2n;Tn=T2n;//In老積分值

doublesigma=0;

for(intk=0;k<n;k++)sigma+=f(a+(k+0.5)*h);T2n=(Tn+h*sigma)/2;I2n=(4*T2n-Tn)/3;//I2n新積分值

}

returnI2n;}小矩形求和辛普生處理前后兩次辛普生值的差14:38:3728性能比較求同樣的數(shù)學(xué)函數(shù)，區(qū)間和精度矩陣法比辛普生法多循環(huán)許多次14:38:37295.標(biāo)準(zhǔn)Ｃ++算法(StandardC++Algorithms)揭示：標(biāo)準(zhǔn)C++提供了諸多算法，這些算法的組合構(gòu)成了許多問(wèn)題的解，對(duì)算法的準(zhǔn)確了解是編程能力的一大體現(xiàn)做法：吃透標(biāo)準(zhǔn)Ｃ++算法，靈活運(yùn)用之14:38:3730容器的區(qū)間表示vector<int>a(10);//下面表示待處理的元素vector<int>b(a.begin()+1,a.begin()+7);0123456789首尾待處理的元素14:38:3731逐一讀入兩個(gè)０１字串，比較是否含有相同元素intmain(){ifstreamin("string.txt");

for(strings,t;in>>s>>t;){

比較輸出yes

或no}}14:38:3732分別排序，直接加以字串比較是直截了當(dāng)?shù)乃悸罚篺or(strings,t;in>>s>>t;){sort(s.begin(),s.end());sort(t.begin(),t.end());cout<<(s==t?"yes\n":"no\n");}C++標(biāo)準(zhǔn)算法14:38:3733避免排序，分別統(tǒng)計(jì)兩個(gè)字串中０１的個(gè)數(shù)則性能更優(yōu)：

(排序至少做O(nlogn)數(shù)量級(jí)運(yùn)算，統(tǒng)計(jì)只做O(n)數(shù)量級(jí)運(yùn)算)for(strings,t;in>>s>>t;){

ints1=count(s.begin(),s.end(),’1’);

ints0=count(s.begin(),s.end(),’0’);

intt1=count(t.begin(),t.end(),’1’);

intt0=count(t.begin(),t.end(),’0’);cout<<(s1==t1&&s0==t0?"yes\n":"no\n");}C++標(biāo)準(zhǔn)算法14:38:3734字串中非０即１的特征，可以避免多余的統(tǒng)計(jì)，進(jìn)一步提高性能：for(strings,t;in>>s>>t;){

ints1=count(s.begin(),s.end(),’1’);

intt1=count(t.begin(),t.end(),’1’);cout<<(s1==t1&&s.length()==t.length()?"yes\n":"no\n");}C++標(biāo)準(zhǔn)算法14:38:37356.動(dòng)態(tài)內(nèi)存(DynamicMemory)揭示：許多問(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í)堆空間的使用方法14:38:3736使用容器，便是自動(dòng)使用堆內(nèi)存例如，從abc.txt中讀取諸段落：

ifstreamin("abc.txt");vector<string>ps;

//ps.reserve(1100);可以預(yù)留

for(strings;getline(in,s);)ps.push_back(s);預(yù)留是減小頻繁擴(kuò)容造成的數(shù)據(jù)移動(dòng)開(kāi)銷(xiāo)14:38:3737若每個(gè)數(shù)據(jù)的處理，都要用到已經(jīng)處理的數(shù)據(jù)時(shí)，保存歷史數(shù)據(jù)，則可以改善時(shí)間性能例如，統(tǒng)計(jì)一億之內(nèi)的素?cái)?shù)個(gè)數(shù)(原始版)：

boolisPrime(intn){

intsqrtn=sqrt(n*1.0);

for(inti=2;i<=sqrtn;++i)

if(n%i==0)returnfalse;

return

true;}//--------------------------intmain(){

intnum=0;

for(inti=2;i<=100000000;++i)

if(isPrime(i))num++;cout<<num<<endl;}//--------------------------14:38:3738空間換時(shí)間版intmain(){bitset<100000000>*p=newbitset<100000000>;p->set();

for(inti=2;i<=10000;++i)

if(p->test(i))

for(intj=i*i;j<p->size();j+=i)p->reset(j);

intnum=0;

for(inti=2;i<100000000;++i)

if(p->test(i))num++;cout<<num<<endl;

delete[]p;}在空間中統(tǒng)計(jì)完成每個(gè)元素的標(biāo)記14:38:37397.低級(jí)編程(LowerProgramming)揭示：通過(guò)無(wú)原則的代碼優(yōu)化來(lái)簡(jiǎn)化程序的執(zhí)行步驟,從而提高性能.它會(huì)影響可讀性,并需要對(duì)程序的內(nèi)存布局有深刻的了解,這一般是編程課的后繼學(xué)習(xí)內(nèi)容做法：盡量去掉組織程序所花費(fèi)的代價(jià):少用調(diào)用頻繁的函數(shù);通過(guò)指針間訪(fǎng)數(shù)據(jù);盡可能不用類(lèi);無(wú)原則數(shù)據(jù)共享;用C庫(kù)不用C++庫(kù)14:38:3740低級(jí)編程版：

逐一讀入兩個(gè)０１字串，比較是否含有相同元素intcnt(char*a){

intnum=0;

while(*a)if(*a++=='1')num++;

returnnum;}//----