算法合集之《论反汇编在时间常数优化中的应用》.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,反汇编在常数因子优化中的应用,四川省成都七中,周以苏,程序优化是无止境的，其中常数因子也是决定程序运行快慢的关键之一。,然而在竞赛中，渐进时间复杂度是人们关注的重点，而同样能够决定程序运行快慢的,常数因子,优化问题却缺乏重视。,绪言,在,Visual C+,语言环境下，从特定编译器生成的汇编代码出发，我探讨了反汇编在常数因子优化中的应用，并提出了若干优化改进方案。,引例：关于,memset,函数的小实验,已知,memset,函数为,O(N),复杂度的语句。,#include,const,int,Total=1000000000;,const,int,Time=,你喜欢的合法的数值,;,char,fieldTotal/Time;,int,i,j;,int,main(),for,(;j10;j+),for,(i=0;iTime;i+),memset(field,0,sizeof,(field);,return,0;,你能直接答出,Time,值与运行速度的关系？,观看右边的,C+,程序,（假设计算机具有足够大的内存）,分析,可能你认为,Time,值不影响程序时间复杂度，因此对程序的速度无影响。,Time,值与运行速度的关系,但是，当上机实验后，你会发现，,Time,值较大或较小时运行速度会变慢，这是为什么呢？,#include,const,int,Total=1000000000;,const,int,Time=,你喜欢的合法的数值,;,char,fieldTotal/Time;,int,i,j;,int,main(),for,(;j10;j+),for,(i=0;i(i-1);,原始代码：,const,a=1,2,4,8,16,32,64,128,256,512,1024,2048,4096;,c=b%ai;,d=e/ai;,二、除法（求余）的优化,由于计算机内存是线性的，多维数组的元素在排列为线性序列后存入存储器，如下所示：,0,0,0,1,0,2,0,3,1,0,1,1,1,2,1,3,2,0,2,1,2,2,2,3,3,0,3,1,3,2,3,3,三、关于多维数组的性能优化,0,0,0,1,0,2,0,3,1,0,1,1,1,2,1,3,2,0,2,1,2,2,2,3,3,0,3,1,3,2,3,3,由于在结构上需要进行转换，多维数组的引址操作被翻译成了乘法操作。,数组定义：,a1010,Debug,模式下，对数组的取值操作使用了,imul,运算（,Release,模式编译时会进行和乘法运算相同的优化）：,return,aij;,00411B6F,mov,eax,dword,ptr,i,00411B75,imul,eax,eax,28h,00411B78,lea,ecxa,eax,00411B7F,mov,edx,dword,ptr,j,00411B85,mov,eax,dword,ptr,ecx,+,edx,*,4,三、关于多维数组的性能优化,由于,imul,是一种比例时间较大的指令，如果能消去这一指令，便能够产生较大幅度的优化。,三、关于多维数组的性能优化,return,aij;,00411B6F,mov,eax,dword,ptr,i,00411B75,imul,eax,eax,28h,00411B78,lea,ecx,a,eax,00411B7F,mov,edx,dword,ptr,j,00411B85,mov,eax,dword,ptr,ecx,edx,*,4,如果操作的变址方法固定（比如像宽度优先搜索，变址操作为,+1,-1,+N,-N,），,那么用指针加减操作以及辅助记录就能获得更快的速度（消去了乘法操作）。,定义表和指针：,int,table200200;,int,*,ptr,*ptr2;,定义滑动常数：,/East,South,West,North,const,go=1,200,-1,-200;,/,假设,ptr,已赋值,ptr2=ptr+go0;,00411A4C,mov,eax,dword,ptr,go,00411A51,mov,ecx,dword,ptr,ptr,00411A57,lea,edx,ecx,+,eax,4,00411A5A,mov,dword,ptr,ptr2,edx,return,*ptr2;,00411A60,mov,eax,dword,ptr,ptr2,00411A65,mov,eax,dword,ptr,eax,这样本来隐藏的乘法操作就被消去了。,三、关于多维数组的性能优化,这种操作被我称为指针的“行走”操作。使用这个优化有个条件，就是指针变化方式固定。,让我们通过一个例子来了解这种优化的作用。,（真的很有用）,三、关于多维数组的性能优化,题意描述：,在,N*M,的矩阵中，有一些障碍，有一个物体放在某个格子上。它会按照一个时间表向某一方向运动，一个时间单位移动格。某一秒你可以让它运动，也可以让它静止。问物体最多能运动的长度。,时间表由很多个时间片段构成，在每个时间片断中，物体将向同一方向运动。,数据规模：,50%,的数据中，,1N,M200,，,时间长度,(T)200,；,100%,的数据中，,1N,M200,，,时间片段个数,(K)200,，,时间长度,(T)40000,。,例：,adv1900(NOI2005),这道题有很多做法，其中最优做法是使用单调性降维。,无论用什么方法，都必经一个关键步骤，这就是在不同的时间点间进行状态转移，并且，都要将这一步“批处理”化。,最优做法的单调性降维，以及其他各式各样的优化，如堆和,RMQ,等，都是基于对这一步骤的渐进时间复杂度的优化。,例：,adv1900(NOI2005),但是，利用“行走”操作，我们完全可以另辟蹊径。,基于此步骤具有的使用优化的典型特点：,（,1,）位于循环最里层，直接影响运行速度；,（,2,）大量使用对数组的变化方式固定的操作，可以用指针“行走”来优化。,虽然最终还是使用“批处理化”的思想，但是这种方法没有把精力用在渐进复杂度的优化上，而转向到了具体的实现上。,例：,adv1900(NOI2005),本题的移动情况可以靠在移动前进行对变量的初始化实现。,在某个时间段中对前面位置的询问可以用反方向“行走”实现。,对于取址运算中的位运算，可以用强制转换指针的方法消去。,对障碍判断的实现可以用统一变量格式实现。,例：,adv1900(NOI2005),例：,adv1900(NOI2005),下表展现了此方法与非“行走”优化方法的速度对比,(Debug,模式,),选手名称：,withoutWalk,试题：,adv1900,文件名：,adv1900,编号,评测结果,时间,内存,0,正确,0.016s,520KB,1,正确,0.016s,520KB,2,正确,0.016s,520KB,3,正确,0.063s,520KB,4,正确,0.344s,520KB,5,超时,1.016s,520KB,6,正确,0.781s,520KB,7,超时,1.031s,520KB,8,正确,0.625s,520KB9,超时,1.156s,520KB,本题总得分,70,，有效用时,5.064s,。,选手名称：,withWalk,试题：,adv1900,文件名：,adv1900,编号,评测结果,时间,内存,0,正确,0.016s,520KB,1,正确,0.016s,520KB,2,正确,0.016s,520KB,3,正确,0.047s,520KB,4,正确,0.234s,520KB,5,正确,0.703s,520KB,6,正确,0.547s,520KB,7,正确,0.734s,520KB,8,正确,0.484s,520KB,9,正确,0.797s,520KB,本题总得分,100,，有效用时,3.594s,。,表,3,：“行走”优化方法,表,4,：非“行走”优化方法,总结,汇编语言具有高速、高效的特点，并且它的细微差异，都会导致程序运行速度的一定的变化。,上述几个实例展现了反汇编在常数因子优化中的应用。,我相信，对汇编程序的分析与比较，能够使程序运行速度进一步提高，从而更快更好的解决实际问题。,欢迎,提问,T,h,a,n,k,y,o,u,