论细节优化的一些方法

《论细节优化的一些方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、论细节优化的一些方法广东北江实验学校卢彦丞指导老师黄叶亭【目录】1.内容摘要2.关键词3.正文WAY1多用位运算WAY2使用合适的类型WAY3数组下标上的优化WAY4判重处理采用Hash表WAY5能不用循环就不用循环WAY6减少重复运算WAY7把小循环放在外面WAY8循环合并WAY9与循环无关的条件应直接放在循环外WAY10减少条件判断另：标记时如何节省空间？4.总结1.内容摘要本文主要讲的是细节优化节省时间的一些方法，也讲了标记数组节省空间的办法。2.关键词：细节优化代码优化3.正文6一个程序超时怎么办

2、？如何优化？有两种方法：“从大处着手”和“从小处着手”。“从大处着手”比较难，“从小处着手”却是人人都可以做到的。这里就主要谈谈“从小处着手”的方法，即细节优化的方法。有一句谚语说：“细节决定成败。”为什么有时采用同样的算法，分数却相差这么远？这是细节优化到不到位的问题。细节优化也不容忽视。细节优化的方法有很多种，这里就列举几种关于节省时间的方法吧。WAY1多用位运算，少用浮点运算。如：ndiv2可以改为nshl1，如果你用trunc(n/2)，那你就太不会节省时间了。一般乘以2的n次幂的式子可以改为左移

3、，如：n*4可以改为nshl2x*16可以改为xshl4a*4096可以改为ashl12一般乘除法比加减法、位运算慢好几十倍。所以一个数乘以一个常量，可以用左移、加法组合代替。如以下的代码A可以改成代码B，代码C可以改成代码D，将会减少运行时间。代码A：n:=0;whilenoteolndobeginread(c);x:=ord(c)-48;n:=n*10+x;end;代码B：n:=0;whilenoteolndobeginread(c);x:=ord(c)-48;n:=nshl3+nshl1+x;//1

4、0=2^3+2^1end;代码C：p:=0;whilenoteolndobeginread(x);p:=p*1000+x;end;代码D：p:=0;whilenoteolndobeginread(x);p:=pshl10-pshl4-pshl3+x;//1000=2^10-2^4-2^3end;虽然繁琐了一点，但这也不失为一种尽量避免超时的好方法。WAY2使用合适的类型对于基于32位系统的FreePascal，整型存取的速度从快到慢依次是longint/dword（32位）（二进制位，下同），intege

5、r/word（16位），shortint/byte（8位），int64/qword（64位6）。而对于基于16位系统的TurboPascal和BorlandPascal，整型存取速度从快到慢依次是integer/word（16位），shortint/byte（8位），longint（32位），comp（64位）。时下竞赛常用的编译程序是FreePascal，所以我建议大家多用longint和dword，少用其他整型。[空间需求量很紧可以考虑用integer/word，还不行再考虑shortint/byte

6、，运算十几位（十进制位）的数可以考虑用int64/qword，能不用高精度就不用高精度]而对于浮点数的四种类型，建议大家看情况而用，这里列出来作比较：序号类型占用空间优点缺点1single4字节=32位加减运算快精度低占用空间少2real6字节=48位乘除运算快加减运算不如double快占用空间较少3double8字节=64位加减运算快乘除运算慢精度高占用空间较多4extended10字节=80位精度非常高运算慢占用空间多WAY3对于数组结构，如果空间允许的话，将其下标改为0至2n-1。如：vara:ar

7、ray[1..10000]oflongint;可以改为：vara:array[0..16383]oflongint;有人说下标改为1至2n，我认为这样不是最快的。因为计算机寻址时，是按0～2n-1、2n～2·2n-1、2·2n～3·2n-1、……的方式寻址，而下标改为1至2n寻址时还得减1，何苦呢？而对于下标原本是1至2n的数组，如：varb:array[1..1024]oflongint;应该改为下标从0开始：varb:array[0..1023]oflongint;WAY4对于判重处理，如果空间允许，

8、采用Hash表来标记。即hash[value]=0代表value代表的结点未出现过，可以出现；hash[value]=1代表value代表的结点出现过，不能重复第二次了。用这种时间复杂度为O(1)的算法，何乐而不为？至于标记时如何节省空间，请点击这里。WAY5能不用循环就不用循环。先看一段代码：fori:=1to1000000dobegin……forj:=0to5doq[j]:=f(i,j);……end;这段代码，j共赋了初值