论细节优化的一些方法.doc

论细节优化的一些方法广东北江实验学校 卢彦丞 指导老师 黄叶亭【目录】1. 内容摘要2. 关键词3. 正文WAY 1 多用位运算WAY 2 使用合适的类型WAY 3 数组下标上的优化WAY 4 判重处理采用Hash表WAY 5 能不用循环就不用循环WAY 6 减少重复运算WAY 7 把小循环放在外面WAY 8 循环合并WAY 9 与循环无关的条件应直接放在循环外WAY 10 减少条件判断另：标记时如何节省空间？4. 总结1. 内容摘要本文主要讲的是细节优化节省时间的一些方法，也讲了标记数组节省空间的办法。2. 关键词：细节优化 代码优化3. 正文一个程序超时怎么办？如何优化？有两种方法：“从大处着手”和“从小处着手”。“从大处着手”比较难，“从小处着手”却是人人都可以做到的。这里就主要谈谈“从小处着手”的方法，即细节优化的方法。有一句谚语说：“细节决定成败。”为什么有时采用同样的算法，分数却相差这么远？这是细节优化到不到位的问题。细节优化也不容忽视。细节优化的方法有很多种，这里就列举几种关于节省时间的方法吧。WAY 1 多用位运算，少用浮点运算。 如：n div 2 可以改为 n shl 1，如果你用trunc(n/2)，那你就太不会节省时间了。一般乘以2的n次幂的式子可以改为左移，如：n*4 可以改为 n shl 2x*16 可以改为 x shl 4a*4096 可以改为 a shl 12一般乘除法比加减法、位运算慢好几十倍。所以一个数乘以一个常量，可以用左移、加法组合代替。如以下的代码A可以改成代码B，代码C可以改成代码D，将会减少运行时间。代码A：n:=0;while not eoln dobegin read(c); x:=ord(c)-48;n:=n*10+x;end;代码B：n:=0;while not eoln dobegin read(c); x:=ord(c)-48; n:=n shl 3+n shl 1+x;/10=23+21end;代码C：p:=0;while not eoln dobegin read(x); p:=p*1000+x;end;代码D：p:=0;while not eoln dobegin read(x); p:=p shl 10-p shl 4-p shl 3+x;/1000=210-24-23end;虽然繁琐了一点，但这也不失为一种尽量避免超时的好方法。WAY 2 使用合适的类型对于基于32位系统的Free Pascal，整型存取的速度从快到慢依次是longint/dword（32位）（二进制位，下同），integer/word（16位），shortint/byte（8位），int64/qword（64位）。而对于基于16位系统的Turbo Pascal和Borland Pascal，整型存取速度从快到慢依次是integer/word（16位），shortint/byte（8位），longint（32位），comp（64位）。时下竞赛常用的编译程序是Free Pascal，所以我建议大家多用longint和dword，少用其他整型。空间需求量很紧可以考虑用integer/word，还不行再考虑shortint/byte，运算十几位（十进制位）的数可以考虑用int64/qword，能不用高精度就不用高精度而对于浮点数的四种类型，建议大家看情况而用，这里列出来作比较：序号类型占用空间优点缺点1single4字节=32位加减运算快精度低占用空间少2real6字节=48位乘除运算快加减运算不如double快占用空间较少3double8字节=64位加减运算快乘除运算慢精度高占用空间较多4extended10字节=80位精度非常高运算慢占用空间多WAY 3 对于数组结构，如果空间允许的话，将其下标改为0至2n-1。如：var a:array1.10000of longint;可以改为：var a:array0.16383of longint;有人说下标改为1至2n，我认为这样不是最快的。因为计算机寻址时，是按02n-1、2n22n-1、22n32n-1、的方式寻址，而下标改为1至2n寻址时还得减1，何苦呢？而对于下标原本是1至2n的数组，如：var b:array1.1024of longint;应该改为下标从0开始：var b:array0.1023of longint;WAY 4 对于判重处理，如果空间允许，采用Hash表来标记。即hashvalue=0代表value代表的结点未出现过，可以出现；hashvalue=1代表value代表的结点出现过，不能重复第二次了。用这种时间复杂度为O(1)的算法，何乐而不为？至于标记时如何节省空间，请点击这里。WAY 5 能不用循环就不用循环。先看一段代码：for i:=1 to 1000000 dobegin for j:=0 to 5 do qj:=f(i,j); end;这段代码，j共赋了初值1,000,000次，递增了5,000,000次,与终值比较了6,000,000次。实际上，j循环只循环了六次，相信没有人没耐性去把一个简单的赋值语句写六次。如果把它写六次，就减少了12,000,000次的多余运算了。代码可改为：for i:=1 to 1000000 dobegin q0:=f(i,0); q1:=f(i,1); q2:=f(i,2); q3:=f(i,3); q4:=f(i,4); q5:=f(i,5); end；WAY 6 减少重复运算看下面这段代码：for i:=1 to 100 dofor j:=1 to 100 dofor k:=1 to 100 doai,j,k:=(2*6)*(ai-1,j,k*i+ai,j-1,k-1*(i*j)+ai,j,k-1);其中i*j运算了多少次？1,000,000次！2*6运算了多少次？1,000,000次！还有i-1和j-1也是！这真浪费！大好时光竟然浪费在重复运算上，不是浪费是什么？应该在i和j每次变动后立即算出这些表达式的值，以后就不用再计算了。代码修改为：c:=2*6;for i:=1 to 100 dobegin i1:=i-1;for j:=1 to 100 dobegin j1:=j-1;ij:=i*j;for k:=1 to 100 doai,j,k:=c*(ai1,j,k*i+ai,j1,k-1*ij+ai,j,k-1);end;end;这样，2*6只算了1次，i-1只算了100次，j-1和i*j只算了10,000次。 WAY 7 尽量把小循环放在外面，这样可以减少定初值的数量。如：for i:=1 to 100 dofor j:=1 to 5 do要定101次初值。而for j:=1 to 5 dofor i:=1 to 100 do只要定6次初值。WAY 8 合并循环，就减少了循环变量定初值、递增、比较的次数。如：把以下代码for i:=1 to 500 do xi:=f(i);for j:=1 to 500 do yj:=g(j);改成for i:=1 to 500 dobegin xi:=f(i); yi:=g(i);end;就减少了1001次无谓操作。WAY 9 与循环无关的条件应直接放在循环外，就可以避免重复判断。如：for i:=1 to 10000 doif bb then xi:=f(vi) else xi:=g(vi);应改为：if bb thenfor i:=1 to 10000 do xi:=fv(i)elsefor i:=1 to 10000 do xi:=gv(i);看似多了一个循环，实则少了9999次判断。WAY 10 用多重判断语句嵌套来减少条件判断。如：a为真的可能性约是50%，b为真的可能性约是30%，c为真的可能性约是70%，则：if a and b and c then imple;可以改为if b then if a then if c then imple;imple是一个过程也就是把“and”语句改成多重判断时，可能性越小的布尔表达式放在越外层；而if a or b or c then imple;可以技巧性地改为if not c then if not a then if not b then else imple else impleelse imple;这样做是因为竞赛中默认编译开关关于B的一项是$B-，所以无法实现“and表达式中出现假跳过后面，or表达式中出现真跳过后面”的优化功能，且竞赛不允许自设编译开关，才只能这样的。另：在设标记数组时为节省空间，考虑到标记值只需占很少空间，所以可以压缩存储，这里略讲一二。第一种情况： 标记值为0或1时，采用八位一压的方法。第二种情况： 标记值为1或2时，改为0或1，输入时减一，输出时加一，然后按第一种情况处理。也可以四个数压成一个字节，但要浪费50%的空间。第三种情况： 标记值为-1、0、1时，四个数压成一个字节，-1对应11，0对应00，1对应01。第四种情况： 标记值为0、1、2时，类似于第三种情况，0对应00，1对应01，2对应10。第五种情况： 标记值为-2、-1、0、1或-1、0、1、2或0、1、2、3时类似于第三种情况，0对应00，1对应01，-2或2对应10，-1或3对应11。第六种情况： 标记值多于4个：要占用3个二进制位，2个数压成一个shortint或byte，就会浪费2