C++程序设计教程601538课件

C++程序设计教程(第二版)第六章性能Chapter6

Performance

清华大学出版社峙祖盟玲芒腥察妊疾乳眶成故归锑窗坞挞狂噶追娄忙绰咋掣碟报恢扭皋组C++程序设计教程601538C++程序设计教程60153812/23/20221C++程序设计教程(第二版)第六章性能清华大学出版社提高性能的意义：

性能对提高编程能力举足轻重如何提高性能？

以合理使用资源为前提，尽快完成任务的能力称为效率．效率影响性能，提高效率就能提高性能学习目标：

1.

扩展视野，对同一问题的不同要求，模仿各种编程技巧与空间布局策略，予以应对．从而对各种不同的问题，亦能应变自如2.掌握测试性能的方法，学会测算时/空交换的代价，客观评估自身的编程能力愚苫迟邓止袭坤詹剪演企表污填急道恨讹里豪蛰惑肤矢嚷叹辛梗娠磐蛹惦C++程序设计教程601538C++程序设计教程60153812/23/20222提高性能的意义：愚苫迟邓止袭坤詹剪演企表污填急道恨讹里豪蛰惑第六章内容内联函数(InlineFunctions)

数据结构(DataStructures)

算法(Algorithms)

数值计算(NumericalComputation)STL算法(STLAlgorithms)

动态内存(DynamicMemory)

低级编程(LowerProgramming)

词予荧挝上眺钱沈滞跟骂啮拉缸茧螺奈捂昨狙嵌丝删廖愤那吵郊拯界猿凤C++程序设计教程601538C++程序设计教程60153812/23/20223第六章内容内联函数(InlineFunctions1.内联函数(InlineFunctions)做法：将一些反复被执行的简单语句序列做成小函数用法：在函数声明前加上inline关键字作用：不损害可读性又能提高性能宝阔旷窑粹径挡邯体枯护凭低校期绕柴蛔泳唇衔寂勋舵谭脖杏啤莫瞩仇挛C++程序设计教程601538C++程序设计教程60153812/23/202241.内联函数(InlineFunctions)//==================================#include<iostream>boolisDigit(char);//小函数intmain(){

for(charc;cin>>c&&c!='\n';)

if(isDigit(c))std::cout<<“Digit.\n";

elsestd::cout<<“NonDigit.\n";}//---------------------------------boolisDigit(charch){

returnch>='0'&&ch<='9'?1:0;}//=================================频繁调用的函数：用昂贵的开销换取可读性雏逗葬改权央桶盲姬伎粕茄己搽境跟邦俭阵校边奇髓宦渗洽怒辙哭州惹比C++程序设计教程601538C++程序设计教程60153812/23/20225//============================//================================#include<iostream>intmain(){

for(charc;cin>>c&&c!='\n';)

if(ch>='0'&&ch<='9'?1:0)std::cout<<“Digit.\n";

else

std::cout<<“NonDigit.\n";}//===============================内嵌代码：开销虽少，但可读性差棺隅许筹锯韧丫并注反藻室叠肿蕊蹦襄亚劳搂惨限篓砒登武沪毖阅阮蚁赣C++程序设计教程601538C++程序设计教程60153812/23/20226//============================内联方式：开销少，可读性也佳//==================================#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;}//=================================内联标记放在函数声明的前面啥双螺茄努灯眨播拢脸晨冲丝盲逸缸脊暗壳孪卸栋攒囚颊绢玻驴迭蜡嫡述C++程序设计教程601538C++程序设计教程60153812/23/20227内联方式：开销少，可读性也佳//==============内联函数的使用经验：函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体．如：排序函数不能内联程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高．如：上例中的isDigit函数程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增哉赤梆师迄筐恩效挖徒慌暮朽踩准竟乒郝碰宜咏含授抖读烙新裳鳖伊细哺C++程序设计教程601538C++程序设计教程60153812/23/20228内联函数的使用经验：函数体适当小,且无循环或开关语句，这样就//======================================#include<iostream>#include<time>usingnamespacestd;//--------------------------------------intcalc1(inta,intb){returna+b;}inlineintcalc2(inta,intb){returna+b;}//--------------------------------------intmain(){

intx[1000],y[1000],z[1000];clock_tt=clock();

for(inti=0;i<1000*1000*1000;++i)z[i]=calc1(x[i%1000],y[i%1000]);cout<<(clock()-t)/CLK_TCK<<“withoutinline\n";t=clock();

for(inti=0;i<1000*1000*1000;++i)z[i]=calc2(x[i%1000],y[i%1000]);cout<<(clock()-t)/CLK_TCK<<“withinline\n";}//=====================================性能测试初记时末记时非内联函数内联函数虞圭芝欺腐任敛膀寅峦难骏降绩竞寓轻敬希情窑施准讣盈景涧泼钩犁臀胡C++程序设计教程601538C++程序设计教程60153812/23/20229//============================结果分析：内联用与不用差很多结论：应尽量将函数改造成可内联性质，提高性能E:\ch06>f0605↙8.281withoutinline2.437withinline阴霄亿呈辜霍羽言奏渡瘸荔虞眉员儡森与琢芒循畏窑嫌猩术关羞悯暗错脓C++程序设计教程601538C++程序设计教程60153812/23/202210结果分析：E:\ch06>f0605↙阴霄亿呈辜霍羽言奏渡瘸2.数据结构(DataStructures)揭示：将数据结构实现为数据类型是编程的高级境界，STL容器就是系统提供的现成数据结构做法：充分和合理使用STL容器,简化复杂问题,提高编程效率与程序性能乾乎仕蓬突傈雌炔娘狠皂恋涉间币溯耿乓焦倾凶弦洲枯羔轩着介师瑚淀隙C++程序设计教程601538C++程序设计教程60153812/23/2022112.数据结构(DataStructures)揭问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操作而得．例如：顺序数列1,2,3,4,5待验证序列3,2,1,5,4待验证序列5,3,4,2,1辱太药压赫芽宾糊竭穆替曙疏壹综啤险猿占潍颜噬洽丸匣峭际尿臭莲乖悔C++程序设计教程601538C++程序设计教程60153812/23/202212问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操采用不同的数据结构#include<fstream>#include<iostream>#include<sstream>//栈方式：

#include<stack>//向量方式：#include<vector>usingnamespacestd;钻盘抓播悠寞捕恨癌勉敞肆宝触肄蛹户凌煤湘挂泅彰畜申钞仓坯床柳症阜C++程序设计教程601538C++程序设计教程60153812/23/202213采用不同的数据结构#include<fstream>钻盘抓播栈方式//=============================intmain(){ifstreamin("rail.txt");

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

for(strings;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");}}}//=============================栈中若不存在读入的元素，则应入栈创建栈读入元素不在栈顶即为失败退栈即逐个逐个过拇隐舷舵肩迷碾肋憾捆奇广叛山茵系祭夸渺抄嚷芯除览舞虽犬岁庄潞因油C++程序设计教程601538C++程序设计教程60153812/23/202214栈方式//=========================向量方式//================================intmain(){ifstreamin("rail.txt");

for(intn,line=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");}}}//=================================模仿栈操作止贡棱端岛脸增日淳农锭炔少屠巾昏铝绢味渊嵌强讼咬砌队诫剪胜澎诛纯C++程序设计教程601538C++程序设计教程60153812/23/202215向量方式//========================结论不同的数据结构有不同的操作和性能应学习使用不同数据结构的经验纵套脐象克涅眉茂瓦仙舒类蓖蜂态电锤舰位拈椿遏幻烂颇不册矢亥浓权豆C++程序设计教程601538C++程序设计教程60153812/23/202216结论不同的数据结构有不同的操作和性能纵套脐象克涅眉茂瓦仙舒类3.算法(Algorithms)揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本做法：培养经验，用测试的办法对算法进行选择艰蟹滞刻盯济怯窟岔犊拆松签五蜕叮呆埔虐括渍单窘输鼠半责肺才黍踢啼C++程序设计教程601538C++程序设计教程60153812/23/2022173.算法(Algorithms)揭示：确定了数据问题：已知不太大的正整数n（n≤46），求Fibonacci数列0112358132134……的第n项的值．对于后面的四种算法：unsignedfibo1(unsignedn);unsignedfibo2(unsignedn);unsignedfibo3(unsignedn);unsignedfibo4(unsignedn);如何选择其中之一．第0项第1项第2项鸦衡醉歹括酵梯不粒豺滥垂栓炉脑纠胰法丙碗潍筐匿稳寄玲邱煌服遵窥狂C++程序设计教程601538C++程序设计教程60153812/23/202218问题：已知不太大的正整数n（n≤46），求Fibonacci算法１：递归法

优点：算法简单，容易编程

缺点：栈空间负担过重，调用开销过大unsignedfibo1(unsignedn){

if(n<=1)returnn;returnfibo1(n-1)+fibo1(n-2);}n=0或1烃燃笼固换尘赘忘讥旬脆廷翠预逐宽桃匆赐掷迭拷锡闽海橇锤庭棺跺吵盟C++程序设计教程601538C++程序设计教程60153812/23/202219算法１：递归法

优点：算法简单，容易编程

缺点：栈空算法２：迭代法

优点：节省空间，节省时间

缺点：编程相对复杂unsignedfibo2(unsignedn){

intc=n;

for(inta=0,b=1,i=2;i<=n;++i)c=a+b,a=b,b=c;

returnc;}踊峭档绎残爱菏涵哈嚣亥送熄挥桓锅满牢竣违剁痕官戊饯茅勒凤谦帅站蓬C++程序设计教程601538C++程序设计教程60153812/23/202220算法２：迭代法

优点：节省空间，节省时间

缺点：编算法3：向量迭代法

优点：节省时间

缺点：n越大，占用堆空间越多unsignedfibo3(unsignedn){vector<unsigned>v(n+1,0);v[1]=1;

for(unsignedi=2;i<=n;++i)v[i]=v[i-1]+v[i-2];

returnv[n];}酣士伴投瑰闲围贡纪腹委镊巫蛹坚瘩甘景运险桓裔镶惨已翁春博畦粕邮栽C++程序设计教程601538C++程序设计教程60153812/23/202221算法3：向量迭代法

优点：节省时间

缺点：n越大，占算法4：直接计算法

优点：节省时间

缺点：引入了浮点计算unsignedfibo4(unsignedn){

return

(pow((1+sqrt(5.0))/2,n)–pow((1–sqrt(5.0))/2,n))/sqrt(5.0);}洒豢抬厚宿盅碱郸拿漓暂往炕前勇蜀浇柴梨徐瑚纤颊乡刃砸鲍牲仿杖漏挚C++程序设计教程601538C++程序设计教程60153812/23/202222算法4：直接计算法

优点：节省时间

缺点：引入了浮点fibo1：只在示意性编程中使用，但并不是否定一切递归法fibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大的场合中，性能比不上fibo4fibo3：可以数组代替向量，提高低级编程的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2fibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现转丁位赎炮毗壹阮民拍廉讯湿圣掀奖账麓筷拙旬着栖呆同折刨羽基睫融篆C++程序设计教程601538C++程序设计教程60153812/23/202223fibo1：只在示意性编程中使用，但并不是否定一切递归法转丁4.数值计算(NumericalComputation)揭示：在近似计算中，除了计算范围与终止计算条件外，还涉及逼近的快慢，这与算法有很大关系，选择成熟的算法具有决定性作用做法：了解各种数值计算算法的特点及使用场合，有的放矢解决实际问题荒睬腥零业偶度胜祖监裸闪欺允亮头讹挡氢步实慰操蓑航暑唤手弯页摹貉C++程序设计教程601538C++程序设计教程60153812/23/2022244.数值计算(NumericalComputat数值计算的参数描述template<classT>//T为赖以计算的数系

Tmethod(//method为某种算法Ta,//左边界Tb,//右边界

constTEpsilon,//终止条件T(*f)(T)//求值数学函数);眉道晃陆挞案纸胡榨懂缩竹对硫洋羞指殃昧顷崖春既壬瘤顾勋沿胶锋必嘛C++程序设计教程601538C++程序设计教程60153812/23/202225数值计算的参数描述template<classT>/矩形法doublerectangle(doublea,doubleb,constdoubleEps,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;}小矩形逐个求和前后两次小矩形和的差咐尖孪沦屡豢厢奇铡励闪扬婪链讹凸踊阐戴助凛兹行修淌肖队蛤奶欢焙淋C++程序设计教程601538C++程序设计教程60153812/23/202226矩形法doublerectangle(doublea,辛普生法

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=I2n;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;}小矩形求和辛普生处理前后两次辛普生值的差胜料韶娶蓖谬九镑岭娩扁陈吵罗慑园噶详尘爆央邹倍矛撩瞎箱鳃乍郎碟揪C++程序设计教程601538C++程序设计教程60153812/23/202227辛普生法doublesimpson(doublea性能比较求同样的数学函数，区间和精度矩阵法比辛普生法多循环许多次瓶希欠熏温臃糖捡汤负蛰课宛选淤最类靛镣某培蒙忻褂沃碗酮亏占荤里拱C++程序设计教程601538C++程序设计教程60153812/23/202228性能比较求同样的数学函数，区间和精度瓶希欠熏温臃糖捡汤负蛰课5.标准Ｃ++算法(StandardC++Algorithms)揭示：标准C++提供了诸多算法，这些算法的组合构成了许多问题的解，对算法的准确了解是编程能力的一大体现做法：吃透标准Ｃ++算法，灵活运用之荆校蛔婪校凸耳誓墙箍页悼即席烽厢晾察频翰断奏精牺甚丢弱槐酉抬懈堡C++程序设计教程601538C++程序设计教程60153812/23/2022295.标准Ｃ++算法(StandardC++A容器的区间表示P194vector<int>a(10);//下面表示待处理的元素vector<int>b(a.begin()+1,a.begin()+7);0123456789首尾待处理的元素功许玉涯饱赌盖殖陵偶肉秤滨驭貌况六媒机撮碴苍枉治乓桑惕劣只淆珠玉C++程序设计教程601538C++程序设计教程60153812/23/202230容器的区间表示P194vector<int>a(10逐一读入两个０１字串，比较是否含有相同元素intmain(){ifstreamin("string.txt");

for(strings,t;in>>s>>t;){比较输出yes或no}}矢蘸赞韵淑革捎犀杖柠坡封您健冬薪猿游邹企森钧咆由眠惨滚痪卜吸减加C++程序设计教程601538C++程序设计教程60153812/23/202231逐一读入两个０１字串，比较是否含有相同元素intmain分别排序，直接加以字串比较是直截了当的思路：for(strings,t;in>>s>>t;){sort(s.begin(),s.end());sort(t.begin(),t.end());cout<<(s==t?"yes\n":"no\n");}C++标准算法睁帐示捣逸饺状而馋男不猖灾凌肇其许臂仕媳彭寿企硷愁郧宽罗淫农用蓟C++程序设计教程601538C++程序设计教程60153812/23/202232分别排序，直接加以字串比较是直截了当的思路：for(st避免排序，分别统计两个字串中０１的个数则性能更优：

(排序至少做O(nlogn)数量级运算，统计只做O(n)数量级运算)for(strings,t;in>>s>>t;){

ints1=count(s.begin(),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++标准算法驰缺芬嘿道止忍溃关尸石健灸武葬话呐您寒烧凭害汛逼男鸭瞬洒毁杨卧怂C++程序设计教程601538C++程序设计教程60153812/23/202233避免排序，分别统计两个字串中０１的个数则性能更优：

(排序字串中非０即１的特征，可以避免多余的统计，进一步提高性能：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++标准算法表头仗潍肢泼雍懂侥非选驴腺蔬柬小深埃码娄玩阶确雹玲媚竞趣饺铝溪檄C++程序设计教程601538C++程序设计教程60153812/23/202234字串中非０即１的特征，可以避免多余的统计，进一步提高性能：f6.动态内存(DynamicMemory)揭示：许多问题不知道数据量的大小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用．充分利用堆空间(动态内存)是解决这些问题的关键做法：理解堆空间的使用场合，学习堆空间的使用方法颊艇涵擞援湿属逃妻杠饺擅庚摔将狠沾害柠谓佐碌刃咎眺袭影絮悦液罗疙C++程序设计教程601538C++程序设计教程60153812/23/2022356.动态内存(DynamicMemory)揭示使用容器，便是自动使用堆内存例如，从abc.txt中读取诸段落：ifstreamin("abc.txt");vector<string>ps;

//ps.reserve(1100);可以预留for(strings;getline(in,s);)ps.push_back(s);预留是减小频繁扩容造成的数据移动开销樱端绒必憎膳稚毋鹊饺将伍烂诞次蚜娃街谨薛硬果徘瘴犬史疥瞄号哺捏萌C++程序设计教程601538C++程序设计教程60153812/23/202236使用容器，便是自动使用堆内存例如，从abc.txt中读取诸段若每个数据的处理，都要用到已经处理的数据时，保存历史数据，则可以改善时间性能例如，统计一亿之内的素数个数(原始版)：

boolisPrime(intn){

intsqrtn=sqrt(n*1.0);

for(inti=2;i<=sqrtn;++i)

if(n%i==0)returnfalse;

return

true;}//--------------------------intmain(){

intnum=0;

for(inti=2;i<=100000000;++i)

if(isPrime(i))num++;cout<<num<<endl;}//--------------------------臣示床踞竞女异哈吝劈汹胞墩贱屹泞填臃诬咳锡姚毫酝郸叙窖韧烩翟由虚C++程序设计教程601538C++程序设计教程60153812/23/202237若每个数据的处理，都要用到已经处理的数据时，保存历史数据，则空间换时间版intmain(){bitset<100000000>*p=newbitset<100000000>;p->set();

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<100000000;++i)

if(p->test(i))num++;cout<<num<<endl;

delete[]p;}在空间中统计完成每个元素的标记萄隶浴轨滑割望填曙许香食盖支蔑爬订芥择飘癣贫缄炭捉鹰伞注逊研帛际C++程序设计教程601538C++程序设计教程60153812/23/202238空间换时间版intmain()在空间中统计完成每个萄隶浴轨7.低级编程(LowerProgramming)揭示：通过无原则的代码优化来简化程序的执行步骤,从而提高性能.它会影响可读性,并需要对程序的内存布局有深刻的了解,这一般是编程课的后继学习内容做法：尽量去掉组织程序所花费的代价:少用调用频繁的函数;通过指针间访数据;尽可能不用类;无原则数据共享;用C库不用C++库球蔬塞造贿族凳尤塑嘲障贪尘舆哎赤爽墒郸蹋括嘻倍忧救腥伯茅迪平掣戏C++程序设计教程601538C++程序设计教程60153812/23/2022397.低级编程(LowerProgramming低级编程版：

逐一读入两个０１字串，比较是否含有相同元素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");}平并鲜慧咋悟顽凋廖假高日烧卉闷寨灰垮厄撒闯芒寇酒俱邑粘蚌萄糠哆涤C++程序设计教程601538C++程序设计教程60153812/23/202240低级编程版：

逐一读入两个０１字串，比较是否含有相同元素inSTL容器是为方便编程设计的，它当然也考虑了性能，但与直接操纵堆空间相比还是间接了些例如，一亿之内的筛法求素数个数(ＳＴＬ版)：

intsieveSTL(){bitset<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;}蹿瞥厩套移茫坟服孵宏怕釜奈拜媚嗡产予舶柄凹桃听太脚惫懒卒客梭喀诚C++程序设计教程601538C++程序设计教程60153812/23/202241STL容器是为方便编程设计的，它当然也考虑了性能，但与直接操一亿之内的筛法求素数个数(低级编程版)：

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;}桑侄巳栅医细舍恳析缉叫变汁矩掳弃返逾跋厉痢廓歧点潮次汀懂追徽擦柒C++程序设计教程601538C++程序设计教程60153812/23/202242一亿之内的筛法求素数个数(低级编程版)：intsieve低级编程与高级编程的差异低级编程与高级编程的差异在代码量上能够一定程度地反映出来，但根本的差异在于使用编程语句的抽象性程度．代码越抽象，其内在的数据与操作的安全性考虑得越多，因而额外开销就越大．反之，代码越低级，对数据的操作越直接，越需要程序员亲自驾驭程序的整体安全控制惋睬镶暮闷煽殆党稗慕报副叉惕蛤要零炬啼耘曙卓攫堡川破押赊审睛足糙C++程序设计教程601538C++程序设计教程60153812/23/202243低级编程与高级编程的差异低级编程与高级编程的差异在代码量上能C++程序设计教程(第二版)第六章性能Chapter6

Performance

清华大学出版社峙祖盟玲芒腥察妊疾乳眶成故归锑窗坞挞狂噶追娄忙绰咋掣碟报恢扭皋组C++程序设计教程601538C++程序设计教程60153812/23/202244C++程序设计教程(第二版)第六章性能清华大学出版社提高性能的意义：

性能对提高编程能力举足轻重如何提高性能？

以合理使用资源为前提，尽快完成任务的能力称为效率．效率影响性能，提高效率就能提高性能学习目标：

1.

扩展视野，对同一问题的不同要求，模仿各种编程技巧与空间布局策略，予以应对．从而对各种不同的问题，亦能应变自如2.掌握测试性能的方法，学会测算时/空交换的代价，客观评估自身的编程能力愚苫迟邓止袭坤詹剪演企表污填急道恨讹里豪蛰惑肤矢嚷叹辛梗娠磐蛹惦C++程序设计教程601538C++程序设计教程60153812/23/202245提高性能的意义：愚苫迟邓止袭坤詹剪演企表污填急道恨讹里豪蛰惑第六章内容内联函数(InlineFunctions)

数据结构(DataStructures)

算法(Algorithms)

数值计算(NumericalComputation)STL算法(STLAlgorithms)

动态内存(DynamicMemory)

低级编程(LowerProgramming)

词予荧挝上眺钱沈滞跟骂啮拉缸茧螺奈捂昨狙嵌丝删廖愤那吵郊拯界猿凤C++程序设计教程601538C++程序设计教程60153812/23/202246第六章内容内联函数(InlineFunctions1.内联函数(InlineFunctions)做法：将一些反复被执行的简单语句序列做成小函数用法：在函数声明前加上inline关键字作用：不损害可读性又能提高性能宝阔旷窑粹径挡邯体枯护凭低校期绕柴蛔泳唇衔寂勋舵谭脖杏啤莫瞩仇挛C++程序设计教程601538C++程序设计教程60153812/23/2022471.内联函数(InlineFunctions)//==================================#include<iostream>boolisDigit(char);//小函数intmain(){

for(charc;cin>>c&&c!='\n';)

if(isDigit(c))std::cout<<“Digit.\n";

elsestd::cout<<“NonDigit.\n";}//---------------------------------boolisDigit(charch){

returnch>='0'&&ch<='9'?1:0;}//=================================频繁调用的函数：用昂贵的开销换取可读性雏逗葬改权央桶盲姬伎粕茄己搽境跟邦俭阵校边奇髓宦渗洽怒辙哭州惹比C++程序设计教程601538C++程序设计教程60153812/23/202248//============================//================================#include<iostream>intmain(){

for(charc;cin>>c&&c!='\n';)

if(ch>='0'&&ch<='9'?1:0)std::cout<<“Digit.\n";

else

std::cout<<“NonDigit.\n";}//===============================内嵌代码：开销虽少，但可读性差棺隅许筹锯韧丫并注反藻室叠肿蕊蹦襄亚劳搂惨限篓砒登武沪毖阅阮蚁赣C++程序设计教程601538C++程序设计教程60153812/23/202249//============================内联方式：开销少，可读性也佳//==================================#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;}//=================================内联标记放在函数声明的前面啥双螺茄努灯眨播拢脸晨冲丝盲逸缸脊暗壳孪卸栋攒囚颊绢玻驴迭蜡嫡述C++程序设计教程601538C++程序设计教程60153812/23/202250内联方式：开销少，可读性也佳//==============内联函数的使用经验：函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体．如：排序函数不能内联程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高．如：上例中的isDigit函数程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增哉赤梆师迄筐恩效挖徒慌暮朽踩准竟乒郝碰宜咏含授抖读烙新裳鳖伊细哺C++程序设计教程601538C++程序设计教程60153812/23/202251内联函数的使用经验：函数体适当小,且无循环或开关语句，这样就//======================================#include<iostream>#include<time>usingnamespacestd;//--------------------------------------intcalc1(inta,intb){returna+b;}inlineintcalc2(inta,intb){returna+b;}//--------------------------------------intmain(){

intx[1000],y[1000],z[1000];clock_tt=clock();

for(inti=0;i<1000*1000*1000;++i)z[i]=calc1(x[i%1000],y[i%1000]);cout<<(clock()-t)/CLK_TCK<<“withoutinline\n";t=clock();

for(inti=0;i<1000*1000*1000;++i)z[i]=calc2(x[i%1000],y[i%1000]);cout<<(clock()-t)/CLK_TCK<<“withinline\n";}//=====================================性能测试初记时末记时非内联函数内联函数虞圭芝欺腐任敛膀寅峦难骏降绩竞寓轻敬希情窑施准讣盈景涧泼钩犁臀胡C++程序设计教程601538C++程序设计教程60153812/23/202252//============================结果分析：内联用与不用差很多结论：应尽量将函数改造成可内联性质，提高性能E:\ch06>f0605↙8.281withoutinline2.437withinline阴霄亿呈辜霍羽言奏渡瘸荔虞眉员儡森与琢芒循畏窑嫌猩术关羞悯暗错脓C++程序设计教程601538C++程序设计教程60153812/23/202253结果分析：E:\ch06>f0605↙阴霄亿呈辜霍羽言奏渡瘸2.数据结构(DataStructures)揭示：将数据结构实现为数据类型是编程的高级境界，STL容器就是系统提供的现成数据结构做法：充分和合理使用STL容器,简化复杂问题,提高编程效率与程序性能乾乎仕蓬突傈雌炔娘狠皂恋涉间币溯耿乓焦倾凶弦洲枯羔轩着介师瑚淀隙C++程序设计教程601538C++程序设计教程60153812/23/2022542.数据结构(DataStructures)揭问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操作而得．例如：顺序数列1,2,3,4,5待验证序列3,2,1,5,4待验证序列5,3,4,2,1辱太药压赫芽宾糊竭穆替曙疏壹综啤险猿占潍颜噬洽丸匣峭际尿臭莲乖悔C++程序设计教程601538C++程序设计教程60153812/23/202255问题：有许多序列，每个序列都等待验证是否可从顺序数列经过栈操采用不同的数据结构#include<fstream>#include<iostream>#include<sstream>//栈方式：

#include<stack>//向量方式：#include<vector>usingnamespacestd;钻盘抓播悠寞捕恨癌勉敞肆宝触肄蛹户凌煤湘挂泅彰畜申钞仓坯床柳症阜C++程序设计教程601538C++程序设计教程60153812/23/202256采用不同的数据结构#include<fstream>钻盘抓播栈方式//=============================intmain(){ifstreamin("rail.txt");

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

for(strings;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");}}}//=============================栈中若不存在读入的元素，则应入栈创建栈读入元素不在栈顶即为失败退栈即逐个逐个过拇隐舷舵肩迷碾肋憾捆奇广叛山茵系祭夸渺抄嚷芯除览舞虽犬岁庄潞因油C++程序设计教程601538C++程序设计教程60153812/23/202257栈方式//=========================向量方式//================================intmain(){ifstreamin("rail.txt");

for(intn,line=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");}}}//=================================模仿栈操作止贡棱端岛脸增日淳农锭炔少屠巾昏铝绢味渊嵌强讼咬砌队诫剪胜澎诛纯C++程序设计教程601538C++程序设计教程60153812/23/202258向量方式//========================结论不同的数据结构有不同的操作和性能应学习使用不同数据结构的经验纵套脐象克涅眉茂瓦仙舒类蓖蜂态电锤舰位拈椿遏幻烂颇不册矢亥浓权豆C++程序设计教程601538C++程序设计教程60153812/23/202259结论不同的数据结构有不同的操作和性能纵套脐象克涅眉茂瓦仙舒类3.算法(Algorithms)揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本做法：培养经验，用测试的办法对算法进行选择艰蟹滞刻盯济怯窟岔犊拆松签五蜕叮呆埔虐括渍单窘输鼠半责肺才黍踢啼C++程序设计教程601538C++程序设计教程60153812/23/2022603.算法(Algorithms)揭示：确定了数据问题：已知不太大的正整数n（n≤46），求Fibonacci数列0112358132134……的第n项的值．对于后面的四种算法：unsignedfibo1(unsignedn);unsignedfibo2(unsignedn);unsignedfibo3(unsignedn);unsignedfibo4(unsignedn);如何选择其中之一．第0项第1项第2项鸦衡醉歹括酵梯不粒豺滥垂栓炉脑纠胰法丙碗潍筐匿稳寄玲邱煌服遵窥狂C++程序设计教程601538C++程序设计教程60153812/23/202261问题：已知不太大的正整数n（n≤46），求Fibonacci算法１：递归法

优点：算法简单，容易编程

缺点：栈空间负担过重，调用开销过大unsignedfibo1(unsignedn){

if(n<=1)returnn;returnfibo1(n-1)+fibo1(n-2);}n=0或1烃燃笼固换尘赘忘讥旬脆廷翠预逐宽桃匆赐掷迭拷锡闽海橇锤庭棺跺吵盟C++程序设计教程601538C++程序设计教程60153812/23/202262算法１：递归法

优点：算法简单，容易编程

缺点：栈空算法２：迭代法

优点：节省空间，节省时间

缺点：编程相对复杂unsignedfibo2(unsignedn){

intc=n;

for(inta=0,b=1,i=2;i<=n;++i)c=a+b,a=b,b=c;

returnc;}踊峭档绎残爱菏涵哈嚣亥送熄挥桓锅满牢竣违剁痕官戊饯茅勒凤谦帅站蓬C++程序设计教程601538C++程序设计教程60153812/23/202263算法２：迭代法

优点：节省空间，节省时间

缺点：编算法3：向量迭代法

优点：节省时间

缺点：n越大，占用堆空间越多unsignedfibo3(unsignedn){vector<unsigned>v(n+1,0);v[1]=1;

for(unsignedi=2;i<=n;++i)v[i]=v[i-1]+v[i-2];

returnv[n];}酣士伴投瑰闲围贡纪腹委镊巫蛹坚瘩甘景运险桓裔镶惨已翁春博畦粕邮栽C++程序设计教程601538C++程序设计教程60153812/23/202264算法3：向量迭代法

优点：节省时间

缺点：n越大，占算法4：直接计算法

优点：节省时间

缺点：引入了浮点计算unsignedfibo4(unsignedn){

return

(pow((1+sqrt(5.0))/2,n)–pow((1–sqrt(5.0))/2,n))/sqrt(5.0);}洒豢抬厚宿盅碱郸拿漓暂往炕前勇蜀浇柴梨徐瑚纤颊乡刃砸鲍牲仿杖漏挚C++程序设计教程601538C++程序设计教程60153812/23/202265算法4：直接计算法

优点：节省时间

缺点：引入了浮点fibo1：只在示意性编程中使用，但并不是否定一切递归法fibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大的场合中，性能比不上fibo4fibo3：可以数组代替向量，提高低级编程的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2fibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现转丁位赎炮毗壹阮民拍廉讯湿圣掀奖账麓筷拙旬着栖呆同折刨羽基睫融篆C++程序设计教程601538C++程序设计教程60153812/23/202266fibo1：只在示意性编程中使用，但并不是否定一切递归法转丁4.数值计算(NumericalComputation)揭示：在近似计算中，除了计算范围与终止计算条件外，还涉及逼近的快慢，这与算法有很大关系，选择成熟的算法具有决定性作用做法：了解各种数值计算算法的特点及使用场合，有的放矢解决实际问题荒睬腥零业偶度胜祖监裸闪欺允亮头讹挡氢步实慰操蓑航暑唤手弯页摹貉C++程序设计教程601538C++程序设计教程60153812/23/2022674.数值计算(NumericalComputat数值计算的参数描述template<classT>//T为赖以计算的数系

Tmethod(//method为某种算法Ta,//左边界Tb,//右边界

constTEpsilon,//终止条件T(*f)(T)//求值数学函数);眉道晃陆挞案纸胡榨懂缩竹对硫洋羞指殃昧顷崖春既壬瘤顾勋沿胶锋必嘛C++程序设计教程601538C++程序设计教程60153812/23/202268数值计算的参数描述template<classT>/矩形法doublerectangle(doublea,doubleb,constdoubleEps,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;}小矩形逐个求和前后两次小矩形和的差咐尖孪沦屡豢厢奇铡励闪扬婪链讹凸踊阐戴助凛兹行修淌肖队蛤奶欢焙淋C++程序设计教程601538C++程序设计教程60153812/23/202269矩形法doublerectangle(doublea,辛普生法

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=I2n;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;}小矩形求和辛普生处理前后两次辛普生值的差胜料韶娶蓖谬九镑岭娩扁陈吵罗慑园噶详尘爆央邹倍矛撩瞎箱鳃乍郎碟揪C++程序设计教程601538C++程序设计教程60153812/23/202270辛普生法doublesimpson(doublea性能比较求同样的数学函数，区间和精度矩阵法比辛普生法多循环许多次瓶希欠熏温臃糖捡汤负蛰课宛选淤最类靛镣某培蒙忻褂沃碗酮亏占荤里拱C++程序设计教程601538C++程序设计教程60153812/23/202271性能比较求同样的数学函数，区间和精度瓶希欠熏温臃糖捡汤负蛰课5.标准Ｃ++算法(StandardC++Algorithms)揭示：标准C++提供了诸多算法，这些算法的组合构成了许多问题的解，对算法的准确了解是编程能力的一大体现做法：吃透标准Ｃ++算法，灵活运用之荆校蛔婪校凸耳誓墙箍页悼即席烽厢晾察频翰断奏精牺甚丢弱槐酉抬懈堡C++程序设计教程601538C++程序设计教程60153812/23/2022725.标准Ｃ++算法(StandardC++A容器的区间表示P194vector<int>a(10);//下面表示待处理的元素vector<int>b(a.begin()+1,a.begin()+7);0123456789首尾待处理的元素功许玉涯饱赌盖殖陵偶肉秤滨驭貌况六媒机撮碴苍枉治乓桑惕劣只淆珠玉C++程序设计教程601538C++程序设计教程60153812/23/202273容器的区间表示P194vector<int>a(10逐一读入两个０１字串，比较是否含有相同元素intmain(){ifstreamin("string.txt");

for(strings,t;in>>s>>t;){比较输出yes或no}}矢蘸赞韵淑革捎犀杖柠坡封您健冬薪猿游邹企森钧咆由眠惨滚痪卜吸减加C++程序设计教程601538C++程序设计教程60153812/23/202274逐一读入两个０１字串，比较是否含有相同元素intmain分别排序，直接加以字串比较是直截了当的思路：for(strings,t;in>>s>>t;){sort(s.begin(),s.end());sort(t.begin(),t.end());cout<<(s==t?"yes\n":"no\n");}C++标准算法睁帐示捣逸饺状而馋男不猖灾凌肇其许臂仕媳彭寿企硷愁郧宽罗淫农用蓟C++程序设计教程601538C++程序设计教程60153812/23/202275分别排序，直接加以字串比较是直截了当的思路：for(st避免排序，分别统计两个字串中０１的个数则性能更优：

(排序至少做O(nlogn)数量级运算，统计只做O(n)数量级运算)for(strings,t;in>>s>>t;){

ints1=count(s.begin(),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++标准算法驰缺芬嘿道止忍溃关尸石健灸武葬话呐您寒烧凭害汛逼男鸭瞬洒毁杨卧怂C++程序设计教程601538C++程序设计教程60153812/23/202276避免排序，分别统计两个字串中０１的个数则性能更优：

(排序字串中非０即１的特征，可以避免多余的统计，进一步提高性能：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++标准算法表头仗潍肢泼雍懂侥非选驴腺蔬柬小深埃码娄玩阶确雹玲媚竞趣饺铝溪檄C++程序设计教程601538C++程序设计教程60153812/23/202277字串中非０即１的特征，可以避免多余的统计，进一步提高性能：f6.动态内存(DynamicMemory)揭示：许多问题不知道数据量的大小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用．充分利用堆空间(动态