火鳥編程追求小、快、精,所以算法問題成為了我不斷學習和探索的方向,現將一些心得貼出,供諸位高手批評指正,也望能有些拋磚引玉的裨益。先來看看火鳥在注冊表研究中的發現(此處為過去進行時,時間約為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,仍然能在一秒中內完成!
end;
點評:火鳥以前只會用所謂“冒泡法”排序,見了Shell 真不愧為醍醐灌頂,大夢方醒。真是精巧的算法!套一句廣告詞“不只是快一點”你也來試試吧!