算法效率与程序优化

算法效率与程序优化在信息学竞赛中，常遇到程序运行超时的情况。然而，同一个程序设计思想，用不同算法，会有不同的运行效率；而即使是同样的算法，由于在代码的细节方面设计有所不同，执行起来效率也会有所不同。当遇到所需时间较长的问题时，一个常数级优化可能是AC的关键所在。下面，我们就从代码细节与算法设计两方面，比较不同程序执行时间的异同，从而选择其中较优的算法，提高程序运行效率。本试验所采用的环境是：CPUCeleron3.06GHz，内存248M，操作系统WindowsXPSP2，程序语言C。编译环境Dev-c++。以下称为1号机。配置略好于NOIP标准测试机CPU2.0GHz。第一章各种运算的速度一、基本运算的速度为了增强算法效率的计算准确性，我们采用重复试验20次取平均值的做法。每次试验运行100000000次。基本运行时间，是指在准备计算的运算复杂度之外，只包括循环控制变量的加减与比较所消耗的时间。要从实际运行时间中减去基本运行时间，才是这种运算真正的运行时间，称为净运行时间。#includestdio.hmain(){inti,j;doublea,b,sum=0;for(j=0;j20;j++){//此处添加随机数产生a=clock();for(i=0;i100000000;i++);//此处添加运算b=clock();printf(%lf\n,b-a);sum+=b-a;}printf(ans=%lf,sum/20.0);getch();}运行平均时间是：202.3ms。（1）赋值运算净运行时间0.8ms，与基本运行时间202.3ms相比，可忽略不计，故以后将赋值运算作为基本运行时间的一部分，不予考虑。（2）加法运算产生随机数：x=rand();y=rand();循环内加法：t=x+y;下面的各种简单运算只是更改运算符即可，不再写出代码。净运行时间41.45ms，即：在1s的时限中，共可进行(1000-202.3)/41.45*10^8=1.9*10^9次加法运算，即：只通过循环、加法和赋值的运算次数不超过1.9*10^9.。而应用+=运算，与普通加法时间几乎相同，所以+=只是一种方便书写的方法，没有实质效果。同样的，各种自运算并不能提高效率。（3）减法运算净运行时间42.95ms，与加法运算基本相同。可见，在计算机内部实现中，把减法变成加法的求补码过程是较快的，而按位相加的过程占据了较多的时间，借用化学中的一句术语，可以称为整个运算的“速控步”。当然，这个“速控步”的运行速度受计算机本身制约，我们无法优化。在下面的算法设计中，还会遇到整个算法的“速控步”，针对这类情况，我们要对占用时间最多的步骤进行细心优化，减少常数级运算次数。（4）乘法运算净运行时间58.25ms，明显比加减法要慢，但不像某些人想象的那样慢，至少速度大于加减法的1/2。所以在实际编程时，没有必要把两个或三个加法变成乘法，其实不如元素乘常数来得快。不必“谈乘色变”，实际乘法作为CPU的一种基本运算，速度还是很快的。以上四种运算速度都很快，比循环所需时间少很多，在普通的算法中，每个最内层循环约含有4-5个加、减、乘运算，故整个算法的运行时间约为循环本身所需时间的2倍。（5）除法运算净运行时间1210.2ms，是四种常规运算中最慢的一种，耗时是加法的28倍，是乘法的21.5倍，确实如常人所说“慢几十倍”，一秒的时限内只能运行8.26*10^7次，不足一亿次，远大于循环时间。所以，在计算时应尽量避免除法，尤其是在对时间要求较高的内层循环，尽量不安排除法，如果整个循环中值不变，可以使用在循环外预处理并用一个变量记录，循环内再调用该变量的方法，可以大大提高程序运行效率。（6）取模运算净运行时间1178.15ms，与除法运算速度几乎相当，都非常慢。所以，取模运算也要尽量减少。在大数运算而只要求求得MODN的值的题目中，应尽量利用数据类型的最大允许范围，在保证不超过MAXINT的前提下，尽量少执行MOD运算。例如在循环数组、循环队列的应用中，取模运算必不可少，这时优化运算便十分重要。可利用计数足够一定次数后再统一MOD，循环完后再MOD，使用中间变量记录MOD结果等方法减少次数。在高精度计算中，许多人喜欢边运算边整理移位，从而在内层循环中有除、模运算各一次，效率极低。应该利用int的数据范围，先将计算结果保存至当前位，在各位的运算结束后再统一整理。以下是用统一整理法编写的高精度乘法函数，规模为10000位。inta[10000]={0},b[10000]={0},c[10000]={0};voidmul(){inti,j,t;for(i=0;i10000;i++)for(j=0;j10000-i;j++)c[i+j]+=a[i]*b[j];for(i=0;i9999;i++){c[i+1]+=c[i]/10;c[i]%=10;}}以上函数运行后，平均用时276.55ms。以下是边运算边整理的程序。voidmul(){inti,j,t;for(i=0;i10000;i++)for(j=0;j10000-i;j++){c[i+j+1]+=(c[i+j]+a[i]*b[j])/10;c[i+j]=(c[i+j]+a[i]*b[j])%10;}}以上函数运行后，平均用时882.80ms。统一整理与边整理边移位相比，快了3.2倍，有明显优势。故尽量减少除法、取模运算的次数，是从常数级别降低时间复杂度的方法。（7）大小比较if(xy)x=y;净运行时间39.1ms，与加法运算速度相当。故比较运算也属于较快的基本运算。二、位运算的速度（1）左移、右移x1;x1;净运行时间无法测出，证明位运算速度极快。而使用自乘计算需要64.1ms，自除运算需要164.85ms，所以尽可能使用位运算代替乘除。（2）逻辑运算t=x|y;t=x^y;t=x&y;净运行时间约30ms，比加法运算（约40ms）快较多，是因为全是按二进制位计算。但加减与位运算关系并不大，所以利用位运算主要是利用左右移位的高速度。三、数组运算的速度（1）直接应用数组for(i=0;i10000;i++)for(k=0;k10000;k++)t=q[k];净运行时间39.85ms。这里计算了内层循环的时间。若改为for(i=0;i100000000;i++)t=q[0];则净运行时间为1.50ms，很快，与202.3ms的循环时间相比，可以忽略。故应用数组，速度很快，不必担心数组寻址耗时。同时我们发现，循环耗时在各种运算中是很大的，仅次于乘除，故我们要尽量减少循环次数，能在一个循环中解决的问题不放在两个循环中，减少循环变量次数。（2）二维数组for(i=0;i5000;i++)for(k=0;k5000;k++)t=z[i][k];实际运行时间为80.45ms，若规模扩至10000则10s内无法出解，由于频繁访问虚拟内存。可以试想，若物理内存足够大，则运行时间约为320ms，仅为202.3ms的基准运行时间的3/2，差距似乎并不是很大；由此推得其净运行时间约为120ms。但相较加、减等简单操作，速度仍为3倍，尤其与几乎不需时间的一维数组相比差距巨大。尤其是在计算中，二维数组元素经常调用，时间效率不可忽视。所以，对于已知数目不多的同样大小的数组，可用几个变量名不同的一维数组表示，如x、y方向，两种不同参数，而不要滥用二维数组。在滚动数组中，可用两个数组交替计算的方式，用二维数组同样较慢。四、实数运算的速度测试方法与“基本运算”类似。（次数：100000000，单位：ms）运算符=+-*/%longint43.0531.3-74.7569.55299.65360.5int6441.4514.957.9566.41243.451858.85double46.1510.2512.633.651753.55--由上表可见，涉及乘除、取模时int64很慢，要慎用；int显然最快，但对大数据要小心越界。若一组变量中既有超出int的，又有不超过int的，则要分类处理，不要直接都定义成int64，尤其在乘除模较多的高精度过程中。以上讨论了主要基本运算的速度问题。概括起来说，除、模最慢，二维数组较慢，加减乘、逻辑位运算、比较大小较快，左右移位、一维数组、赋值几乎不需要时间。而循环for或while语句十分特殊，它的运算速度大于判断大小、自加控制变量所用时间之和，无论采用内部if判断退出，还是在入口处判断，都回用去约200ms的时间。所以尽量减少循环次数，是优化算法的关键。对于双层或多层的循环，应把循环次数少的放在最外层，最大的循环位居最内部，以减少内层循环的执行次数。第二章各种算法的速度一、排序算法的速度1.冒泡排序for(i=0;i20000;i++)a[i]=rand();s=clock();for(i=0;in;i++)for(j=0;ji;j++)if(a[i]a[j]){t=a[i];a[i]=a[j];a[j]=t;}b=clock();运行时间：1407ms2.选择排序for(i=0;i20000;i++)a[i]=rand();s=clock();for(i=0;in;i++){max=0;for(j=0;jn;j++)if(a[j]a[max])max=j;b[i]=a[max];a[max]=-1000000;}t=clock();运行时间：1220ms3.插入排序for(i=0;i20000;i++)a[i]=rand();s=clock();for(i=0;in;i++){t=a[i];for(j=i-1;j=0;j--)if(a[j]t)break;for(l=i;lj+1;l--)a[l]=a[l-1];a[j+1]=t;}t=clock();运行时间：984ms以上三种都是O(n^2)的排序，其中插入排序最快，且可以用指针加以优化。从编程复杂度上，冒泡排序最简单。从算法的稳定性上，插入排序是稳定的，即排序后关键字相同的记录顺序不改变，特别适用于表达式处理等问题。一般的选择排序是不稳定的，但这里给出的程序由于使用了人类最原始的方法，即依次选择最大的并排除，故是稳定的。冒泡排序是不稳定的，涉及必须保持数据原顺序的题目时不能选择冒泡排序，而必须选择稳定的排序方式。以下试验所采用的环境是：CPUIntelCore1.73GHz*2，内存512M，操作系统Windows7UltimateBeta，程序语言C。编译环境Dev-c++，以下称为2号机。由于CPU速度较慢，且操作系统占用资源较多，程序运行速度明显减慢，第一章的“基本运行测试”需要时间约为前者的2倍，即为406ms。故第一章的程序运行时间此处应乘2。4.快速排序的标准版#defineMAX10000000inta[MAX];intp(intl,intr){intx=a[l],i=l-1,j=r+1,t;while(1){do{--j;}while(a[j]x);do{++i;}while(a[i]x);if(ij){t=a[i];a[i]=a[j];a[j]=t;}elsereturnj;}}voidq(intl,intr){intn;if(lr){n=p(l,r);q(l,n);q(n+1,r);}}运行时间：2948ms。注意：不要以为三种平方级排序方法的速度与快速排序可比拟，因为平方级的数据范围是10000，而快速排序的范围是10000000。对于10000的数据，快速排序只需3.1ms。另外，快速排序不是稳定的排序，需要保持原顺序的不能用此法。voidp(intl,intr){intx=a[l],i=l-1,j=r+1,t;if(lr){while(1){do{--j;}while(a[j]x);do{++i;}while(a[i]x);if(ij){t=a[i];a[i]=a[j];a[j]=t;}elsebreak;}p(l,j);p(j+1,r);}}若程序改为