钱能C++程序设计教程6

2/27/20201C++程序设计教程(第二版)第六章性能Chapter6Performance清华大学出版社钱能2/27/20202提高性能的意义：性能对提高编程能力举足轻重如何提高性能？以合理使用资源为前提，尽快完成任务的能力称为效率．效率影响性能，提高效率就能提高性能学习目标：1.扩展视野，对同一问题的不同要求，模仿各种编程技巧与空间布局策略，予以应对．从而对各种不同的问题，亦能应变自如2.掌握测试性能的方法，学会测算时/空交换的代价，客观评估自身的编程能力2/27/20203第六章内容1.内联函数(InlineFunctions)2.数据结构(DataStructures)3.算法(Algorithms)4.数值计算(NumericalComputation)5.STL算法(STLAlgorithms)6.动态内存(DynamicMemory)7.低级编程(LowerProgramming)2/27/202041.内联函数(InlineFunctions)做法：将一些反复被执行的简单语句序列做成小函数用法：在函数声明前加上inline关键字作用：不损害可读性又能提高性能2/27/202051.//==================================2.#includeiostream3.boolisDigit(char);//小函数4.intmain(){5.for(charc;cinc&&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.}//=================================频繁调用的函数：用昂贵的开销换取可读性2/27/202061.//================================2.#includeiostream3.intmain(){4.for(charc;cinc&&c!='\n';)5.if(ch='0'&&ch='9'?1:0)6.std::cout“Digit.\n;7.else8.std::cout“NonDigit.\n;9.}//===============================内嵌代码：开销虽少，但可读性差2/27/20207内联方式：开销少，可读性也佳1.//==================================2.#includeiostreaminlineboolisDigit(char);//小函数intmain(){for(charc;cinc&&c!='\n';)if(isDigit(c))std::coutDigit.\n;elsestd::coutNonDigit.\n;}//---------------------------------boolisDigit(charch){returnch='0'&&ch='9'?1:0;}//=================================内联标记放在函数声明的前面2/27/20208内联函数的使用经验：函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体．如：排序函数不能内联程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高．如：上例中的isDigit函数程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增2/27/202091.//======================================2.#includeiostream3.#includetime4.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;i1000*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;i1000*1000*1000;++i)17.z[i]=calc2(x[i%1000],y[i%1000]);18.cout(clock()-t)/CLK_TCK“withinline\n;19.}//=====================================性能测试初记时末记时非内联函数内联函数2/27/202010结果分析：内联用与不用差很多结论：应尽量将函数改造成可内联性质，提高性能E:\ch06f0605↙8.281withoutinline2.437withinline2/27/2020112.数据结构(DataStructures)揭示：将数据结构实现为数据类型是编程的高级境界，STL容器就是系统提供的现成数据结构做法：充分和合理使用STL容器,简化复杂问题,提高编程效率与程序性能2/27/202012问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操作而得．例如：顺序数列1,2,3,4,5待验证序列3,2,1,5,4待验证序列5,3,4,2,12/27/202013采用不同的数据结构#includefstream#includeiostream#includesstream//栈方式：#includestack//向量方式：#includevectorusingnamespacestd;2/27/202014栈方式//=============================intmain(){ifstreamin(rail.txt);for(intn,line=0;inn&&n&&in.ignore();){cout(line++?\n:);for(strings;getline(in,s)&&s!=0;){istringstreamsin(s);stackintst;for(intlast=0,coach;sincoach;st.pop()){for(intp=last+1;p=coach;++p)st.push(p);if(lastcoach)last=coach;if(st()!=coach)break;}cout(!sin?Yes\n:No\n);}}}//=============================栈中若不存在读入的元素，则应入栈创建栈读入元素不在栈顶即为失败退栈即逐个逐个过2/27/202015向量方式//================================intmain(){ifstreamin(rail.txt);for(intn,line=0;inn&&n&&in.ignore();){cout(line++?\n:);for(strings;getline(in,s)&&s!=0;){istringstreamsin(s);vectorintst;for(intlast=0,coach;sincoach;st.pop_back())){for(intp=last+1;p=coach;++p)st.push_back(p);if(lastcoach)last=coach;if(st.back()!=coach)break;}cout(!sin?Yes\n:No\n);}}}//=================================模仿栈操作2/27/202016结论不同的数据结构有不同的操作和性能应学习使用不同数据结构的经验2/27/2020173.算法(Algorithms)揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本做法：培养经验，用测试的办法对算法进行选择2/27/202018问题：已知不太大的正整数n（n≤46），求Fibonacci数列0112358132134……的第n项的值．对于后面的四种算法：unsignedfibo1(unsignedn);unsignedfibo2(unsignedn);unsignedfibo3(unsignedn);unsignedfibo4(unsignedn);如何选择其中之一．第0项第1项第2项2/27/202019算法１：递归法优点：算法简单，容易编程缺点：栈空间负担过重，调用开销过大1.unsignedfibo1(unsignedn)2.{3.if(n=1)returnn;4.returnfibo1(n-1)+fibo1(n-2);5.}n=0或12/27/202020算法２：迭代法优点：节省空间，节省时间缺点：编程相对复杂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.}2/27/202021算法3：向量迭代法优点：节省时间缺点：n越大，占用堆空间越多1.unsignedfibo3(unsignedn)2.{3.vectorunsignedv(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.}2/27/202022算法4：直接计算法优点：节省时间缺点：引入了浮点计算1.unsignedfibo4(unsignedn)2.{3.return4.(pow((1+sqrt(5.0))/2,n)5.–pow((1–sqrt(5.0))/2,n))6./sqrt(5.0);7.}2/27/202023fibo1：只在示意性编程中使用，但并不是否定一切递归法fibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大的场合中，性能比不上fibo4fibo3：可以数组代替向量，提高低级编程的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2fibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现2/27/2020244.数值计算(NumericalComputation)揭示：在近似计算中，除了计算范围与终止计算条件外，还涉及逼近的快慢，这与算法有很大关系，选择成熟的算法具有决定性作用做法：了解各种数值计算算法的特点及使用场合，有的放矢解决实际问题2/27/202025数值计算的参数描述templateclassT//T为赖以计算的数系Tmethod(//method为某种算法Ta,//左边界Tb,//右边界constTEpsilon,//终止条件T(*f)(T)//求值数学函数);2/27/202026矩形法doublerectangle(doublea,doubleb,constdoubleEps,double(*f)(double)){doublew=b-a,sN=w*(f(a)+f(b))/2,sO=