一步步教你優化Delphi字串查找(轉載)

　　1 、高精度的計時函數

　　計數器可以以二進制或二—十進制(BDC)計數。計數器每秒産生1193180次脈沖，每次脈沖使計數器的數字減一，産生頻率是可變的,用QueryPerformanceFrequency可以得到,一般情況下都是1193180。QueryPerformance Counter可以得到目前的計數器值。是以隻要你的計算機

夠快，理論上精度可以達到1/1193180秒。

　　2 、代碼優化執行個體

　　下面以一個自定義的字元串函數的為例，說明代碼優化過程。

　　Delphi提供的字元串函數裡有一個Pos函數，它的定義是：

　　它的作用是在字元串S中查找字元串Substr，傳回值是Substr在S中第一次出現的位置，如果沒有找到，傳回值為0。

<a href="http://www.yesky.com/key/303/100303.html">var</a>

　iPos: Integer;

　TmpStr:string;

begin

　TmpStr:=s;

　iPos := Pos(Substr,TmpStr); Result:=0;

　//查找Substr第一次出現位置

　while iPos&lt;&gt;0 do

　begin

　　Delete(TmpStr,1,iPos+length(Substr)-1);

　　//删除已經查找過的字元

　　Result:=Result+iPos;

　　iPos := Pos(Substr,TmpStr); //查找Substr出現位置

　　if iPos=0 then break;

　　Result:=Result+length(Substr)-1;

　end;

end;

　　這個函數裡，用到了Delete函數，我們再來看一看System.pas檔案裡Delete函數的實作過程，請看下面代碼：

procedure _LStrDelete{ var s : AnsiString; index, count : Integer };

asm

{ EDX index }

{ ECX count }

PUSH EBX

PUSH ESI

PUSH EDI

MOV ESI,EDX

MOV EDI,ECX

CALL UniqueString

MOV EDX,[EBX]

nothing to do }

JE @@exit

MOV ECX,[EDX-skew].StrRec.length

do nothing }

DEC ESI

JL @@exit

CMP ESI,ECX

JGE @@exit

{ limit count to [0 .. Length(s) - index] }

TEST EDI,EDI

JLE @@exit

SUB ECX,ESI { ECX = Length(s) - index

}

CMP EDI,ECX

JLE @@1

@@1:

{ move length - index - count characters from

s+index+count to s+index }

SUB ECX,EDI { ECX = Length(s) - index

- count }

ADD EDX,ESI { EDX = s+index }

CALL Move

{ set length(s) to length(s) - count }

MOV EAX,EBX

MOV EDX,[EDX-skew].StrRec.length

SUB EDX,EDI

CALL _LStrSetLength

@@exit:

POP EDI

POP ESI

POP EBX

　　Delete 函數中，有這兩句：CALL Move和CALL_LstrSetLength。其中Move函數是将一個記憶體塊拷貝到另一個位址，LstrSetLength函數将改變字元串的長度，其中也有對記憶體進行配置設定的代碼。這些對記憶體進行操作的函數都是極其消耗CPU運作時間的，是以Delete函數也是一個極其消耗CPU運作時間的函數。為了盡量避免使用這些函數，我對自定義函數RightPos進行了改寫。

　　修改後不再使用Delete及Pos函數，直接通過指針對記憶體操作，提高了效率。

function RightPosEx(const Substr,S: string): Integer;

var

  iPos: Integer;

  TmpStr: string;

  i, j, lvlen: Integer;

  PCharS, PCharSub: PChar;

  PCharS := PChar(s); //将字元串轉化為PChar格式

  PCharSub := PChar(Substr);

  Result := 0;

  lvlen := length(Substr);

  for i := 0 to length(S) - 1 do

  begin

    for j := 0 to lvlen - 1 do

    begin

      if PCharS[i + j] &lt;&gt; PCharSub[j] then break;

    end;

    if j = lvlen then Result := i + 1;

  end;

　　請看第一句PCharS:=PChar(s)，它的作用是将Delphi字元串強制轉化為PChar 格式(PChar 是Windows中使用的标準字元串，不包含長度資訊，使用0為結束标志)，并得到指向PChar字元串的指針PcharS。

　　下面就要對自定義函數的運作時間進行測量，為了提高測量的精度，減小随機性，我們計算重複10000次所需的時間。代碼如下：

i,len,iPos: Integer;

PerformanceCount1,PerformanceCount2,Count:int64;

len:=10000; //重複次數

QueryPerformanceCounter(PerformanceCount1);//開始計數

for i:=0 to len-1 do

　iPos:=RightPos(’12’,Edit1.Text); //被測試的函數

QueryPerformanceCounter(PerformanceCount2); //結束計數

Count:=(PerformanceCount2-PerformanceCount1);

Label1.Caption:=inttostr(iPos)+’ time=’+inttostr(Count);

End;

　　我的配置是Duron700，256M記憶體，測試中RightPos函數重複了10000遍，RightPos使用的參數為：Substr=12，S=Edit12ewew12tet。得到的測量結果是Count=217000，又對其他幾個函數作了對比，結果如下：

函數名

重複次數

QueryPerformanceCounter 計數值

Pos

10000

150000

RightPos

217000

RightPosEx

160000

　　可以看出測試的結果是比較滿意的，改進過的RightPosEx函數效率比RightPos高很多，考慮到測試用的字元串比較短，使用長字元串效果更明顯。如果直接使用Delphi的字元串格式而不用轉為PChar格式，則效率又可提高一步。但字元串格式是Delphi語言自定義的,存在相容性問題。是以這一版本的字串搜尋函數就不列出來了，讀者在前面代碼的基礎上很容易就可寫出來的。代碼優化到底要執行到哪一步，是仁者見仁，智者見智的問題。有的人偏重于提高效率，有的人偏重于保證相容性，這需要在實際使用過程中作取舍。

----

實際測試，

{*

//長字元串（大概1M左右)

1000次

BDS 2007 見Demos

(Delete) time: 323301

(CopyStr) time: 953036

(LastPosEx)Pos: 144881

 time: 3665003

(Pos)Pos: 58745

 time: 314023

(FastPosEx)Pos: 58745

 time: 11383136

(fstAt)Pos: 58745

 time: 354948

(SmartPos)Pos: 58745

 time: 206409

*}

const

  COUNT_NUM = 10000;

procedure TForm1.btnDeleteAndCopyStrClick(Sender: TObject);

  i, lvlen, iPos: Integer;

  PerformanceCount1, PerformanceCount2, Count: int64;

  lvSubString, lvSourceString: string;

  lvlen := COUNT_NUM; //重複次數

  lvSourceString := edtSourceString.Text;

  if chkUseMemoSource.Checked then

    lvSourceString := mmoSourceString.Text;

    lvlen := lvlen div 10;

  QueryPerformanceCounter(PerformanceCount1); //開始計數

  lvSubString := lvSourceString;

  for i := 0 to lvlen - 1 do

    Delete(lvSubString, 1, 1);

  QueryPerformanceCounter(PerformanceCount2); //結束計數

  Count := (PerformanceCount2 - PerformanceCount1);

  mmoMessage.Lines.Add('(Delete) time: ' + inttostr(Count));

    lvSubString := CopyStr(lvSubString, 2, Length(lvSubString));

  mmoMessage.Lines.Add('(CopyStr) time: ' + inttostr(Count));

procedure TForm1.btnPosTestClick(Sender: TObject);

    lvSubString := edtPosTest.Text;

    iPos := LastPosEx(lvSubString, lvSourceString); //被測試的函數

  mmoMessage.Lines.Add('(LastPosEx)Pos: ' + inttostr(iPos) + sLineBreak + ' time: ' + inttostr(Count));

    iPos := Pos(lvSubString, lvSourceString); //被測試的函數

  mmoMessage.Lines.Add('(Pos)Pos: ' + inttostr(iPos) + sLineBreak + ' time: ' + inttostr(Count));

    iPos := FastPosEx(PChar(lvSourceString), Length(lvSourceString), PChar(lvSubString), Length(lvSubString)); //被測試的函數

  mmoMessage.Lines.Add('(FastPosEx)Pos: ' + inttostr(iPos) + sLineBreak + ' time: ' + inttostr(Count));

    iPos := fstAt(lvSubString, lvSourceString); //被測試的函數

  mmoMessage.Lines.Add('(fstAt)Pos: ' + inttostr(iPos) + sLineBreak + ' time: ' + inttostr(Count));

    iPos := SmartPos(lvSubString, lvSourceString); //被測試的函數

  mmoMessage.Lines.Add('(SmartPos)Pos: ' + inttostr(iPos) + sLineBreak + ' time: ' + inttostr(Count));