作者:火鸟 redbirdli@hotmail.com
火鸟编程追求小、快、精,所以算法问题成为了我不断学习和探索的方向,现将一些心得贴出,供诸位高手批评指正,也望能有些抛砖引玉的裨益。先来看看火鸟在注册表研究中的发现(此处为过去进行时,时间约为1999-2000年之间)。
隐藏驱动器算法 a..z 用 2的n次方表示如隐藏a和c 用2的0次+2的2次=5表示 var stmp:string; itmp,irun,ival:integer; begin ival:=0; stmp:=uppercase(edit1.text); for irun:=1 to length(stmp) do begin itmp:=ord(stmp[irun])-66; itmp:=Trunc(Ldexp(2,itmp)); ival:=ival+itmp; end; edit2.text:=inttostr(ival); //以上是正向运算 stmp:=''''''''; while ival >0 do begin for irun:=0 to 25 do if Ldexp(2,irun)>ival then break; ival:=ival-Trunc(Ldexp(2,irun-1)); stmp:=chr(65+irun)+stmp; end; edit3.Text :=stmp;
点评:此法似乎无太大用途,因为其虽将各字母用同一字符表示,但有以下不足:1.字母在字串中必须唯一,即不能第二次出现同一个字母;2.返回的字符无法确定原来的排列次序。鸡肋是也!火鸟倒是想到了此法的一个用处,如您正在做一个管理系统的权限模块,可以用I、O、Q、B、M等字母表示其进货、销售、查询、数据备份和管理员维护等功能。将其经过算法处理后写入同一个字段,一来可以加密权限操作,二来可以减小字段长度。如将其转换成16进制或更高进制(火鸟建议您将16以后的数字按F代表16的概念顺序排下去)您的字段将更小也将更安全。
以下是关于运算速度的问题,先声明,火鸟本学不是计算机,所以如您觉得这些问题是课本上早讲过的。不必见笑,跳过不看便是。以下是代码:
procedure TForm1.Button1Click(Sender: TObject);//这是一个使用了指针的排序 var it:array[0..39999] of integer; itmp,irun,iset:integer; pi:^integer; begin for itmp:=0 to 39999 do it[itmp]:=39999-itmp+Random(999); caption:=timetostr(time)+''''-''''; //开始计时 for itmp:=0 to 39999 do begin pi:=@it[itmp]; for irun:=itmp+1 to 39999 do if pi^>it[irun] then pi:=@it[irun]; iset:=it[itmp]; it[itmp]:=pi^; pi^:=iset; end; caption:=caption+timetostr(time);//计时结束,在火鸟P3 533EB 128M内存中运算了7秒左右 end;
procedure TForm1.Button1Click(Sender: TObject);//这是一个未使用指针的排序 var it:array[0..39999] of integer; itmp,irun,iset:integer; pi:integer; begin for itmp:=0 to 39999 do it[itmp]:=39999-itmp+Random(999); caption:=timetostr(time)+''''-''''; //开始计时 for itmp:=0 to 39999 do begin pi:=itmp; for irun:=itmp+1 to 39999 do if it[pi]>it[irun] then pi:=irun; iset:=it[itmp]; it[itmp]:=it[pi]; it[pi]:=iset; end; caption:=caption+timetostr(time);//在同样环境中运算了10秒以上 end; 点评:以上两种算法唯一不同之处在于,第一种在循环中运行了指针,而第二种在循环中直接对值操作,可见运用指针可以提高程序效率。
procedure TForm1.Button1Click(Sender: TObject);//这是一个插入排序法 var it:array[0..39999] of integer; itmp,irun,iset:integer; pi:integer; begin for itmp:=0 to 39999 do it[itmp]:=39999-itmp+Random(999); caption:=timetostr(time)+''''-''''; //开始计时 for itmp:=1 to 39999 do begin pi:=it[itmp]; irun:=itmp-1; while (pi< it[irun]) and (irun>-1) do begin it[irun+1]:=it[irun]; irun:=irun-1; end; it[irun+1]:=pi; end; caption:=caption+timetostr(time);//在同样环境中运算了6-7秒 end;
如您已读懂了以上的插入排序法的代码,再来看看老美Shell早在1959年(玩笑话:好像那时我妈妈还在上托儿所)提出的插入排序法,此法也称为减小步长法: procedure TForm1.Button1Click(Sender: TObject); var it:array[0..39999] of integer; itmp,irun,iset:integer; pi:integer; begin for itmp:=0 to 39999 do it[itmp]:=39999-itmp+Random(999); caption:=timetostr(time)+''''-''''; //开始计时 iset:=40000; while iset>1 do begin iset:=iset div 2; itmp:=iset; repeat pi:=it[itmp]; irun:=itmp-iset; while (irun>-1) and (pi< it[irun]) do begin it[irun+iset]:=it[irun]; irun:=irun-iset; end; it[irun+iset]:=pi; itmp:=itmp+1; until itmp>40000 end; caption:=caption+timetostr(time);//在同样环境中运算不到1秒!即使将数组扩大到199999,仍然能在一秒中内完成!