delphi - Delphi 有快速的 GetToken 例程吗？

Question

在我的程序中，我处理了数百万个具有特殊字符的字符串，例如“|”分隔每个字符串中的标记。我有一个函数可以返回第 n 个 token ，就是这样:

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 }

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

我最近升级到 Delphi 2009，我的字符串都是 Unicode。这个 GetTok 函数仍然有效并且仍然有效。

我已经浏览了 Delphi 2009 中的新库，其中有许多新功能和附加功能。

但是我还没有在任何新的 Delphi 库和各种 fastcode 项目中看到我需要的 GetToken 函数，除了 Zarko Gajic's: Delphi Split / Tokenizer Functions 之外，我在 Google 搜索中找不到任何东西。 ，这不像我已经拥有的那样优化。

在我的程序中，任何改进，甚至 10% 都会很明显。我知道另一种选择是 StringLists 并始终将标记分开，但这在内存方面有很大的开销，我不确定我是否做了所有这些工作来转换它是否会更快。

哇。所以在说了这么多冗长的谈话之后，我的问题真的是:

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

如果没有，您是否可以对我上面的代码进行任何优化以进行改进？

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

是的，我的 Delim 是一个单一的角色，所以很明显我可以做一些重大的优化。我在 GetTok 例程(上面)中使用 Pos 和 PosEx 让我不知道我可以通过逐个字符搜索来更快地完成它，代码如下:

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

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

困惑:好吧，现在我真的很困惑。

我采纳了 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 }

在纸面上，我认为你不能做得比这更好。

所以我把这两个例程都放到了任务中，并使用 AQTime 来查看发生了什么。我的运行包括对 GetTok 的 1,108,514 次调用。

AQTime 将原始例程计时为 0.40 秒。对 Pos 的百万次调用耗时 0.10 秒。 50 万个 TokenNum = 1 份需要 0.10 秒。 600,000 次 PosEx 调用仅用了 0.03 秒。

然后我用 AQTime 为我的新例程计时，以进行相同的运行和完全相同的调用。 AQTime 报告说我的新“快速”例程花费了 3.65 秒，是它的 9 倍。根据 AQTime 的罪魁祸首是第一个循环:

     while (PLine^ <> #0) and (PLine^ <> Delim) do
       inc(PLine);

执行 1800 万次的 while 行报告为 2.66 秒。据说执行 1600 万次的 inc 线需要 0.47 秒。

现在我想我知道这里发生了什么。我在去年提出的一个问题中遇到了与 AQTime 类似的问题: Why is CharInSet faster than Case statement?

再次是 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;

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

我使用 Pos 和 PosEx 调用的旧程序耗时 0.29 秒。
带有 PChars 的新版本耗时 2.07 秒。

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

谜团已揭开! Andreas 在他的回答中说将 Delim 参数从字符串更改为 Char。我将始终只使用一个字符，所以至少对于我的实现来说这是很有可能的。我对发生的事情感到惊讶。

100 万次调用的时间从 1.88 秒减少到 0.22 秒。

令人惊讶的是，当我将 Delim 参数更改为 Char 时，我原来的 Pos/PosEx 例程的时间从 0.29 秒增加到 0.44 秒。

坦率地说，我对 Delphi 的优化器很失望。 Delim 是一个常量参数。优化器应该注意到循环中正在发生相同的转换，并且应该将其移出，以便它只执行一次。

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

最重要的是，使用 Andrea 修复的新 PChar 例程比我的原始例程快 25%(0.22 对 0.29)。

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

关闭优化并打开字符串格式检查只会将时间从 0.22 增加到 0.30。它添加了与原始相同的内容。

使用汇编程序代码或调用用汇编程序编写的例程(如 Pos 或 PosEx)的优势在于它们不受您设置的代码生成选项的影响。它们将始终以相同的方式运行，一种预先优化且不臃肿的方式。

我在最近几天重申，比较微优化代码的最佳方法是在 CPU 窗口中查看和比较汇编程序代码。如果 Embarcadero 能让那个窗口更方便一点，并允许我们将部分复制到剪贴板或打印其中的部分，那就太好了。

此外，我在这篇文章的早些时候不公平地抨击了 AQTime，认为为我的新例程添加的额外时间完全是因为它添加了仪器。现在我回去检查 Char 参数而不是 String，while 循环下降到 0.30 秒(从 2.66 开始)，并且 inc 线下降到 0.14 秒(从 0.47 开始)。奇怪的是 inc 线也会下降。但我已经厌倦了所有这些测试。

我采用了 Carl 的按字符循环的想法，并用这个想法重写了代码。它进行了另一项改进，从 0.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;

对此可能还有一些小的优化，例如 CurToken = Tokennum 比较，它们应该是相同的类型，Integer 或 Byte，以更快的为准。

但是，让我们说，我现在很高兴。

再次感谢 StackOverflow Delphi 社区。

Answer 1

它对“Delim”的预期有很大的不同。如果预计它是单个字符，那么最好逐个字符地遍历字符串，最好是通过 PChar，并专门进行测试。

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

您可能对 this answer I gave to a question some time before, about the fastest way to parse a line in Delphi. 感兴趣(但我看到是您提出了这个问题!不过，在解决您的问题时，我会遵循我描述的解析方式， 而不是 像您使用的那样使用 PosEx，这取决于通常的 Delim好像。)

UPDATE :好的，我花了大约 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;

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

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;

Here's the full program I used for benchmarking.

结果如下:

*** 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

根据数据的特征、分隔符是否可能是字符以及您如何使用它，不同的方法可能会更快。

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