C程序设计教程课件

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

2、ne Functions ) n 数据结构数据结构 ( Data Structures ) n 算法算法 ( Algorithms ) n 数值计算数值计算 ( Numerical Computation )n STL算法算法 ( STL Algorithms ) n 动态内存动态内存 ( Dynamic Memory ) n 低级编程低级编程 ( Lower Programming ) 11/20/2021C程序设计教程PPT课件41. 内联函数内联函数 ( Inline Functions )n做法：将一些反复被执行的简单语句序列做成小函数n用法：在函数声明前加上inline关键字n作用：

3、不损害可读性又能提高性能11/20/2021C程序设计教程PPT课件5n/=n#includenboolbool isDigit(charchar); / 小函数nintint main( )n forfor(charchar c; cinc & c!=n; )n ifif(isDigit(c) n std:cout“Digit.n;n elseelse std:cout=0 & ch=9 ? 1 : 0;n/=频繁调用的函数：用昂贵的开销换取可读性11/20/2021C程序设计教程PPT课件6n/=n#includenintint main( )n forfor(charch

4、ar c; cinc & c!=n; )n ifif(ch=0 & ch=9 ? 1 : 0)n std:cout“Digit.n;n elseelse n std:cout“NonDigit.n;n/=内嵌代码：开销虽少，但可读性差11/20/2021C程序设计教程PPT课件7内联方式：开销少，可读性也佳n/=n#includeninline inline boolbool isDigit(charchar); / 小函数nintint main( )n forfor(charchar c; cinc & c!=n; )n ifif(isDigit(c) n std:

5、coutDigit.n;n elseelse n std:cout=0 & ch=9 ? 1 : 0;n/=内联标记放在函数声明的前面11/20/2021C程序设计教程PPT课件8内联函数的使用经验：n函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体如：排序函数不能内联n程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高如：上例中的isDigit函数n程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增 11/20/2021C程序设计教程PPT课件9n/=n#includen#includenusing namespace

6、using 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 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)/C

7、LK_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 inline2.437 with inline11/20/2021C程序设计教程PPT课件112. 数据结构数据结构 ( Data Structures )n揭示：将数据结构实现为数据类型是编程的高级境界，STL容器就是系统提供的现成数据结构n做法：充分和合理使用STL容器,简化复杂问题,提

8、高编程效率与程序性能11/20/2021C程序设计教程PPT课件12问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操作而得 例如：顺序数列 1,2,3,4,5 待验证序列 3,2,1,5,4 待验证序列 5,3,4,2,111/20/2021C程序设计教程PPT课件13采用不同的数据结构#include#include#include/ 栈方式： #include/ 向量方式：#includeusing namespace std;11/20/2021C程序设计教程PPT课件14栈方式/=intint main() ifstream in(rail.txt); forfor(int

9、int 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) break; co

10、utn & 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

11、(!sin ? Yesn : Non); /=模仿栈操作11/20/2021C程序设计教程PPT课件16结论n不同的数据结构有不同的操作和性能n应学习使用不同数据结构的经验11/20/2021C程序设计教程PPT课件173. 算法算法 ( Algorithms )n揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本n做法：培养经验，用测试的办法对算法进行选择11/20/2021C程序设计教程PPT课件18问题：已知不太大的正整数n（n46），求Fibonacci数列 0 1 1 2 3 5 8 1

12、3 21 34 的第n项的值对于后面的四种算法： unsigned fibo1 (unsigned n); unsigned fibo2 (unsigned n); unsigned fibo3 (unsigned n); unsigned fibo4 (unsigned n);如何选择其中之一 第0项第1项第2项11/20/2021C程序设计教程PPT课件19算法：递归法 优点：算法简单，容易编程 缺点：栈空间负担过重，调用开销过大nunsigned fibo1 (unsigned n)nn if (n=1) return n;n return fibo1(n-1) + fibo1(n-2)

13、;nn=0或111/20/2021C程序设计教程PPT课件20算法：迭代法 优点：节省空间，节省时间缺点：编程相对复杂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/20/2021C程序设计教程PPT课件21算法3：向量迭代法 优点：节省时间 缺点：n越大，占用堆空间越多nunsigned fibo3 (unsigned n)nn vector v(n+1, 0); n v1 = 1;n for (unsigned i=2; i=n;

14、+i)n vi = vi-1 + vi-2;n return vn;n11/20/2021C程序设计教程PPT课件22算法4：直接计算法 优点：节省时间 缺点：引入了浮点计算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/20/2021C程序设计教程PPT课件23nfibo1：只在示意性编程中使用，但并不是否定一切递归法nfibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大

15、的场合中，性能比不上fibo4nfibo3：可以数组代替向量，提高低级编程的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2nfibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现11/20/2021C程序设计教程PPT课件244. 数值计算数值计算 ( Numerical Computation )n揭示：在近似计算中，除了计算范围与终止计算条件外，还涉及逼近的快慢，这与算法有很大关系，选择成熟的算法具有决定性作用n做法：了解各种数值计算算法的特点及使用场合，有的放矢解决实际问题11/20/2021C程序设计教程PPT课件25数值计

16、算的参数描述template / T为赖以计算的数系 T method ( / method为某种算法T a, / 左边界T b, / 右边界 const T Epsilon, / 终止条件 T ( * f ) ( T ) / 求值数学函数);11/20/2021C程序设计教程PPT课件26矩形法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 ( s

17、N - 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;小矩形求和辛普生处理前后两次辛普生值的差11/20/2021C程序设计教程PPT课件28性能比较求同样的数学函数，区间和精度矩阵法比辛普生法多

18、循环许多次11/20/2021C程序设计教程PPT课件295. 标准标准+ 算法算法 ( Standard C+ Algorithms )n揭示：标准C+提供了诸多算法，这些算法的组合构成了许多问题的解，对算法的准确了解是编程能力的一大体现n做法：吃透标准+算法，灵活运用之11/20/2021C程序设计教程PPT课件30容器的区间表示 P194vector a (10);/ 下面表示待处理的元素vector b (a.begin ()+1, a.begin ()+7 ); 0123456789首尾待处理的元素11/20/2021C程序设计教程PPT课件31逐一读入两个字串，比较是否含有相同元素

19、int main ( ) ifstream in ( string.txt ) ; for (string s,t; inst; ) 比较 输出 yes 或 no 11/20/2021C程序设计教程PPT课件32分别排序，直接加以字串比较是直截了当的思路：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()

20、, 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() ? yesn : non);C+标准算法11/20/2021C程序设计教程PPT课件356. 动态内存动态内存 ( Dynamic Memory )n揭示：许多问题不知道数据量的大

21、小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用充分利用堆空间(动态内存)是解决这些问题的关键n做法：理解堆空间的使用场合，学习堆空间的使用方法11/20/2021C程序设计教程PPT课件36使用容器，便是自动使用堆内存例如，从abc.txt中读取诸段落： ifstream in ( abc.txt ) ; vector ps ; / ps.reserve(1100) ; 可以预留 for ( string s ; getline ( in, s ) ; ) ps.push_back(s) ;预留是减小频繁扩容造成的数据移动开销11/20/2021C程序设计教程PPT课件

22、37若每个数据的处理，都要用到已经处理的数据时，保存历史数据，则可以改善时间性能例如，统计一亿之内的素数个数(原始版)： 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/20/2021C程序设计教程PPT课件38空间换时间版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);