优化Pos函数 |
尚未結案
|
circusmonkey
一般會員 發表:6 回覆:10 積分:8 註冊:2004-06-28 發送簡訊給我 |
小弟看了D5的pos函数,它是用汇编语言写的。效率非常的高。
但是pos函数比较简单,不可以搜索第二个匹配的substr,也不可以从尾部反向搜索。 一般来说,如果要搜索第二个匹配的substr。思路是:在找到第一个匹配位置(P1)后,复制剩余的字符串,并进行Pos操作(Copy(S, P1+1, Maxint);然后把第二次找到的位置和P1做相应处理,并返回函数值。如果是搜索第n个匹配的substr,只需要用递归的办法,即可实现。 用这个办法来搜索第n个substr,所需要花费的时间差不多是n倍Pos需要的时间,并加上n-1次Copy剩余字符串的时间。不过我仔细想想,觉得这样做有一个问题:如果我们要在一个10mb的xml文本中搜索某个substr,那么需要花费的时间可能就需要好几分钟了吧。原因是反复用Copy函数复制一个极大的字符串。 小弟不懂汇编。但是觉得如果模仿DELPHI的Pos函数(在systems.pas中为procedure _Pos),写一个可以指定StartIndex的Pos2函数,可能会更好些。 小弟在网上搜索过不少资料,比较著名的字符串函数库是FastString。它虽然可以指定StartIndex,但是奇怪的是它的效率比用Pos低一些,而且似乎对Unicode有不兼容的现象。 所以小弟希望各位好心的朋友能出出主意,把Pos的执行速度提高到极致。
最好可以写出
- Pos2(const Substr, S: WideString; LeftStartIndex: Integer = 1)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>LeftStartIndex 指开始比较的位置
- PosBack(const Substr, S: WideString; RightEndIndex: Integer = -1)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RightEndIndex 指开始比较的位置 發表人 - circusmonkey 於 2004/07/05 21:49:53
|
circusmonkey
一般會員 發表:6 回覆:10 積分:8 註冊:2004-06-28 發送簡訊給我 |
补充一下,DELPHI5的Pos函数如下: procedure _Pos{ substr : ShortString; s : ShortString ) : Integer};
asm
{ ->EAX Pointer to substr }
{ EDX Pointer to string }
{ <-EAX Position of substr in s or 0 } PUSH EBX
PUSH ESI
PUSH EDI MOV ESI,EAX { Point ESI to substr }
MOV EDI,EDX { Point EDI to s } XOR ECX,ECX { ECX = Length(s) }
MOV CL,[EDI]
INC EDI { Point EDI to first char of s } PUSH EDI { remember s position to calculate index } XOR EDX,EDX { EDX = Length(substr) }
MOV DL,[ESI]
INC ESI { Point ESI to first char of substr } DEC EDX { EDX = Length(substr) - 1 }
JS @@fail { < 0 ? return 0 }
MOV AL,[ESI] { AL = first char of substr }
INC ESI { Point ESI to 2'nd char of substr } SUB ECX,EDX { #positions in s to look at }
{ = Length(s) - Length(substr) 1 }
JLE @@fail
@@loop:
REPNE SCASB
JNE @@fail
MOV EBX,ECX { save outer loop counter }
PUSH ESI { save outer loop substr pointer }
PUSH EDI { save outer loop s pointer } MOV ECX,EDX
REPE CMPSB
POP EDI { restore outer loop s pointer }
POP ESI { restore outer loop substr pointer }
JE @@found
MOV ECX,EBX { restore outer loop counter }
JMP @@loop @@fail:
POP EDX { get rid of saved s pointer }
XOR EAX,EAX
JMP @@exit @@found:
POP EDX { restore pointer to first char of s }
MOV EAX,EDI { EDI points of char after match }
SUB EAX,EDX { the difference is the correct index }
@@exit:
POP EDI
POP ESI
POP EBX
end;
|
circusmonkey
一般會員 發表:6 回覆:10 積分:8 註冊:2004-06-28 發送簡訊給我 |
|
circusmonkey
一般會員 發表:6 回覆:10 積分:8 註冊:2004-06-28 發送簡訊給我 |
|
timhuang
尊榮會員 發表:78 回覆:1815 積分:1608 註冊:2002-07-15 發送簡訊給我 |
Hi, 在 delphi 7 中的 PosEx 或許可以解決你的問題! 原型如下,
function PosEx(const SubStr, S: string; Offset: Cardinal = 1): Integer; var I,X: Integer; Len, LenSubStr: Integer; begin if Offset = 1 then Result := Pos(SubStr, S) else begin I := Offset; LenSubStr := Length(SubStr); Len := Length(S) - LenSubStr 1; while I <= Len do begin if S[I] = SubStr[1] then begin X := 1; while (X < LenSubStr) and (S[I X] = SubStr[X 1]) do Inc(X); if (X = LenSubStr) then begin Result := I; exit; end; end; Inc(I); end; Result := 0; end; end; |
circusmonkey
一般會員 發表:6 回覆:10 積分:8 註冊:2004-06-28 發送簡訊給我 |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |