Delphi有没有快速的GetToken例程？

StackOverflow https://stackoverflow.com/questions/1694001

题

在我的程序中，我处理数百万个具有特殊字符的字符串，例如“ |”在每个字符串中分开令牌。我有一个返回第 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 }

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

我最近升级到 Delphi 2009，我的字符串都是 Unicode。这个 GetTok 功能仍然有效并且仍然运行良好。

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

但我还没有在任何新的 Delphi 库、各种 fastcode 项目中看到我需要的 GetToken 函数，并且除了 Google 搜索之外我找不到任何东西 扎科·加伊奇的：Delphi 拆分/分词器函数, ，它不像我已经拥有的那样优化。

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

呼。因此，在说了这么多长篇大论之后，我的问题实际上是：

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

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

跟进：巴里·凯利提到了我一年前提出的一个关于优化文件中行的解析的问题。当时我什至没有想到我的 GetTok 例程不用于读取或解析。直到现在我才看到 GetTok 例程的开销，这让我提出了这个问题。在卡尔·斯莫特里茨和巴里给出答案之前，我从未想过将两者联系起来。如此明显，但它只是没有注册。感谢您指出了这一点。

是的，我的 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 来查看发生了什么。我的运行包括 1,108,514 次对 GetTok 的调用。

AQTime 将原始例程计时为 0.40 秒。对 Pos 的一百万次调用只用了 0.10 秒。50 万个 TokenNum = 1 副本花费了 0.10 秒。60万个PosEx呼叫只用了0.03秒。

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

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

while 行执行了 1800 万次，报告执行时间为 2.66 秒。inc 行执行了 1600 万次，据说只需要 0.47 秒。

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

又是巴里·凯利给我提供了线索。基本上，像 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;

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

我的 Pos 和 PosEx 调用的旧过程花了 0.29 秒。新的 PChars 耗时 2.07 秒。

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

谜团已揭开！Andreas 在他的回答中说将 Delim 参数从字符串更改为 Char。我将始终只使用 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 线也会下降。但我已经因为所有这些测试而疲惫不堪了。

我采用了卡尔的按字符循环的想法，并用这个想法重写了代码。它又取得了进步，从 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 社区。

有帮助吗？

解决方案

您的新函数（带有 PChar 的函数）应将“Delim”声明为 查尔 而不是作为 细绳. 。在当前的实现中，编译器必须将 PLine^ 字符转换为字符串，以将其与“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 }

其他提示

这对“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;

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

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;

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

结果如下：

*** 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 链接和基准测试结果。）

Delphi 编译成非常高效的代码；根据我的经验，很难用汇编程序做得更好。

我认为你应该只指向一个 PChar （它们仍然存在，不是吗？我在字符串的开头与 Delphi 4.0 左右分道扬镳，并在计算“|”时递增它，直到找到 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;

使用汇编器将是一种微观优化。通过优化算法可以获得更大的收益。每次都不做工作胜过以最快的方式做工作。

一个例子是，如果您的程序中有些地方需要同一行的多个标记。另一个返回标记数组的过程应该比多次调用您的函数要快，特别是如果您让该过程不返回所有标记，而只返回所需数量的标记，您可以将其索引到该数组中。

但总的来说，我同意卡尔的答案（+1），使用 PChar 扫描可能会比您当前的代码更快。

这是我的个人库中已有相当长一段时间并广泛使用的功能。我相信这是它的最新版本。我过去曾出于各种不同的原因优化过多个版本。这个尝试考虑引用的字符串，但如果删除该代码，它会使函数稍微快一点。

实际上，我还有许多其他例程，CountSections 和 ParseSectionPOS 就是几个例子。

不幸的是，这个例程仅基于 ansi/pchar。虽然我不认为将其转移到 unicode 会很困难。也许我已经这样做了......我必须检查一下。

笔记：该例程的 ParseNum 索引基于 1。

function ParseSection(ParseLine: string; ParseNum: Integer; ParseSep: Char; QuotedStrChar:char = #0) : string;
var
   wStart, wEnd : integer;
   wIndex : integer;
   wLen : integer;
   wQuotedString : boolean;
begin
   result := '';
   wQuotedString := false;
   if not (ParseLine = '') then
   begin
      wIndex := 1;
      wStart := 1;
      wEnd := 1;
      wLen := Length(ParseLine);
      while wEnd <= wLen do
      begin
         if (QuotedStrChar <> #0) and (ParseLine[wEnd] = QuotedStrChar) then
            wQuotedString := not wQuotedString;

         if not wQuotedString and (ParseLine[wEnd] = ParseSep) then
         begin
            if wIndex=ParseNum then
               break
            else
            begin
               inc(wIndex);
               wStart := wEnd+1;
            end;
         end;
         inc(wEnd);
      end;

      result := copy(ParseLine, wStart, wEnd-wStart);
      if (length(result) > 0) and (QuotedStrChar <> #0) and (result[1] = QuotedStrChar) then
         result := AnsiDequotedStr(result, QuotedStrChar);
   end;
end; { ParseSection }

在您的代码中，我认为这是唯一可以优化的行：

Result := copy(Line, P+1, MaxInt)

如果您在那里计算新的长度，它可能会快一点，但不是您想要的 10%。

你的标记化算法看起来相当不错。为了优化它，我将通过分析器运行它（例如 AQ时间 来自 AutomatedQA）以及生产数据的代表性子集。这将指出你最薄弱的地方。

唯一接近的 RTL 函数是 Classes 单元中的这个函数：

procedure TStrings.SetDelimitedText(const Value: string);

它标记化，但同时使用 引用字符 和 分隔符, ，但您只使用分隔符。

它使用 设置字符串 系统单元中的函数，这是一种基于 PChar/PAnsiChar/PUnicodeChar 和长度设置字符串内容的快速方法。

这也可能会给你带来一些进步；另一方面， 复制 真的也很快。

我不是一个总是指责算法的人，但如果我看一下第一条消息来源、 问题是，对于字符串 N，您也要对字符串 1...n-1 进行 POS/posexes。

这意味着对于 N 个项目，您需要对 (n, n-1,n-2...1) POSes (=+/- 0.5*N^2) 求和，而只需要 N 个。

如果您只是缓存最后找到的结果的位置，例如在通过VAR参数传递的记录中，你可以获得很多收获。

类型
TLastPosition = record elementnr ：整数;// 最后的标记数 elementpos：整数;// 最后匹配的字符索引 结束；

然后一些东西

if tokennum=(lastposition.elementnr 1) then 兴办 newpos:=posex(delim,line,lastposition.elementpos)；结尾;

不幸的是，我现在没有时间写出来，但我希望你明白

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top