背景
稍后添加
我制作了一个纯Pascal函数来查找Unicode字符串中字符的位置,如下所示:
function CharPosEx(const chChr: Char; const sStr: string;
const iOffset: Integer=1): Integer;
var
PStr : PChar;
PRunIdx: PChar;
PEndIdx: PChar;
iLenStr: Integer;
begin
Result := 0;
iLenStr := Length(sStr);
if (iLenStr = 0) or (iOffset <= 0) or (iOffset > iLenStr) then Exit;
PStr := Pointer(sStr);
PEndIdx := @PStr[iLenStr - 1];
PRunIdx := @PStr[iOffset - 1];
repeat
if PRunIdx^ = chChr then begin
Result := PRunIdx - PStr + 1;
Exit;
end;
Inc(PRunIdx);
until PRunIdx > PEndIdx;
end;
我决定不使用内置的StrUtils.PosEx()
,因为我想在CharPosEx
的优化纯Pascal函数的基础上创建一个UTF16_CharPosEx
函数。我正试图找到一个更快的通用解决方案,就像Fastcode项目的纯Pascal方法一样。
原始报表
根据这个问题的公认答案,Delphi:fast Pos with 64 bit,最快找到字符串中子字符串位置的纯Pascal函数是Fastcode Project的PosEx_Sha_Pas_2()
。
对于查找字符串中字符位置的最快纯Pascal函数,我注意到Fastcode Project有CharPos()
、CharPosIEx()
和CharPosEY()
用于从左到右匹配,还有CharPosRev()
用于从右到左匹配。
然而,问题是所有的Fastcode函数都是在Delphi 2009之前开发的,Delphi 2009是第一个支持Unicode的Delphi版本。
我对CharPos()
和CharPosEY()
感兴趣。我想重新对它们进行基准测试,因为现在有一些优化技术是无用的,比如Fastcode函数中偶尔实现的循环展开技术。
然而,我无法为CharPos
系列的每一个挑战重新编译基准项目,因为我一直在这里使用DelphiXE3,因此我无法得出哪一个是最快的。
问题
这里的任何人都知道或可以确定哪一个是最快的纯Pascal实现来解决上述Fastcode挑战,尤其是CharPos()
和CharPosEY()
?
欢迎使用Fastcode项目解决方案中的其他方法。
备注
- 我在这里使用的Unicode字符串术语指的是类型为
UnicodeString
的字符串,而不管其编码方案如何 - 如果编码方案很重要,我的意思是固定宽度的16位编码方案(UCS-2(
在快速代码示例中,许多在字符串中查找字符的解决方案都使用一种技术将字符串以较大的块读取到寄存器中,然后分析寄存器字节是否匹配。当字符是单字节时,这一点很好,但当字符是16位unicode时,这不是最佳的。
有些示例甚至使用查找表,但这在unicode字符串搜索中也不是最佳的。
我发现fastcode purepascal PosEx_Sha_Pas_2
字符串搜索例程在32/64位模式下都能很好地工作,即使是单字符搜索。你还不如用那种套路。
我把PosEx_Sha_Pas_2
中一些不需要的部分剥离到CharPosEx_LU_Pas中,并在执行时间上获得了一些百分比:
function CharPosEx_LU_Pas(c: Char; const S: string; Offset: Integer = 1): Integer;
var
len: Integer;
p, pStart, pStop: PChar;
label
Loop0, Loop4,
TestT, Test0, Test1, Test2, Test3, Test4,
AfterTestT, AfterTest0,
Ret;
begin;
p := Pointer(S);
if (p = nil) or (Offset < 1) then
begin;
Exit(0);
end;
len := PLongInt(PByte(p) - 4)^; // <- Modified to fit 32/64 bit
if (len < Offset) then
begin;
Exit(0);
end;
pStop := p + len;
pStart := p;
p := p + Offset + 3;
if p < pStop then
goto Loop4;
p := p - 4;
goto Loop0;
Loop4:
if c = p[-4] then
goto Test4;
if c = p[-3] then
goto Test3;
if c = p[-2] then
goto Test2;
if c = p[-1] then
goto Test1;
Loop0:
if c = p[0] then
goto Test0;
AfterTest0:
if c = p[1] then
goto TestT;
AfterTestT:
p := p + 6;
if p < pStop then
goto Loop4;
p := p - 4;
if p < pStop then
goto Loop0;
Exit(0);
Test3:
p := p - 2;
Test1:
p := p - 2;
TestT:
p := p + 2;
if p <= pStop then
goto Ret;
Exit(0);
Test4:
p := p - 2;
Test2:
p := p - 2;
Test0:
Inc(p);
Ret:
Result := p - pStart;
end;
我声称这个片段没有独创性,因为从PosEx_Sha_Pas_2中去掉那些不需要的代码部分是一项简单的任务。
基准32位(101个字符串,最后一个字符匹配(:50000000次重复。
System.Pos: 1547 ms
PosEX_Sha_Pas_2: 1292 ms
CharPosEx: 2315 ms
CharPosEx_LU_Pas: 1103 ms
SysUtils.StrScan: 2666 ms
基准64位(101个字符串,最后一个字符匹配(:50000000次重复。
System.Pos: 20928 ms
PosEX_Sha_Pas_2: 1783 ms
CharPosEx: 2874 ms
CharPosEx_LU_Pas: 1728 ms
SysUtils.StrScan: 3115 ms