C++程序设计教程601538精品.ppt

1、11:28:401C+程序设计教程(第二版)第六章 性能 Chapter 6 Performance 清华大学出版社 11:28:412n提高性能的意义：性能对提高编程能力举足轻重n如何提高性能？以合理使用资源为前提，尽快完成任务的能力称为效率效率影响性能，提高效率就能提高性能n学习目标：1.扩展视野，对同一问题的不同要求，模仿各种编程技巧与空间布局策略，予以应对从而对各种不同的问题，亦能应变自如 2.掌握测试性能的方法，学会测算时/空交换的代价，客观评估自身的编程能力11:28:413第六章内容1.内联函数内联函数(Inline Functions)2.数据结构数据结构(Data Struc

2、tures)3.算法算法(Algorithms)4.数值计算数值计算(Numerical Computation)5.STL算法算法(STL Algorithms)6.动态内存动态内存(Dynamic Memory)7.低级编程低级编程(Lower Programming)11:28:4141.内联函数内联函数(Inline Functions)n做法：将一些反复被执行的简单语句序列做成小函数n用法：在函数声明前加上inline关键字n作用：不损害可读性又能提高性能11:28:4151./=2.#include3.3.boolbool isDigit(charchar);/小函数4.4.int

3、int main()5.forfor(charchar c;cinc&c!=n;)6.ifif(isDigit(c)7.std:cout“Digit.n;8.elseelse std:cout=0&ch=9?1:0;12./=频繁调用的函数：用昂贵的开销换取可读性11:28:4161./=2.#include3.3.intint main()4.forfor(charchar c;cinc&c!=n;)5.ifif(ch=0&ch=9?1:0)6.std:cout“Digit.n;7.elseelse 8.std:cout“NonDigit.n;9./=内嵌代码：开销虽少，但可读性差11:28

4、:417内联方式：开销少，可读性也佳1./=2.#includeninline boolinline bool isDigit(charchar);/小函数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/=内联标记放在函数声明的前面11:28:418内联函数的使用经验：n函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体如：排序函数不能内联n程序中特别是在循环中反复执行该函数，这样就使嵌

5、入的代码利用率较高如：上例中的isDigit函数n程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增 11:28:4191./=2.#include3.#include4.4.using namespaceusing namespace std;5./-6.6.intint calc1(intint a,intint b)returnreturn a+b;7.7.inline intinline int calc2(intint a,intint b)returnreturn a+b;8./-9.9.intint main()10.intint x1000,y1000,z

6、1000;11.clock_t t=clock();12.forfor(intint i=0;i1000*1000*1000;+i)13.zi=calc1(xi%1000,yi%1000);14.cout(clock()-t)/CLK_TCK“without inlinen;15.t=clock();16.forfor(intint i=0;i1000*1000*1000;+i)17.zi=calc2(xi%1000,yi%1000);18.cout(clock()-t)/CLK_TCKf0605 8.281 without inline2.437 with inline11:28:42112

7、.数据结构数据结构(Data Structures)n揭示：将数据结构实现为数据类型是编程的高级境界，STL容器就是系统提供的现成数据结构n做法：充分和合理使用STL容器,简化复杂问题,提高编程效率与程序性能11:28:4212问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操作而得 例如：顺序数列 1,2,3,4,5 待验证序列 3,2,1,5,4 待验证序列 5,3,4,2,111:28:4213采用不同的数据结构#include#include#include/栈方式：#include/向量方式：#includeusing namespace std;11:28:4214栈方式

8、/=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=coach;+p)st.push(p);if if(lastcoach)last=coach;if if(st.top()!=coach)br

9、eak;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;+p)st.push_back(p);if if(lastcoach)last=coach;if if(st.back()!=coach)break;cout(!sin?Yesn:Non);/=模仿栈操作11:28:4216结

10、论n不同的数据结构有不同的操作和性能n应学习使用不同数据结构的经验11:28:42173.算法算法(Algorithms)揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本做法：培养经验，用测试的办法对算法进行选择11:28:4218问题：已知不太大的正整数n（n46），求Fibonacci数列 0 1 1 2 3 5 8 13 21 34 的第n项的值对于后面的四种算法：unsigned fibo1(unsigned n);unsigned fibo2(unsigned n);unsigned

11、fibo3(unsigned n);unsigned fibo4(unsigned n);如何选择其中之一 第0项第1项第2项11:28:4219算法：递归法 优点：算法简单，容易编程 缺点：栈空间负担过重，调用开销过大1.unsigned fibo1(unsigned n)2.3.if(n=1)return n;4.return fibo1(n-1)+fibo1(n-2);5.n=0或111:28:4220算法：迭代法 优点：节省空间，节省时间缺点：编程相对复杂1.unsigned fibo2(unsigned n)2.3.int c=n;4.for(int a=0,b=1,i=2;i=n;

12、+i)5.c=a+b,a=b,b=c;6.return c;7.11:28:4221算法3：向量迭代法 优点：节省时间 缺点：n越大，占用堆空间越多1.unsigned fibo3(unsigned n)2.3.vector v(n+1,0);4.v1=1;5.for(unsigned i=2;i=n;+i)6.vi=vi-1+vi-2;7.return vn;8.11:28:4222算法4：直接计算法 优点：节省时间 缺点：引入了浮点计算1.unsigned fibo4(unsigned n)2.3.return 4.(pow(1+sqrt(5.0)/2,n)5.pow(1 sqrt(5.0

13、)/2,n)6./sqrt(5.0);7.11:28:4223fibo1：只在示意性编程中使用，但并不是否定一切递归法fibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大的场合中，性能比不上fibo4fibo3：可以数组代替向量，提高低级编程的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2fibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现11:28:42244.数值计算数值计算(Numerical Computation)揭示：在近似计算中，除了计算范围与终止计算条件外，还涉及逼近的快慢，这与算法有很大关系，选择成熟的

14、算法具有决定性作用做法：了解各种数值计算算法的特点及使用场合，有的放矢解决实际问题11:28:4225数值计算的参数描述template /T为赖以计算的数系 T method(/method为某种算法T a,/左边界T b,/右边界 const T Epsilon,/终止条件 T(*f)(T)/求值数学函数);11:28:4226矩形法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)=E

15、ps;n*=2)sO=sN;sN=0;for(int i=0;i Eps;n+=n,h/=2.0)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:28:4328性能比较求同样的数学函数，区间和精度矩阵法比辛普生法多循环许多次11:28:43295.标准标准+算法算法(Standard C+Algorithms)揭示：标准C+提供了诸多

16、算法，这些算法的组合构成了许多问题的解，对算法的准确了解是编程能力的一大体现做法：吃透标准+算法，灵活运用之11:28:4330容器的区间表示 P194vector a(10);/下面表示待处理的元素vector b(a.begin()+1,a.begin()+7);0123456789首尾待处理的元素11:28:4331逐一读入两个字串，比较是否含有相同元素int main()ifstream in(string.txt);for(string s,t;inst;)比较 输出 yes 或 no 11:28:4332分别排序，直接加以字串比较是直截了当的思路：for(string s,t;in

17、st;)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.begin(),t.end(),1);cout(s1=t1&s.length()=t.length

18、()?yesn:non);C+标准算法11:28:43356.动态内存动态内存(Dynamic Memory)揭示：许多问题不知道数据量的大小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用充分利用堆空间(动态内存)是解决这些问题的关键做法：理解堆空间的使用场合，学习堆空间的使用方法11:28:4336使用容器，便是自动使用堆内存例如，从abc.txt中读取诸段落：ifstream in(abc.txt);vector ps;/ps.reserve(1100);可以预留 for(string s;getline(in,s);)ps.push_back(s);预留是减小频繁扩

19、容造成的数据移动开销11:28:4337若每个数据的处理，都要用到已经处理的数据时，保存历史数据，则可以改善时间性能例如，统计一亿之内的素数个数(原始版)：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(int i=2;i=100000000;+i)if(isPrime(i)num+;coutnumendl;/-11:28:4338空间换时间版int main()bitset*p=new bits

20、et;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:28:4341STL容器是为方便编程设计的，它当然也考虑了性能，但与直接操纵堆空间相比还是间接了些例如，一亿之内的筛法求素数个数(版)：int sieveSTL()bitset&p=*new bitset;p.set();int nu

21、m=100000000-2;for(int i=2;i=10000;+i)if(p.test(i)for(int j=i*i;jp.size();j+=i)if(p.test(j)&num-)p.reset(j);delete&p;return num;11:28:4342一亿之内的筛法求素数个数(低级编程版)：int sieve()unsigned int*p=(unsigned int*)malloc(12500000);memset(p,-1,12500000);int num=100000000-2;for(int i=2;i=10000;+i)if(pi/32&(1i%32)for(int j=i*i;j100000000;j+=i)if(pj/32&(1j%32)&num-)pj/32&=(1j%32);free(p);return num;11:28:4343低级编程与高级编程的差异低级编程与高级编程的差异在代码量上能够一定程度地反映出来，但根本的差异在于使用编程语句的抽象性程度代码越抽象，其内在的数据与操作的安全性考虑得越多，因而额外开销就越大反之，代码越低级，对数据的操作越直接，越需要程序员亲自驾驭程序的整体安全控制