那些遇到过的问题

Delphi有快速的GetToken例程吗？

lke*_*ler 21 delphi optimization parsing token aqtime

在我的程序中,我处理了数百万个具有特殊字符的字符串,例如"|" 分隔每个字符串中的标记.我有一个返回第n个令牌的函数,就是这样:

function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
var
 I, P, P2: integer;
begin
  P2 := Pos(Delim, Line);
  if TokenNum = 1 then begin
    if P2 = 0 then
      Result := Line
    else
      Result := copy(Line, 1, P2-1);
  end
  else begin
    P := 0; { To prevent warnings }
    for I := 2 to TokenNum do begin
      P := P2;
      if P = 0 then break;
      P2 := PosEx(Delim, Line, P+1);
    end;
    if P = 0 then
      Result := ''
    else if P2 = 0 then
      Result := copy(Line, P+1, MaxInt)
    else
      Result := copy(Line, P+1, P2-P-1);
  end;
end; { GetTok }
Run Code Online (Sandbox Code Playgroud)

当我使用Delphi 4时,我开发了这个函数.它调用了最初由Fastcode开发的非常有效的PosEx例程,现在包含在Delphi的StrUtils库中.

我最近升级到Delphi 2009,我的字符串都是Unicode.这个GetTok功能仍然可以正常工作.

我已经浏览了Delphi 2009中的新库,并且有许多新功能和新增功能.

但是我没有在任何新的Delphi库中,在各种快速代码项目中看到过像我需要的GetToken函数,除了Zarko Gajic之外我找不到谷歌搜索的任何东西:Delphi Split/Tokenizer Functions,它不是像我已经拥有的那样优化.

任何改进,甚至10%都会在我的计划中引人注目.我知道另一种选择是StringLists并始终保持令牌独立,但这有很大的内存开销,我不确定我是否做了所有工作来转换它是否会更快.

呼.所以这个冗长的谈话之后,我的问题确实是:

你知道GetToken例程的任何非常快速的实现吗？汇编程序优化版本是理想的吗？

如果没有,您是否可以在上面的代码中看到任何可能有所改进的优化？

跟进:Barry Kelly提到了一年前我问过的关于优化文件中行的解析的问题.那时我甚至没想过我的GetTok例程没有用于读取或解析.直到现在我才看到我的GetTok例程的开销导致我提出这个问题.直到Carl Smotricz和Barry的回答,我才想到要把两者联系起来.很明显,但它没有注册.感谢您指出了这一点.

是的,我的Delim是一个单一角色,所以显然我有一些我可以做的重大优化.我在GetTok例程(上面)中使用Pos和PosEx使我觉得我可以通过逐字符搜索更快地完成它,并使用以下代码:

      while (cp^ > #0) and (cp^ <= Delim) do    
        Inc(cp);
Run Code Online (Sandbox Code Playgroud)

我将通过每个人的答案,尝试各种建议并进行比较.然后我会发布结果.

困惑:好的,现在我真的很困惑.

我把Carl和Barry的建议与PChars一起使用,这是我的实现:

function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
 I: integer;
 PLine, PStart: PChar;
begin
  PLine := PChar(Line);
  PStart := PLine;
  inc(PLine);
  for I := 1 to TokenNum do begin
    while (PLine^ <> #0) and (PLine^ <> Delim) do
      inc(PLine);
    if I = TokenNum then begin
      SetString(Result, PStart, PLine - PStart);
      break;
    end;
    if PLine^ = #0 then begin
      Result := '';
      break;
    end;
    inc(PLine);
    PStart := PLine;
  end;
end; { GetTok }
Run Code Online (Sandbox Code Playgroud)

在纸面上,我认为你不能比这更好.

因此,我将两个例程都放到了任务中,并使用AQTime来查看正在发生的事情.我已经包含了1,108,514次GetTok调用.

AQTime将原始程序定时为0.40秒.百万次拨打Pos的时间为0.10秒.TokenNum的50万份= 1份拷贝需要0.10秒.600,000个PosEx电话只用了0.03秒.

然后我用AQTime为我的新例程计时相同的运行和完全相同的调用.AQTime报告我的新"快速"例程需要3.65秒,这是9倍的时间.根据AQTime的罪魁祸首是第一个循环:

     while (PLine^ <> #0) and (PLine^ <> Delim) do
       inc(PLine);
Run Code Online (Sandbox Code Playgroud)

执行了1800万次的while行报告为2.66秒.执行1600万次的公司线据说需要0.47秒.

现在我以为我知道这里发生了什么.我在去年提出的一个问题中遇到了与AQTime类似的问题:为什么CharInSet比Case语句更快？

再一次是Barry Kelly让我陷入困境.基本上,像AQTime这样的仪表分析器并不一定能完成微优化工作.它增加了每行的开销,这可能会淹没结果,这些数字清楚地显示出来.在我的新"优化代码"中执行的3400万行压倒了我原始代码的数百万行,显然很少或没有来自Pos和PosEx例程的开销.

Barry使用QueryPerformanceCounter给我一个代码示例来检查他是否正确,在那种情况下他是.

好的,现在让我们用QueryPerformanceCounter做同样的事情来证明我的新例程更快,而不是像AQTime所说的那样慢9倍.所以我走了:

function TimeIt(const Title: string): double;
var  i: Integer;
  start, finish, freq: Int64;
  Seconds: double;
begin
  QueryPerformanceCounter(start);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 1);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 2);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 3);
  for i := 1 to 250000 do
    GetTokOld('This is a string|that needs|parsing', '|', 4);
  QueryPerformanceCounter(finish);
  QueryPerformanceFrequency(freq);
  Seconds := (finish - start) / freq;
  Result := Seconds;
end;
Run Code Online (Sandbox Code Playgroud)

因此,这将测试对GetTok的1,000,000次调用.

Pos和PosEx呼叫的旧程序耗时0.29秒.PChars的新版本耗时2.07秒.

现在我完全糊涂了!谁能告诉我为什么PChar程序不仅速度慢,而且速度慢8到9倍!？

谜团已揭开!Andreas在回答中将Delim参数从字符串更改为Char.我将永远只使用Char,所以至少对于我的实现,这是非常可能的.我对发生的事感到惊讶.

100万个电话的时间从1.88秒下降到0.22秒.

令人惊讶的是,当我将Delim参数更改为Char时,我原来的Pos​​/PosEx例程的时间从.29上升到.44秒.

坦率地说,我对Delphi的优化器感到很失望.Delim是一个不变的参数.优化器应该已经注意到循环内发生了相同的转换,并且应该将其移出,以便只进行一次.

仔细检查我的代码生成参数,是的,我确实有优化True和字符串格式检查关闭.

最重要的是,使用Andrea修复的新PChar例程比我原来的快25%(.22对.29).

我仍然想在这里跟进其他评论并测试它们.

关闭优化并启用字符串格式检查只会将时间从.22增加到.30.它增加了与原版相同的内容.

使用汇编程序代码或调用用汇编程序(如Pos或PosEx)编写的例程的优点是它们不受您设置的代码生成选项的限制.它们将始终以相同的方式运行,这是一种预先优化且不臃肿的方式.

在过去的几天里,我再次确认,比较微优化代码的最佳方法是查看并比较CPU窗口中的汇编代码.如果Embarcadero可以使该窗口更方便,并允许我们将部分复制到剪贴板或打印部分,这将是很好的.

另外,我在这篇文章的早些时候不公平地抨击了AQTime,认为为我的新例程添加的额外时间完全是因为它添加了仪器.现在我回过头来检查Char参数而不是String,while循环下降到.30秒(从2.66开始),inc线下降到.14秒(从.47开始).奇怪的是,公司线路也会下降.但是我已经厌倦了所有这些测试.

我采用了卡尔关于字符循环的想法,并用这个想法重写了代码.它进行了另一项改进,从.22降至0.19秒.所以到目前为止这里是最好的:

function GetTok(const Line: string; const Delim: Char; const TokenNum: Byte): string;
{ LK Nov 8, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
  I, CurToken: Integer;
  PLine, PStart: PChar;
begin
  CurToken := 1;
  PLine := PChar(Line);
  PStart := PLine;
  for I := 1 to length(Line) do begin
    if PLine^ = Delim then begin
      if CurToken = TokenNum then
        break
      else begin
        CurToken := CurToken + 1;
        inc(PLine);
        PStart := PLine;
      end;
    end
    else
      inc(PLine);
  end;
  if CurToken = TokenNum then
    SetString(Result, PStart, PLine - PStart)
  else
    Result := '';
end;
Run Code Online (Sandbox Code Playgroud)

仍然可能会对此进行一些小的优化,例如CurToken = Tokennum比较,它应该是相同类型,Integer或Byte,以较快者为准.

但是,让我们说,我现在很高兴.

再次感谢StackOverflow Delphi社区.

Bar*_*lly 12

它对"Delim"的预期产生了很大的影响.如果预期它是一个单个字符,那么你最好逐个字符地逐个字符串,最好通过PChar,并进行特定的测试.

如果它是一个长字符串,Boyer-Moore和类似搜索有一个跳过表的设置阶段,最好的方法是构建表一次,并为每个后续查找重用它们.这意味着你需要调用之间的状态,而这个函数最好作为一个对象的方法.

您可能对我之前给出的一个问题的答案感兴趣,关于在Delphi中解析一行的最快方法.(但我发现是你问了这个问题!尽管如此,在解决你的问题时,我会告诉我如何描述解析,而不是像你使用的那样使用PosEx,这取决于Delim通常的样子.)

更新:好的,我花了大约40分钟来看这个.如果您知道分隔符将成为一个角色,那么第二个版本(即PChar扫描)几乎总是更好,但您必须Delim作为角色传递.在撰写本文时,您将PLine^表达式(Char类型)转换为字符串以与Delim进行比较.那将是非常缓慢的; 甚至索引到字符串中,Delim[1]也会有些慢.

但是,根据您的线条的大小以及要拉出多少分隔的部分,您可能最好采用可恢复的方法,而不是在标记化例程中跳过不需要的分隔部分.如果你通过连续增加索引调用GetTok,就像你目前在迷你基准测试中所做的那样,你最终会得到O(n*n)性能,其中n是分隔部分的数量.如果保存扫描状态并将其恢复到下一次迭代,或者将所有提取的项打包到数组中,则可以将其转换为O(n).

这是一个完成所有标记化的版本,并返回一个数组.它需要两次标记,以便知道制作数组有多大.另一方面,只有第二个标记化需要提取字符串:

// Do all tokenization up front.
function GetTok4(const Line: string; const Delim: Char): TArray<string>;
var
  cp, start: PChar;
  count: Integer;
begin
  // Count sections
  count := 1;
  cp := PChar(Line);
  start := cp;
  while True do
  begin
    if cp^ <> #0 then
    begin
      if cp^ <> Delim then
        Inc(cp)
      else
      begin
        Inc(cp);
        Inc(count);
      end;
    end
    else
    begin
      Inc(count);
      Break;
    end;
  end;

  SetLength(Result, count);
  cp := start;
  count := 0;

  while True do
  begin
    if cp^ <> #0 then
    begin
      if cp^ <> Delim then
        Inc(cp)
      else
      begin
        SetString(Result[count], start, cp - start);
        Inc(cp);
        Inc(count);
      end;
    end
    else
    begin
      SetString(Result[count], start, cp - start);
      Break;
    end;
  end;
end;
Run Code Online (Sandbox Code Playgroud)

这是可恢复的方法.但是,当前位置和分隔符的加载和存储确实有成本:

type
  TTokenizer = record
  private
    FSource: string;
    FCurrPos: PChar;
    FDelim: Char;
  public
    procedure Reset(const ASource: string; ADelim: Char); inline;
    function GetToken(out AResult: string): Boolean; inline;
  end;

procedure TTokenizer.Reset(const ASource: string; ADelim: Char);
begin
  FSource := ASource; // keep reference alive
  FCurrPos := PChar(FSource);
  FDelim := ADelim;
end;

function TTokenizer.GetToken(out AResult: string): Boolean;
var
  cp, start: PChar;
  delim: Char;
begin
  // copy members to locals for better optimization
  cp := FCurrPos;
  delim := FDelim;

  if cp^ = #0 then
  begin
    AResult := '';
    Exit(False);
  end;

  start := cp;
  while (cp^ <> #0) and (cp^ <> Delim) do
    Inc(cp);

  SetString(AResult, start, cp - start);
  if cp^ = Delim then
    Inc(cp);
  FCurrPos := cp;
  Result := True;
end;
Run Code Online (Sandbox Code Playgroud)

这是我用于基准测试的完整程序.

结果如下:

*** count=3, Length(src)=200
GetTok1: 595 ms
GetTok2: 547 ms
GetTok3: 2366 ms
GetTok4: 407 ms
GetTokBK: 226 ms
*** count=6, Length(src)=350
GetTok1: 1587 ms
GetTok2: 1502 ms
GetTok3: 6890 ms
GetTok4: 679 ms
GetTokBK: 334 ms
*** count=9, Length(src)=500
GetTok1: 3055 ms
GetTok2: 2912 ms
GetTok3: 13766 ms
GetTok4: 947 ms
GetTokBK: 446 ms
*** count=12, Length(src)=650
GetTok1: 4997 ms
GetTok2: 4803 ms
GetTok3: 23021 ms
GetTok4: 1213 ms
GetTokBK: 543 ms
*** count=15, Length(src)=800
GetTok1: 7417 ms
GetTok2: 7173 ms
GetTok3: 34644 ms
GetTok4: 1480 ms
GetTokBK: 653 ms
Run Code Online (Sandbox Code Playgroud)

根据数据的特征,分隔符是否可能是一个字符,以及如何使用它,不同的方法可能会更快.

(我在之前的程序中犯了一个错误,我没有为每种常规测量相同的操作.我更新了pastebin链接和基准测试结果.)

And*_*den 11

你的新函数(带有PChar的函数)应该将"Delim"声明为Char而不是String.在您当前的实现中,编译器必须将PLine ^ char转换为字符串,以将其与"Delim"进行比较.这种情况发生在一个紧密的循环中,导致了巨大的性能损失.

function GetTok(const Line: string; const Delim: Char{<<==}; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; http://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
 I: integer;
 PLine, PStart: PChar;
begin
  PLine := PChar(Line);
  PStart := PLine;
  inc(PLine);
  for I := 1 to TokenNum do begin
    while (PLine^ <> #0) and (PLine^ <> Delim) do
      inc(PLine);
    if I = TokenNum then begin
      SetString(Result, PStart, PLine - PStart);
      break;
    end;
    if PLine^ = #0 then begin
      Result := '';
      break;
    end;
    inc(PLine);
    PStart := PLine;
  end;
end; { GetTok }
Run Code Online (Sandbox Code Playgroud)

Car*_*icz 9

Delphi编译为非常高效的代码; 根据我的经验,在汇编程序中做得更好是非常困难的.

我想你应该在字符串的开头指出一个PChar(它们仍然存在,不是它们吗？我在Delphi附近分开4.0)并在计算"|"s时递增它,直到找到n-1他们 我怀疑这会比反复拨打PosEx更快.

记下该位置,然后再将指针递增一点,直到你碰到下一个管道.拉出你的子串.完成.

我只是猜测,但如果这个问题接近最快,我就不会感到惊讶.

编辑:这是我的想法.唉,这段代码是未经编译和未经测试的,但它应该证明我的意思.

特别是,Delim被视为一个单一的字符,我认为如果它能满足要求,那么它将成为一个与众不同的世界,并且PLine中的字符仅被测试一次.最后,没有与TokenNum的比较; 我相信将计数器递减到0以便计算分隔符会更快.

function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
var 
  Del: Char;
  PLine, PStart: PChar;
  Nth, I, P0, P9: Integer;
begin
  Del := Delim[1];
  Nth := TokenNum + 1;
  P0 := 1;
  P9 := Line.length + 1;
  PLine := PChar(line);
  for I := 1 to P9 do begin
    if PLine^ = Del then begin
      if Nth = 0 then begin
        P9 := I;
        break;
      end;
      Dec(Nth);
      if Nth = 0 then P0 := I + 1
    end;
    Inc(PLine);
  end;
  if (Nth <= 1) or (TokenNum = 1) then
    Result := Copy(Line, P0, P9 - P0);
  else
    Result := '' 
end;
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

4086 次

最近记录：

8 年，10 月 前
为什么CharInSet比Case语句更快？ 18
在Delphi中解析一行的最快方法是什么？ 9
更多相关链接
相关归档
如何解析/读取YAML文件到Python对象？ 96
为什么运算符比方法调用慢得多？(结构在较旧的JIT上较慢) 83
Delphi是否可作为EM64和IA64使用？ 13
将标记添加到lucene令牌流 11
gcc/C++：如果 CPU 负载较低，那么代码优化就没有多大用处，对吗？ 5
delphi:如何将TCustomFrame和记录存储在一个列表中 3
是否有可用于 SQL 的 BNF 语法？ 3
Java的SQL解析器库 - 检索SQL语句中存在的表名列表 2
C#DateTime Parser Bug？ 1
局部变量与阵列访问 1
难疑归档
为什么HTML认为"chucknorris"是一种颜色？ 7264
检查JavaScript对象中是否存在密钥？ 2750
如何使用Curl从终端/命令行发布JSON数据到测试Spring REST？ 2606
将字节转换为字符串？ 1968
@classmethod和@staticmethod对初学者的意义？ 1532
在C++中将int转换为字符串的最简单方法 1488
Apache Camel究竟是什么？ 1310
在Python中使用大写字母和数字生成随机字符串 1247
sh和bash之间的区别 1194
什么是"Linting"？ 1044