第六章 C性能

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

2、nline Functions ) 2. 数据结构数据结构 ( Data Structures ) 3. 算法算法 ( Algorithms ) 4. 数值计算数值计算 ( Numerical Computation )5. 标准标准C+算法算法 (Standard C+ Algorithms ) 6. 动态内存动态内存 ( Dynamic Memory ) 7. 低级编程低级编程 ( Lower Programming ) Visual C+ Program Design6.1 内联函数内联函数v做法：将一些反复被执行的简单语句序列做成小函数v用法：在函数声明前加上inline关键字v作用：

3、不损害可读性又能提高性能Visual C+ Program Design1./=2.#include3.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./=频繁调用的函数：用昂贵的开销换取可读性频繁调用的函数：用昂贵的开销换取可读性Visual C+ Program Design1./=2.#include3

4、.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./=内嵌代码：开销虽少，但可读性差内嵌代码：开销虽少，但可读性差Visual C+ Program Design内联方式：开销少，可读性也佳1./=2.#includevinline inline boolbool isDigit(charchar); / 小函数vintint main( )v forfor(charch

5、ar c; cinc & c!=n; )v ifif(isDigit(c) v std:coutDigit.n;v elseelse v std:cout=0 & ch=9 ? 1 : 0;v/=内联标记放在函数声明的前面Visual C+ Program Design内联函数的使用经验：内联函数的使用经验：v函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体v程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高如：上例中的isDigit函数v程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增 Visual C+ Program D

6、esign6.1.2 规则规则v对函数的声明必须在调用之前，因为内联函数的代码在程序运行时是直接嵌在调用处执行的，它不影响链接，只在编译时确定运行代码。如：Visual C+ Program Designv / 未声明内联v /=v #includev using namespace std;v /-v bool isnumber(char); / 此处无inlinev /-v int main()v for(char c; cinc & c!=n; )v if(isnumber(c) coutyou entered a digit.n;v else cout=0 & ch=9 ? 1 : 0

7、;v /=Visual C+ Program Designv编译并不认为那是内联函数。对待isnumber函数调用就如调用普通函数那样，产生该函数的调用代码并进行链接。v内联函数应该尽可能小，且要结构简单。不能含有复杂的结构控制语句，如switch和while。v递归函数不能用来做内联函数。v经验上，内联函数只适合于15行的小函数。在自定义数据类型的时候，会设计大量的小函数定义，这些小函数会被频繁的调用，所以，内联函数针对它们很合适。Visual C+ Program Designv内联函数使用的场合一般为： 函数体适当小，便于嵌入工作进行，不会破坏原有调用主体。 程序中特别是在循环中反复执行

8、该函数，这样就使嵌入函数的效率相对较高。 程序并不多处出现该函数调用，这样就使得嵌入工作量相对较少，代码量也不会剧增。Visual C+ Program Design6.1.3 性能测试性能测试v做个试验，让主函数分别调用内联函数和非内联函数，为了看清两者区别，有必要调用10亿次函数来放大时间差，下列程序设置了三个1000个元素的数组，使用数组的目的是尽量减少其他开销，让调用的开销充分暴露出来，程序代码如下：Visual C+ Program Designv/ 内联性能测试v/=v#includev#includevusing namespace std;v/-vint calc1(int a

9、, int b)v return a+b;v/-vinline int calc2(int a, int b)v return a+b;v/-vint main()v int x1000, y1000, z1000;v clock_t t = clock();v for(int i=0; i1000; +i)v for(int j=0; j1000; +j)v for(int k=0; k1000; +k)v zi = calc1(xj, yk);v cout Not using inline: (clock()-t)/CLK_TCK secondsn;v t = clock();v for(

10、int i=0; i1000; +i)v for(int j=0; j1000; +j)v for(int k=0; k1000; +k)v zi = calc2(xj, yk);v cout Using inline: (clock()-t)/CLK_TCK secondsn;v/=v Not using inline ：8.281 secondsUsing inline ：2.437 secondsVisual C+ Program Design结果分析：内联用与不用差很多结论：应尽量将函数改造成可内联性质，提高性能Visual C+ Program Design6.2.1 STL中的容器

11、中的容器v数据结构给出了操纵问题中所要处理数据的内在表示和问题解答的数学模型，能够规定同类数据的内在组织和操作，这些规定可以“打包”，打成的包是高度独立和内闭的，可声称对其一切行为负责，并且能作为一个整体到处挪用，所以，数据类型能够方便的描述和操作一系列同类数据，并能方便的定义与其他数据类型进行转换的操作。STL中的容器，就是最通用的几种数据结构，它们在C+中以模板类的形式出现，即可容纳一切数据类型的数据集合。每种数据结构都能解决一类数据处理问题。Visual C+ Program Design6.2.2 安排车厢顺序安排车厢顺序v数据结构的好坏，直接关系到程序设计的性能。v如图6-1所示的轨

12、道站，车厢按顺序排列进站，然后出站以组成一列火车，问题是火车以什么样的车厢顺序组合是可能的？ 3，2，1，5，4 是可能的 5，3，4，2，1是不可能的Visual C+ Program Design3，2，1，5，41，2，3，4，5轨道站图6-1 轨道站示意图Visual C+ Program Designv一系列车厢顺序放在rail.txt中，先判断Yes或No。文件的结构有许多组数据，每组数据的每一行上只有一个整数N，表示火车由N节车厢组成。N为0表示文件处理完毕。根据非0的N，规定进站的车厢以1，2，3，.，N的顺序排列。之后的每一行表示一种车厢顺序组合，必须判断Yes或No。若读入

13、的行中只有一个0表示本组数据结束，每组数据的输出中间应有空行。v轨道站是典型的栈结构。栈只能对栈顶元素进行操作。Visual C+ Program Designv如果读入一个车厢号，该车厢可能还没有进站，此时将若干节车厢进站，直到该车厢进站为止。v对于栈顶元素判断是否当前车厢，是则出站，转入下一个循环，否则退出循环输出No。v循环一直进行到读完所有的车厢。每一次循环都应保护最后读入的车厢号信息，以便判断下一次读入的车厢号是否已经进站。v输入文件、程序和运行结果如下：Visual C+ Program Designv/ 安排车厢顺序栈版本v/=v#includev#includev#includ

14、ev#includevusing namespace std;v/-vint main()v ifstream in(rail.txt);v for(int n,line=0; inn & n & in.ignore(); )v cout(line+ ? n:);v for(string s; getline(in, s) & s!=0; )v istringstream sin(s);v stack st;v for(int last=0,coach; sincoach; st.pop()v for(int p=last+1; p=coach; +p) st.push(p);v if(las

15、tcoach) last=coach;v if(st.top()!=coach) break;v v cout(!sin ? Yesn : Non);v v v/=YesNoYesVisual C+ Program Designv该程序使用了STL中的容器针对每组数据先读入一个整数，以确定文件数据是否已结束，然后用in.ignore操作滤去文件在读去整数后的回车，然后循环读入一行，在确认不是0的情况下，处理行中每个元素，方法是建立一个string流，从该流中读入每个整数，string流需要头文件sstream，而容器stack需要头文件stack。v每读入一个整数，做相应的栈操作，压入或弹出。

16、在退出循环后，输出Yes或No的动作取决于string流中数据是否已经读完，读完为Yes,否则为No。Visual C+ Program Designv若数据文件庞大，设计几千组数据，每组数据设计上千个元素，这时候数据结构就很关键。若用向量来做压入和弹出操作，效率就不高。可以想象，向量头上的元素删除时，后面所有的元素要前移，而在头上插入元素时，所有的元素要后移。这些附加操作在stack中是不必的。Visual C+ Program Design6.2.4 向量法向量法v由于向量在头上插入操作效率不高，所以类库并不主张这种操作，连专门的操作都不提供，故只能用很“丑陋”的带两个参数的insert操

17、作，如：Visual C+ Program Designv/ 安排车厢顺序向量版v/=v#includev#includev#includev#includevusing namespace std;v/-vint main()v ifstream in(rail.txt);v for(int n,line=0; inn & n & in.ignore(); )v cout(line+ ? n:);v for(string s; getline(in, s) & s!=0; )v istringstream sin(s);v vector st;v for(int last=0,coach;

18、sincoach; st.erase(st.begin()v for(int p=last+1; p=coach; +p) st.insert(st.begin(),p);v if(lastcoach) last=coach;v if(st.front()!=coach) break;v v cout1v在小于47的自变量下求值，函数可以用int类型来表示，比较下面的四种算法的时间耗用：Visual C+ Program Designv/ Fibonacci数列四种方法比较v/=v#includev#includev#includev#includevusing namespace std;v

19、/-vint fibo1(int n)v if(n=0) return 0;v if(n=1) return 1;v return fibo1(n-1)+fibo1(n-2);v/-vint fibo2(int n)v int a=0, c;v for(int b=1,c,i=2; i=n; +i)v c=a+b, a=b, b=c;v return c;v/-vint fibo3(int n)v vector v(n+1,0); v1=1;v for(int i=2; i=n; +i)v vi = vi-1+vi-2;v return vn;v/-vint fibo4(int n)v ret

20、urn (pow(1+sqrt(5.0)/2,n)-pow(1-sqrt(5.0)/2,n)/sqrt(5.0);v/-Visual C+ Program Designvint main()v int a;v clock_t start=clock();v for(int i=1; i5; +i)v a=fibo1(35);v coutFibo1s time was: (clock()-start)/CLK_TCKn;v v start=clock();v for(int i=1; i5; +i)v a=fibo2(35);v coutFibo2s time was: (clock()-sta

21、rt)/CLK_TCKn;v start=clock();v for(int i=1; i5; +i)v a=fibo3(35);v coutFibo3s time was: (clock()-start)/CLK_TCKn;v start=clock();v for(int i=1; i5; +i)v a=fibo4(35);v coutFibo4s time was: (clock()-start)/CLK_TCKn;v/=Fibo1s time was： 1.625Fibo2s time was： 0Fibo3s time was： 0Fibo4s time was： 0Visual C

22、+ Program Designv2.性能分析：递归最先出局Fibo1使用递归方法，比较容易编程。递归在C+中是使用栈机制来实现的，每深入一层，都要占去一块栈数据区域，对于嵌套层数深的一些算法，空间上会以内存崩溃而告终，而且递归带来了大量的函数调用，带来了许多额外的时间开销，从本程序的测试结果看，其他三个算法还没有使上劲，递归算法就被出局了。Visual C+ Program Designv3.性能分析：其他各有千秋 函数fibo2、fibo3、fibo4在循环次数少于10000的情况下都看不出彼此的明显耗时差别，当循环加到1000000次的时候，分别就n取15、30、45，对三个算法的耗时分

23、别进行测试 n = 15时： n = 30时： n=45时：Fibo2s time was：0.141Fibo3s time was：1.407Fibo4s time was：2.109Fibo2s time was： 0.234Fibo3s time was： 2.219Fibo4s time was： 2.093Fibo2s time was： 0.328Fibo3s time was： 2.954Fibo4s time was： 2.187Visual C+ Program Design算法：迭代法算法：迭代法 优点：节省空间，节省时间优点：节省空间，节省时间缺点：编程相对复杂缺点：编程

24、相对复杂1. int fibo2 (int 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. Visual C+ Program Design算法算法3：向量迭代法：向量迭代法 优点：节省时间优点：节省时间 缺点：缺点：n越大，占用堆空间越多越大，占用堆空间越多1. int fibo3 (int n)2. 3. vector v(n+1, 0); 4. v1 = 1;5. for (int i=2; i=n; +i)6. vi = vi-1 + vi-2;7. return vn

25、;8. Visual C+ Program Design算法算法4：直接计算法：直接计算法 优点：节省时间优点：节省时间 缺点：引入了浮点计算缺点：引入了浮点计算1. int fibo4 (int n)2. 3. return 4. ( pow ( (1+ sqrt ( 5.0 ) ) / 2, n)5. pow ( (1 sqrt ( 5.0 ) ) / 2, n) )6. / sqrt ( 5.0 ) ;7. Visual C+ Program Designfibo2：在讲究性能的场合中使用，它省空间省时间，但在n很大的场合中，性能比不上fibo4fibo3：可以数组代替向量，提高低级编程

26、的性能，它易编易用，还可以读取中间项的值，但在一味追求性能的场合中，比不上fibo2fibo4：在n不太大时，与fibo2相当，在n趋向很大时，其性能优势便充分体现Visual C+ Program Design6.3.3 选择算法选择算法v根据从文件中读取的自变量，来求解第n项的值。规定数据文件为fibo.in。v以fibo2和fibo3来比较，fibo3利用了向量逐项求值，因此可以将各个自变量对应的F(n)通过一个循环预置在向量中，使得所读入的值只需访问一次向量下标就可以得到所求的解。Fibo2则必须每次读入自变量的值后，都展成循环，以求F(n)。程序如下：Visual C+ Progra

27、m Designv/ Fibonacci数列两种方法比较v/=v#includev#includev#includev#includevusing namespace std;v/-vint main()v ifstream in(fibo.in);v ofstream out(fibo.out);v clock_t start=clock();v for(int n; inn & n; )v int a=0;v for(int b=1,c,i=2; i=n+2; +i)v c=a+b, a=b, b=c;v outaendl;v v coutFibo2s time was: (clock()

28、-start)/CLK_TCKn;v in.seekg(0); / goto beginning of filev start=clock();v vector v(47,1);v for(int i=3; in & n; ) outvnendl;v coutFibo3s time was: (clock()-start)/CLK_TCKn;v/=Visual C+ Program Designv对于文件中含有10000个数据时，测得：Fibo2s time was： 1.735Fibo3s time was： 1.768v对于文件中含有30000个数据时，测得：Fibo2s time was

29、： 5.562Fibo3s time was： 1.780vfibo2随着文件数据量的增多，耗时成比例地增大，fibo3却对文件数据量增多，反映“迟钝”，故认为fibo3比fibo2优。Visual C+ Program Design6.4.1 求解积分问题求解积分问题v函数为1/x，积分从l开始，当终点值大于l时，积分值为正，小于l大于0时，值为负，见图6-2，b点在l点的右边，所以l到b的积分值将是正值。文件integral.txt中存放着一系列的终点值，根据终点值求积分值，输出结果精确到3位小数。图 6-2 求1,6区域f(x)的积分0lbyf(x) =1/xxVisual C+ Pro

30、gram Designv数值计算设计精度问题，大多数需要靠求值逼近，算法一般表示为下列的模型： 新变量 = 初值 FOR(循环变量=循环初值;|新变量-老变量|逼近精度;循环迭代) 老变量 = 新变量; 新变量 = 计算新值; 返回新变量的值Visual C+ Program Design6.4.2 矩形法矩形法v积分的通常方法是将区域切割成一个个的小矩形，然后求这些小矩形的和。可以将切割小矩形的数量作为循环迭代变量，在前后两个同精度下的小矩形的差，作为逼近是否达到要求的比较的客体。v以下为文件内容、程序和运行结果：Visual C+ Program Designv/ 矩形积分v/=v#inc

31、ludev#includev#includevusing namespace std;v/-vdouble g(double x)v return 1/x;v/-vdouble rectangle(double a, double b, double(*f)(double)v double w=b-a, sumNew=w*(f(a)+f(b)/2, sumOld=0;v for(int n=1; abs(sumNew-sumOld)=1e-4; n*=2)v sumOld=sumNew;v sumNew=0;v for(int i=0; in; +i)v sumNew += f(a + w*(

32、i+0.5)/n);v sumNew *= w/n;v v return sumNew;v/-vint main()v ifstream in(integral.txt);v coutb; )v coutrectangle(1,b,g)n;v/=1.0993.320-3.010-0.000-9.97611.513Visual C+ Program Designv该函数为一种逼近的算法，有三个参数，前两个参数为积分的起止值，第三个参数为所积的函数。逼近算法的循环变量n采用成倍迭代，矩阵宽度为w，随矩阵的数量n的增长而反比例地减少。这里第i个矩阵的高为函数值f(a+w(i+0.5)。积分初值w(f

33、(a)+f(b)/2可以看做是n=1时的最初矩阵划分的面积。v其中一个积分函数参数，是一个所积函数的指针，这种将被积函数以参数形式传递的形式，是为了使其适用于其他被积函数的积分，从而具有通用性。Visual C+ Program Design6.4.3 辛普生法辛普生法v变步长辛普生公式是从变步长梯形公式演化而来，原理是将积分面积划分为一个个的小梯形，求和，采用逼近算法得到。变步长梯形公式的初值为：Tn = h/2 *(f(a)+f(b)v其中n=1，h=b-a，图6-3，6-4所示：Visual C+ Program Designx0abyxf(x) 0abyf(a) f(b) h图6-3

34、a,b区域f(x)所包围的面积图6-4 梯形公式计算面积Visual C+ Program Designv 变步长梯形公式计算面积的近似值为：1220()22nnhnkkThTf xv 2n即将区间a,b划分成2n等分，该公式是，一半的面积由前面的近似公式给出，另一半由原n等分的中值小梯形和的一半给出，如图6-5所示：Visual C+ Program Design0yxabxiXi+1f(xi)f(xi+1)图 6-5 变步长梯形法计算区域划分Visual C+ Program Designv 变步长辛普生公式采用了比矩形更有效的近似计算公式：2243nnnTTIv T2n和Tn分别是划分为

35、2n个n个梯形的梯形和。辛普生公式通过前后两次的梯形划分和只差来逼近。如果它落在一个精度范围内，则认为所求积分的近似度已经达到要求。如：Visual C+ Program Designv/ 辛普生积分v/=v#includev#includev#includevusing namespace std;v/-vdouble g(double x)v return 1/x;v/-vdouble simpson(double a, double b, double(*f)(double)v double I2n=0,h=b-a,T2n=h*(f(a)+f(b)/2,In=T2n,Tn;v for(i

36、nt n=1; abs(I2n-In)1e-3; n+=n,h/=2.0)v In=I2n; Tn=T2n; / In老积分值v double sigma=0;v for(int k=0; kn; k+)v sigma += f(a+(k+0.5)*h);v T2n=(Tn+h*sigma)/2;v I2n=(4*T2n-Tn)/3; / I2n新积分值v v return I2n;v/-vint main()v ifstream in(integral.txt);v coutb; )v coutsimpson(1,b,g)n;v/=Visual C+ Program Designv精度要求很

37、高的情况下，如10-10以上，就可以看出两者的计算时间差异，将循环变量n改为函数体内的局部变量而不仅是for循环的局部变量，就能够观察对于特定的精度要求Epsilon值下的矩阵或梯形分割数。对于Epsilon为0.001时的测试结果见表6-1，变步长辛普生公式、变步长梯形公式与变步长矩形公式三种算法比较，可看出，变步长辛普生公式算法更有效，循环更快到达精度要求。Visual C+ Program Design序积分值矩阵或梯形分割数矩阵法梯形法辛普生法11.099256323223.32020485121283-3.01020485121284-0.0002215-9.976209715252

38、4288131072611.51383886082097152524288表 6-1 三种算法的比较Visual C+ Program Design6.5.1 集合元素访问集合元素访问vC+算法库是STL的一部分，C库不能替代，因为算法实施的元素可以是具有自生自灭和多态的复杂对象，而不仅仅是单纯空间意义上的变量。v算法库总是对元素集合进行操作，标准算法调用中的函数，需要指出元素集合的首尾位置，首位置的元素是包含在算法处理中的，尾位置是不包含在算法处理中的。Visual C+ Program Designv因此，若有10个元素的其中的6个元素需要处理，见图6-6，则首位置就是1号元素，尾位置就是

39、7号元素，指示元素位置并不是用下标，而是用迭代器对象，就是指针，它的类型名称为“容器类型:iterator”,要处理的数据为整个容器的所有内容，只要取容器的begin()和end()成员即可。begin()指向0的那个元素，end()则指向10的那个元素(其实是不存在的那个元素)。Visual C+ Program Designvector a (10);/ 下面表示待处理的元素vector b (a.begin ()+1, a.begin ()+7 ); 0123456789首尾待处理的元素图6-6 算法库总是对元素集合进行操作Visual C+ Program Design6.5.2 判断

40、字符串相等判断字符串相等1v如判断存储在文件string.txt中的若干对字串的相等性。相等为Yes，否则为No。该种字串仅含0和1，如果字串中0和1的个数分别相等，则该对字串为相等。v现在用C+算法库求解，由于string类对于读取文件中字串以及比较都很方便，所以，用string类的对象来逐对存放字串，然后将字串分别排序后对其进行比较是直接的思路。Visual C+ Program Designv / 判断字串相等版本一v /=v #includev #includev #includev using namespace std;v /-v int main()v ifstream in(s

41、tring.txt);v for(string s,t; inst; )v sort(s.begin(), s.end();v sort(t.begin(), t.end();v cout(s=t ? yesn : non);v v /=01010111100110011001100000011110011String.txtnoyesVisual C+ Program Designv程序中用到了算法sort调用，故要包含算法库头文件algorithm,string对象s和t中存储的是从文件中读取的字串，字串中的字符可以通过下标操作来访问，字串有头有尾有长度，可以看做是char类型的容器，所以

42、可以对其进行排序(sort)算法。v使用了算法库，编程变得简单了，然而从问题的实质出发，如果有数千对字串需要进行比较，每个字串可能长达1024个字符，会发现，该算法并不十分有效！Visual C+ Program Design6.5.3 判断字串相等判断字串相等2v基本的排序算法需要对所有元素进行两重循环的操作，最快的排序算法也需要O(nlogn)数量级的运算次数，然而，如果仅对字串分别数一下0和1的个数，再比较其个数值，效率会更高,如：Visual C+ Program Designv/ 判断字串相等版本二v/=v#includev#includev#includevusing namesp

43、ace std;v/-vint main()v ifstream in(string.txt);v for(string s,t; inst; )v int sc1=count(s.begin(), s.end(),1);v int sc0=count(s.begin(), s.end(),0);v int tc1=count(t.begin(), t.end(),1);v int tc0=count(t.begin(), t.end(),0);v cout(sc1=tc1 & sc0=tc0 ? yesn : non);v v/=Visual C+ Program Designvcount计

44、数也包含在C+标准库中，由于count算法只有一重循环的处理时间，虽然编程中有四次count调用，但比较排序算法，对于元素个数激增时，其效率能明显体现出来。Visual C+ Program Design6.5.4 判断字串相等判断字串相等3v根据问题描述，字串中非1即0，所以“0”的个数在总长度已知的情况下，可以不使用count算法，通过并列的判断总长度的相等性而直接得到：Visual C+ Program Designv / 判断字串相等版本三v /=v #includev #includev #includev using namespace std;v /-v int main()v

45、ifstream in(string.txt);v for(string s,t; inst; )v int s1=count(s.begin(), s.end(),1);v int t1=count(t.begin(), t.end(),1);v coutst”，它使s和t获得循环中赖以处理的数据，同时其结果本身又是条件判断，实际上充当了循环变量初始化、条件判断和循环迭代三重身份，将定义“string s，t”放在循环结构头部，可以使得对象定义局部化，从而使过程块的数据能见度更加合理。Visual C+ Program Design6.5.5 剩余串排列剩余串排列1vC+算法库安全，高效和标

46、准，所以在一般情况下，能用算法库来改善编程质量的要尽量用，但是，要真正的用好算法库，还取决于对问题的准确把握。Visual C+ Program Designv有一个数据文件remainder.txt内含一些成对的字串，对于第一个字串，要去掉两个字串中相等的部分，并按字符顺序输出。v一种直观的解是，先对第一个字串排序，然后逐个字符在第二个字串中搜索，把搜索不到的字府输出，就是所要的结果。 然而，算法库中有一个集合差运算set_difference,而且要求两个集合容器是已经排好序的。故有下面的程序：Visual C+ Program Designv / 剩余串排列v /=v #includev

47、 #includev #includev using namespace std;v /-v int main()v ifstream in(remainder.txt);v for(string s,t,u; inst; u=) v sort(s.begin(),s.end();v sort(t.begin(),t.end();v set_difference(s.begin(),s.end(),t.begin(),t.end(),back_inserter(u);v coutuendl;v v /=computer programwrite programthatwill asktheus

48、er forawhole numberremainer.txtcetuweitillwesuhlowVisual C+ Program Designvset_difference的参数为三个集合，表示对两个集合进行差运算，其结果放入另一集合，其中两个源集合，描述集合的首尾区间：一个结果集合，描述容器起点，当然不但要求集合非空，而且还要足够大，能容纳集合差运算的结果。vback_inserter称为插入子，是一种迭代子，表示对参数的最后位置进行插入操作，而且返回的值仍是最后位置。所以Back_inserter对容器的操作，就是不断在容器尾部增加新元素，然后总是指向尾部位置，充当着一个有足够空间存

49、放结果的集合起始位置。Visual C+ Program Design6.5.6 剩余串排列剩余串排列2v然而注意到，对两个集合分别排序的代价是大的，实际上，t串无须排序，下面的解决方法，更加高效：Visual C+ Program Designv / 剩下串的排列版本二v /=v #includev #includev #includev using namespace std;v /-v int main()v ifstream in(remainder.txt);v for(string s,t; inst; )v sort(s.begin(), s.end();v for(int i=

50、0; is.length(); +i)v if(t.find(si)=string:npos) coutsi;v coutendl;v v /=Visual C+ Program Designv因为输出是针对每对字串中第一个字串字符顺序，所以对s串排序是必要的，又因为对t串实施string的find操作，是线性搜索，所以无须预先对其进行排序，对每个已经排好序的s中的字符，只要用find搜索一下就能知道是否要输出该字符了。Visual C+ Program Designv程序中的for循环将循环s.length()次，每次循环都在t中搜索一次，即最多做t.length()次比较，所以for循环实

51、际上至多做了sxt次比较操作，这比前面的程序中既要做t的排序又要做集合差运算来说，要省力的多。v在STL中，有支持一般容器的find算法，也可以用在t上：if(find(t.begin(),t.end(),si)=t.end() coutsi;Visual C+ Program Design6.6.1 预留向量空间预留向量空间vC+提供了动态内存分配的new和delete操作，多用在内存需求不定的场合，如果需要处理的数据变动范围很小，可以用STL中的通用容器来做。v如要统计一片文章中的段落数(约1000个)，并且按每个段落的单词数进行排序输出。由于不知道具体段落数，文件输入时无法决定存放的向量

52、或数组有多大，所以无法进行动态内存申请，可以使用一种STL容器，适合元素不断扩张的要求。若大概知道元素的个数，可以用reserve操作预留空间，代码如下：Visual C+ Program Designv/ 清点单词数v/=v#includev#includev#includev#includev#includevusing namespace std;vtypedef multimap Mmap;v/-vint main()v ifstream in(abc.txt);v vector abc;v / abc.reserve(1100);v Mmap nums;v int n=0;v for

53、(string s; getline(in,s); )v istringstream sin(s);v int num=0;v for(string t; sint; num+);v if(num)v nums.insert(Mmap:value_type(num, n+);v abc.push_back(s);v v v for(Mmap:iterator it=nums.begin(); it!=nums.end(); +it)v coutsecondendl;v/=Visual C+ Program Designv该程序对每次从文件读入的段落getline(in,s)先行清点其单词数，过

54、滤单词数为0的段落，对于非空段落，将其保存在向量中，并将该单词数，放入map中进行自动排序，最后，按段落中单词数的大小为顺序输出每个段落。v对于每一个段落，清点单词数的方法为先将段落视为string流，然后从该输入流中逐个读入单词，边读边计数到num变量中。Visual C+ Program Designv该程序中有一条备用语句”abc.reserve(1100)”,时为了应付向量不断插入所引起的频繁的内存申请释放操作。执行语句后，abc向量一开始就会预留1100空间，供反复插入之用，reserve不会改变向量中实际有的元素数。 reserve可以控制向量既不浪费太多空间，又使插入效率提高，还

55、能应付元素个数不确切的复杂局面。Visual C+ Program Design6.6.2 蛮做素数判断蛮做素数判断v可能没有办法在栈区域中面对大量数据创建。如求1到1亿中素数的个数。v对于这个问题，可以先编一个判断素数的函数“bool isPrime(int n)”，自变量是一个正整数，结果是布尔型的true和false，然后从1到1亿循环调用函数isPrime，统计返回true的个数，见下面的程序：Visual C+ Program Designv/ 求素数个数v/=v#includev#includevusing namespace std;v/-vbool isPrime(int n)

56、v int sqrtn=sqrt(n*1.0);v for(int i=2; i=sqrtn; +i)v if(n%i=0) return false;v return true;v/-vint main()v int num=0;v for(int i=2; i=100000000; +i)v if(isPrime(i)v num+;v coutnumendl;v/=Visual C+ Program Designv 函数isPrime所了一点优化，优化原理是根据一个简单定理：v 若合数n=x*y,令xy,则x ,ynnv 运行发现，程序要十几分钟，原因在于判断素数的工作没有积累，对于每个自

57、然数，测试都是从头做起，所以对于大量数据测试的工作，其算法显得很笨拙。Visual C+ Program Design6.6.3 空间换时间空间换时间v如果直接用素数的筛法，建立一个有1亿元素的容器，再在算法中适当做些优化，就可以在数十秒内得到结果。可以选择位集bitset来实现，因为位集编程简单，效率不错，而且占用尽可能少的空间。明智的办法时改用堆空间，即动态内存空间。下面是用位集来实现的一个版本：Visual C+ Program Designv/ 求素数个数筛法版v/=v#includev#includevusing namespace std;v/-vint main()v bitse

58、t* p = new bitset;v p-set();v for(int i=2; itest(i)v for(int j=i*i; jsize(); j+=i) / 完成素数标记v p-reset(j);v int num=0;v for(int i=2; itest(i)v num+;v coutnumset()是将位集容器中所有元素置1，p-reset()是将所有元素置0.p-test(i)是取第i个元素值,p-size()就是100000000.v如果与分配1亿个向量相比，向量操作比位操作离系统更远，内在的操作更多，所以在上亿次的下标访问中，时间就明显多耗。而位集容器是不能扩充的定长

59、容器，它由一个常量参数确定空间大小。Visual C+ Program Design6.7.1 C编程编程揭示：通过无原则的代码优化来简化程序的执行步骤,从而提高性能.它会影响可读性,并需要对程序的内存布局有深刻的了解,这一般是编程课的后继学习内容做法：尽量去掉组织程序所花费的代价:少用调用频繁的函数;通过指针间访数据;尽可能不用类;无原则数据共享;用C库不用C+库Visual C+ Program Designv / 判断字串相等版本四v /=v #includev #includev /-v int cnt(char* a)v int num=0;v while(*a) if(*a+=1)

60、 num+;v return num;v /-v int main()v freopen(string.txt,r,stdin);v for(char a1025, b1025; scanf(%s,a)0 & scanf(%s,b)0; )v printf(%s,strlen(a)=strlen(b) & cnt(a)=cnt(b) ? yesn:non);v /=Visual C+ Program Designv程序采用了文件指针，指向一个直接操纵硬件驱动设备驱动程序的文件结构变量，因而避免了一些创建文件对象的内在开销。然而在编程上，显然比直接操作文件对象要复杂，该文件操作既要顾头，定义指针