程式師世界 >> 編程語言 >> 更多編程語言 >> Delphi >> 一步步教你如何優化Delphi字串查找

一步步教你如何優化Delphi字串查找

編輯：Delphi

本人在編寫離線浏覽器WebSeizer的過程中，用到大量字符串處理函數，這是很耗CPU的一個處理過程，為了編寫出高效率的網頁解析引擎，對優化代碼作了一番研究。

1 、高精度的計時函數

代碼優化時需要用到精確的計時器。常用的有GetTickCount函數，可以達到毫秒級的精度。但還是很不夠的，這時可以采用提高循環次數的辦法。另外，還有一個精度更高的定時——“高分辨率性能計數器”（high-resolution performance counter），它提供了兩個API函數，取得計數器頻率的QueryPerformanceFrequency和取得計數器數值的QueryPerformanceCounter。實現原理是利用計算機中的8253,8254可編程時間間隔定時器芯片實現的。在計算機內部有三個獨立的16位計數器。

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

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

2 、代碼優化實例

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

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

function Pos(Substr: string; S: string): Integer;

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

在本人編寫WebSeizer軟件（天空軟件站有下載）過程中，Pos已經不能滿足要求。一方面：在處理網頁中的字符串時，要求對大小寫不敏感，即< h t m l > 和代表的含義完全一樣。另一方面：我們還要求有一個函數，返回值是Substr在S中最後一次出現的位置，而不是第一次出現的位置。下面是這個函數的未經優化的代碼。

function RightPos(const Substr,S: string): Integer;
            var
            　iPos: Integer;
            　TmpStr:string;
            begin
            　TmpStr:=s;
            　iPos := Pos(Substr,TmpStr); Result:=0;
            　//查找Substr第一次出現位置
            　while iPos<>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
            { EAX Pointer to s }
            { EDX index }
            { ECX count }
            PUSH EBX
            PUSH ESI
            PUSH EDI
            MOV EBX,EAX
            MOV ESI,EDX
            MOV EDI,ECX
            CALL UniqueString
            MOV EDX,[EBX]
            TEST EDX,EDX { source already empty:
            nothing to do }
            JE @@exit
            MOV ECX,[EDX-skew].StrRec.length
            { make index 0-based, if not in [0 .. Length(s)-1]
            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
            MOV EDI,ECX
            @@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 }
            LEA EAX,[EDX+EDI] { EAX = s+index+count }
            CALL Move
            { set length(s) to length(s) - count }
            MOV EDX,[EBX]
            MOV EAX,EBX
            MOV EDX,[EDX-skew].StrRec.length
            SUB EDX,EDI
            CALL _LStrSetLength
            @@exit:
            POP EDI
            POP ESI
            POP EBX
            end;

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,len: Integer;
            　PCharS,PCharSub:PChar;
            begin
            　PCharS:=PChar(s); //將字符串轉化為PChar格式
            　PCharSub:=PChar(Substr);
            　Result:=0;
            　len:=length(Substr);
            　for i:=0 to length(S)-1 do
            　begin
            　　for j:=0 to len-1 do
            　　begin
            　　　if PCharS[i+j]<>PCharSub[j] then break;
            　　end;
            　　if j=len then Result:=i+1;
            end;

請看第一句PCharS:=PChar(s)，它的作用是將Delphi字符串強制轉化為PChar 格式(PChar 是Windows中使用的標准字符串，不包含長度信息，使用0為結束標志)，並得到指向PChar字符串的指針PcharS。

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

var
            i,len,iPos: Integer;
            PerformanceCount1,PerformanceCount2,Count:int64;
            begin
            len:=10000; //重復次數
            QueryPerformanceCounter(PerformanceCount1);//開始計數
            for i:=0 to len-1 do
            begin
            　iPos:=RightPos(’12’,Edit1.Text); //被測試的函數
            end;
            QueryPerformanceCounter(PerformanceCount2); //結束計數
            Count:=(PerformanceCount2-PerformanceCount1);
            Label1.Caption:=inttostr(iPos)+’ time=’+inttostr(Count);
            End;