程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 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 > 和<HTML>代表的含義完全一樣。另一方面:我們還要求有一個函數,返回值是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;

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

函數名 重復次數 QueryPerformanceCounter 計數值 Pos 10000 150000 RightPos 10000 217000 RightPosEx 10000 160000

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved