《C++程序设计教程 第六章 性能》由会员分享，可在线阅读，更多相关《C++程序设计教程 第六章 性能（43页珍藏版）》请在金锄头文库上搜索。
1、C+程序设计教程(第二版)第六章 性能 Chapter 6 Performance 清华大学出版社 钱 能7/31/20241n提高性能的意义： 性能对提高编程能力举足轻重n如何提高性能？ 以合理使用资源为前提，尽快完成任务的能力称为效率效率影响性能，提高效率就能提高性能n学习目标： 1. 扩展视野，对同一问题的不同要求，模仿各种编程技巧与空间布局策略，予以应对从而对各种不同的问题，亦能应变自如 2. 掌握测试性能的方法，学会测算时/空交换的代价，客观评估自身的编程能力7/31/20242第六章内容1. 内联函数内联函数 ( Inline Functions ) 2. 数据结构数据结构 ( D
2、ata Structures ) 3. 算法算法 ( Algorithms ) 4. 数值计算数值计算 ( Numerical Computation )5. STL算法算法 ( STL Algorithms ) 6. 动态内存动态内存 ( Dynamic Memory ) 7. 低级编程低级编程 ( Lower Programming ) 7/31/202431. 内联函数内联函数 ( Inline Functions )n做法：将一些反复被执行的简单语句序列做成小函数n用法：在函数声明前加上inline关键字n作用：不损害可读性又能提高性能7/31/202441./=2.#include3
3、.3.boolbool isDigit(charchar); / 小函数4.4.intint 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./=频繁调用的函数：用昂贵的开销换取可读性7/31/202451./=2.#include3.3.intint main( )4. forfor(charchar c; cinc & c!=n; )5. ifif(ch=0 & ch=9 ? 1 : 0)6.
4、std:cout“Digit.n;7. elseelse 8. std:cout“NonDigit.n;9./=内嵌代码：开销虽少，但可读性差7/31/20246内联方式：开销少，可读性也佳1./=2.#includeninline inline boolbool 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/=内联标记放在函数声明的前面7/
5、31/20247内联函数的使用经验：n函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体如：排序函数不能内联n程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高如：上例中的isDigit函数n程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增 7/31/202481./=2.#include3.#include4.4.using namespaceusing namespace std;5./-6.6.intint calc1(intint a, intint b) returnreturn a+b; 7.7.inline inl
6、ine intint calc2(intint a, intint b) returnreturn a+b; 8./-9.9.intint main()10. intint x1000, y1000, z1000;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
7、*1000; +i)17. zi = calc2(xi%1000, yi%1000);18. cout(clock()-t)/CLK_TCKf0605 8.281 without inline2.437 with inline7/31/2024102. 数据结构数据结构 ( Data Structures )n揭示：将数据结构实现为数据类型是编程的高级境界，STL容器就是系统提供的现成数据结构n做法：充分和合理使用STL容器,简化复杂问题,提高编程效率与程序性能7/31/202411问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操作而得 例如：顺序数列 1,2,3,4,5 待验证序
8、列 3,2,1,5,4 待验证序列 5,3,4,2,17/31/202412采用不同的数据结构#include#include#include/ 栈方式： #include/ 向量方式：#includeusing namespace std;7/31/202413栈方式/=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
9、(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) break; coutn & n & in.ignore(); ) cout(line+ ? n:); forfor(string s; getline(in, s) & s!=0; ) istringstream sin(s); vector st; forfor(int
10、int 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); /=模仿栈操作7/31/202415结论n不同的数据结构有不同的操作和性能n应学习使用不同数据结构的经验7/31/2024163. 算法算法 ( Algorithms )揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言
11、都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本做法：培养经验，用测试的办法对算法进行选择7/31/202417问题：已知不太大的正整数n（n46），求Fibonacci数列 0 1 1 2 3 5 8 13 21 34 的第n项的值对于后面的四种算法： unsigned fibo1 (unsigned n); unsigned fibo2 (unsigned n); unsigned fibo3 (unsigned n); unsigned fibo4 (unsigned n);如何选择其中之一 第0项第1项第2项7/31/202418算法：递归法 优点：算法
12、简单，容易编程 缺点：栈空间负担过重，调用开销过大1.unsigned fibo1 (unsigned n)2.3. if (n=1) return n;4. return fibo1(n-1) + fibo1(n-2);5.n=0或17/31/202419算法：迭代法 优点：节省空间，节省时间缺点：编程相对复杂1.unsigned fibo2 (unsigned n)2.3. int c=n;4. for (int a=0,b=1,i=2; i=n; +i)5. c=a+b, a=b, b=c;6. return c;7.7/31/202420算法3：向量迭代法 优点：节省时间 缺点：n越大
13、，占用堆空间越多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.7/31/202421算法4：直接计算法 优点：节省时间 缺点：引入了浮点计算1.unsigned fibo4 (unsigned n)2.3. return 4. ( pow ( (1+ sqrt ( 5.0 ) ) / 2, n)5. pow ( (1 sqrt ( 5.0 ) ) / 2, n) )6. / sqrt (
14、5.0 ) ;7.7/31/202422fibo1：只在示意性编程中使用，但并不是否定一切递归法fibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大的场合中，性能比不上fibo4fibo3：可以数组代替向量，提高低级编程的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2fibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现7/31/2024234. 数值计算数值计算 ( Numerical Computation )揭示：在近似计算中，除了计算范围与终止计算条件外，还涉及逼近的快慢，这与算法有很大关系，选择成熟的算法具有决定
15、性作用做法：了解各种数值计算算法的特点及使用场合，有的放矢解决实际问题7/31/202424数值计算的参数描述template / T为赖以计算的数系 T method ( / method为某种算法T a, / 左边界T b, / 右边界 const T Epsilon, / 终止条件 T ( * f ) ( T ) / 求值数学函数);7/31/202425矩形法double rectangle(double a, double b, const double Eps, double (*f ) (double) ) double w=b-a, sN = w*( f (a) + f (b)
16、 ) / 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 ) 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;小矩形求和辛普生处理前后两次辛普生值的差7/31/202427性能比较
17、求同样的数学函数，区间和精度矩阵法比辛普生法多循环许多次7/31/2024285. 标准标准+ 算法算法 ( Standard C+ Algorithms )揭示：标准C+提供了诸多算法，这些算法的组合构成了许多问题的解，对算法的准确了解是编程能力的一大体现做法：吃透标准+算法，灵活运用之7/31/202429容器的区间表示vector a (10);/ 下面表示待处理的元素vector b (a.begin ()+1, a.begin ()+7 ); 0123456789首尾待处理的元素7/31/202430逐一读入两个字串，比较是否含有相同元素int main ( ) ifstream i
18、n ( string.txt ) ; for (string s,t; inst; ) 比较 输出 yes 或 no 7/31/202431分别排序，直接加以字串比较是直截了当的思路：for ( string s,t; inst; ) 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(
19、), 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() ? yesn : non);C+标准算法7/31/2024346. 动态内存动态内存 ( Dynamic Memory )揭示：许多问题不知道数据量的大小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用充分利用堆空间(动态内存)是解决这些问
20、题的关键做法：理解堆空间的使用场合，学习堆空间的使用方法7/31/202435使用容器，便是自动使用堆内存例如，从abc.txt中读取诸段落： ifstream in ( abc.txt ) ; vector ps ; / ps.reserve(1100) ; 可以预留 for ( string s ; getline ( in, s ) ; ) ps.push_back(s) ;预留是减小频繁扩容造成的数据移动开销7/31/202436若每个数据的处理，都要用到已经处理的数据时，保存历史数据，则可以改善时间性能例如，统计一亿之内的素数个数(原始版)： bool isPrime(int n)
21、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;/-7/31/202437空间换时间版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); in
22、t 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);7/31/202440STL容器是为方便编程设计的，它当然也考虑了性能，但与直接操纵堆空间相比还是间接了些例如，一亿之内的筛法求素数个数(版)： int sieveSTL() bitset& p = *new bitset; p.set(); int num=100000000-2; for(int i=2; i=10000; +i) if(p.test
23、(i) for(int j=i*i; jp.size(); j+=i) if(p.test(j) & num-) p.reset(j); delete &p; return num;7/31/202441一亿之内的筛法求素数个数(低级编程版)： 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;7/31/202442低级编程与高级编程的差异低级编程与高级编程的差异在代码量上能够一定程度地反映出来，但根本的差异在于使用编程语句的抽象性程度代码越抽象，其内在的数据与操作的安全性考虑得越多，因而额外开销就越大反之，代码越低级，对数据的操作越直接，越需要程序员亲自驾驭程序的整体安全控制7/31/202443
