【文档说明】C++程序设计教程601538精品.ppt，共(43)页，111.500 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2177.html

以下为本文档部分文字说明：

15:40:361C++程序设计教程(第二版)第六章性能Chapter6Performance清华大学出版社15:40:362◼提高性能的意义：性能对提高编程能力举足轻重◼如何提高性能？以合理使用资源为前提，尽快完成任务的能力称为效率．效率影响性能，提高效率就能提高性能◼学习目

标：1.扩展视野，对同一问题的不同要求，模仿各种编程技巧与空间布局策略，予以应对．从而对各种不同的问题，亦能应变自如2.掌握测试性能的方法，学会测算时/空交换的代价，客观评估自身的编程能力15:40:363第六章内容1.内联函数(InlineFunctions)2.数据结构(

DataStructures)3.算法(Algorithms)4.数值计算(NumericalComputation)5.STL算法(STLAlgorithms)6.动态内存(DynamicMemory)7.低级编程(Low

erProgramming)15:40:3641.内联函数(InlineFunctions)◼做法：将一些反复被执行的简单语句序列做成小函数◼用法：在函数声明前加上inline关键字◼作用：不损害可读性又能提

高性能15:40:3651.//==================================2.#include<iostream>3.boolisDigit(char);//小函数4.intmain(){5.for(charc;cin>>c&&c!='

\n';)6.if(isDigit(c))7.std::cout<<“Digit.\n";8.elsestd::cout<<“NonDigit.\n";9.}//----------------------------

-----10.boolisDigit(charch){11.returnch>='0'&&ch<='9'?1:0;12.}//=================================频繁调用的函数：用昂贵的开销换取可读性15:40:3661.

//================================2.#include<iostream>3.intmain(){4.for(charc;cin>>c&&c!='\n';)5.if(ch>='0'&&c

h<='9'?1:0)6.std::cout<<“Digit.\n";7.else8.std::cout<<“NonDigit.\n";9.}//===============================内嵌代码：开销虽少，但可读性差15:4

0:367内联方式：开销少，可读性也佳1.//==================================2.#include<iostream>◼inlineboolisDigit(char);//小函数◼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;◼}//=================================内联标记放在函数声明的前面15:40:368内联函数的使用经验：◼函数体适当小,且

无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体．如：排序函数不能内联◼程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高．如：上例中的isDigit函数◼程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增15:40:3691.

//======================================2.#include<iostream>3.#include<time>4.usingnamespacestd;5.//----------

----------------------------6.intcalc1(inta,intb){returna+b;}7.inlineintcalc2(inta,intb){returna+b;}

8.//--------------------------------------9.intmain(){10.intx[1000],y[1000],z[1000];11.clock_tt=clock

();12.for(inti=0;i<1000*1000*1000;++i)13.z[i]=calc1(x[i%1000],y[i%1000]);14.cout<<(clock()-t)/CLK_TCK<

<“withoutinline\n";15.t=clock();16.for(inti=0;i<1000*1000*1000;++i)17.z[i]=calc2(x[i%1000],y[i%1000]);18.cout

<<(clock()-t)/CLK_TCK<<“withinline\n";19.}//=====================================性能测试初记时末记时非内联函数内联函数15:40:3610结果分析：内联用与不用差很多

结论：应尽量将函数改造成可内联性质，提高性能E:\ch06>f0605↙8.281withoutinline2.437withinline15:40:36112.数据结构(DataStructures)◼揭示：将数据结构实现为数据类型是编程的高级境界，STL容器就是系统提供的现成数据结

构◼做法：充分和合理使用STL容器,简化复杂问题,提高编程效率与程序性能15:40:3612问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操作而得．例如：顺序数列1,2,3,4,5待验证序列3,2,1,5,4待验证序列5,3,4,2,115:40

:3613采用不同的数据结构#include<fstream>#include<iostream>#include<sstream>//栈方式：#include<stack>//向量方式：#include<vector>usingnamespacestd;15:40:3614栈方式//

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

trings;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");}}}//============

=================栈中若不存在读入的元素，则应入栈创建栈读入元素不在栈顶即为失败退栈即逐个逐个过15:40:3615向量方式//================================intmain(){ifstreamin("rail.txt");for(intn,lin

e=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");}}}//=================================模仿栈操作15:40:3616结论◼不同的数据结构有不同的操作和性能◼应学习使

用不同数据结构的经验15:40:36173.算法(Algorithms)揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本做法：培养经验，用测试的办法对算法进行选择15:40:3618问题：

已知不太大的正整数n（n≤46），求Fibonacci数列0112358132134……的第n项的值．对于后面的四种算法：unsignedfibo1(unsignedn);unsignedfibo2(un

signedn);unsignedfibo3(unsignedn);unsignedfibo4(unsignedn);如何选择其中之一．第0项第1项第2项15:40:3619算法１：递归法优点：算法简单，容易编程缺点：栈空间负担过重

，调用开销过大1.unsignedfibo1(unsignedn)2.{3.if(n<=1)returnn;4.returnfibo1(n-1)+fibo1(n-2);5.}n=0或115:40:3620算法２：迭代法优

点：节省空间，节省时间缺点：编程相对复杂1.unsignedfibo2(unsignedn)2.{3.intc=n;4.for(inta=0,b=1,i=2;i<=n;++i)5.c=a+b,a=b,b=c;6.returnc;7.}15:40:362

1算法3：向量迭代法优点：节省时间缺点：n越大，占用堆空间越多1.unsignedfibo3(unsignedn)2.{3.vector<unsigned>v(n+1,0);4.v[1]=1;5.for(unsignedi=2;i<=n;++i)6.v[i]=v[i-1]+v[i-2];7

.returnv[n];8.}15:40:3622算法4：直接计算法优点：节省时间缺点：引入了浮点计算1.unsignedfibo4(unsignedn)2.{3.return4.(pow((1+sqrt(5.0))/2,n)5.–pow((1–sqrt(5.0))/2,n))6./s

qrt(5.0);7.}15:40:3623fibo1：只在示意性编程中使用，但并不是否定一切递归法fibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大的场合中，性能比不上fibo4fibo3：可以数组代替

向量，提高低级编程的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2fibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现15:40:36244.数值计算(NumericalComputation)揭示：在近似计算中，除了计算范围与终止计

算条件外，还涉及逼近的快慢，这与算法有很大关系，选择成熟的算法具有决定性作用做法：了解各种数值计算算法的特点及使用场合，有的放矢解决实际问题15:40:3625数值计算的参数描述template<classT>//T为赖以计算的数系Tmethod(//meth

od为某种算法Ta,//左边界Tb,//右边界constTEpsilon,//终止条件T(*f)(T)//求值数学函数);15:40:3626矩形法doublerectangle(doublea,doubleb,constdoub

leEps,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;}小矩形逐个求和前后两次小矩形和的差15:40:3627辛普生法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=I

2n;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;}小矩形求和辛普生处理

前后两次辛普生值的差15:40:3628性能比较求同样的数学函数，区间和精度矩阵法比辛普生法多循环许多次15:40:36295.标准Ｃ++算法(StandardC++Algorithms)揭示：标准C++提供了诸多算法，这些算法的组合构成了许多问题

的解，对算法的准确了解是编程能力的一大体现做法：吃透标准Ｃ++算法，灵活运用之15:40:3630容器的区间表示P194vector<int>a(10);//下面表示待处理的元素vector<int>b(a.begin()+1,a.begin()+7);0123456789首尾待处理的元素15

:40:3631逐一读入两个０１字串，比较是否含有相同元素intmain(){ifstreamin("string.txt");for(strings,t;in>>s>>t;){比较输出yes或no}}15:40:3632分别排序

，直接加以字串比较是直截了当的思路：for(strings,t;in>>s>>t;){sort(s.begin(),s.end());sort(t.begin(),t.end());cout<<(s==t?"yes\n":"no\n");}C

++标准算法15:40:3633避免排序，分别统计两个字串中０１的个数则性能更优：(排序至少做O(nlogn)数量级运算，统计只做O(n)数量级运算)for(strings,t;in>>s>>t;){ints1=count(s.be

gin(),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++标准算法15:40:3634字串中非０即１的特征，可以避免多余的统计，进一步提高性能：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++标准算法15:40:36356.动态内存(DynamicMemory)揭示：许多问题不知道数据量的大小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用．充分利用堆空间(动态内存)是解决这些问题

的关键做法：理解堆空间的使用场合，学习堆空间的使用方法15:40:3636使用容器，便是自动使用堆内存例如，从abc.txt中读取诸段落：ifstreamin("abc.txt");vector<string>ps;//ps.re

serve(1100);可以预留for(strings;getline(in,s);)ps.push_back(s);预留是减小频繁扩容造成的数据移动开销15:40:3637若每个数据的处理，都要用到已经处理的数

据时，保存历史数据，则可以改善时间性能例如，统计一亿之内的素数个数(原始版)：boolisPrime(intn){intsqrtn=sqrt(n*1.0);for(inti=2;i<=sqrtn;++i)if(n%

i==0)returnfalse;returntrue;}//--------------------------intmain(){intnum=0;for(inti=2;i<=100000000;++i)

if(isPrime(i))num++;cout<<num<<endl;}//--------------------------15:40:3638空间换时间版intmain(){bitset<100000000>*p=newbitset<100000000>;p->se

t();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<10

0000000;++i)if(p->test(i))num++;cout<<num<<endl;delete[]p;}在空间中统计完成每个元素的标记15:40:36397.低级编程(LowerProgramming)揭示：通过无原则的代码优化来简化程序的执行步骤,从而提高性能.它会影响可读性,并

需要对程序的内存布局有深刻的了解,这一般是编程课的后继学习内容做法：尽量去掉组织程序所花费的代价:少用调用频繁的函数;通过指针间访数据;尽可能不用类;无原则数据共享;用C库不用C++库15:40:3640低级编程版：逐一读入两个０１字串，比较是否

含有相同元素intcnt(char*a){intnum=0;while(*a)if(*a++=='1')num++;returnnum;}//-----------------------------intmain(){freopen("string.txt

","r",stdin);chara[1025],b[1025];whlie(scanf("%s",a)>0&&scanf("%s",b)>0)printf("%s",strlen(a)==strlen(b)

&&cnt(a)==cnt(b)?"yes\n":"no\n");}15:40:3641STL容器是为方便编程设计的，它当然也考虑了性能，但与直接操纵堆空间相比还是间接了些例如，一亿之内的筛法求素数个数(ＳＴＬ版)：intsieveSTL(){b

itset<100000000>&p=*newbitset<100000000>;p.set();intnum=100000000-2;for(inti=2;i<=10000;++i)if(p.test(i))for(intj=i*i;j<

p.size();j+=i)if(p.test(j)&&num--)p.reset(j);delete[]&p;returnnum;}15:40:3642一亿之内的筛法求素数个数(低级编程版)：intsieve(){

unsignedint*p=(unsignedint*)malloc(12500000);memset(p,-1,12500000);intnum=100000000-2;for(inti=2;i<=10000;++i)if(p[i/32]&(1<<i%32))for(intj=i*i;j

<100000000;j+=i)if(p[j/32]&(1<<j%32)&&num--)p[j/32]&=~(1<<j%32);free(p);returnnum;}15:40:3643低级编程与高级编程的差异低级编

程与高级编程的差异在代码量上能够一定程度地反映出来，但根本的差异在于使用编程语句的抽象性程度．代码越抽象，其内在的数据与操作的安全性考虑得越多，因而额外开销就越大．反之，代码越低级，对数据的操作越直接，越需要程序员亲自驾驭程序的整体安全控制