21

私のプログラムでは、「|」などの特殊文字を含む何百万もの文字列を処理しています。各文字列内でトークンを分離します。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 によって開発され、現在 Delphi の StrUtils ライブラリに含まれている非常に効率的な PosEx ルーチンを呼び出します。

最近 Delphi 2009 にアップグレードしましたが、文字列はすべて Unicode です。この GetTok 関数は引き続き機能し、問題なく機能します。

私は Delphi 2009 の新しいライブラリを調べましたが、多くの新しい機能と追加機能があります。

しかし、さまざまな fastcode プロジェクトで、新しい Delphi ライブラリのいずれかで必要な GetToken 関数を見たことがありません。また、 Zarko Gajic の Delphi Split / Tokenizer Functions以外の Google 検索では何も見つかりません。私がすでに持っているものと同じくらい最適化されています。

私のプログラムでは、10％でも改善が見られます。代替手段は StringLists であり、常にトークンを別々に保つことは知っていますが、これにはメモリに関して大きなオーバーヘッドがあり、変換するためにすべての作業を行ったかどうかはわかりません。

うわー。この長々とした話の後で、私の質問は次のとおりです。

GetToken ルーチンの非常に高速な実装を知っていますか? アセンブラに最適化されたバージョンが理想的でしょうか?

そうでない場合、上記の私のコードに改善をもたらす可能性のある最適化はありますか?

フォローアップ: Barry Kelly は、私が 1 年前にファイル内の行の解析を最適化することについて尋ねた質問に言及しました。その時、私は自分の GetTok ルーチンが読み取りや解析に使用されていないことさえ考えていませんでした。GetTok ルーチンのオーバーヘッドを見て、この質問をするようになったのは今だけです。Carl Smotricz と Barry の回答があるまで、私はこの 2 つを結びつけることを考えたことはありませんでした。とても明白ですが、登録されませんでした。ご指摘ありがとうございます。

はい、私の Delim は 1 人のキャラクターなので、大幅な最適化を行うことができます。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 への 100 万回の呼び出しには 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 で同様の問題が発生しました。なぜ CharInSet は Case ステートメントよりも高速ですか?

ここでも Barry Kelly が私にヒントを与えてくれました。これらの数値で明確に示されている結果を圧倒する可能性のある各行にオーバーヘッドが追加されます。新しい「最適化されたコード」で実行された 3,400 万行は、元のコードの数百万行を圧倒し、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 に変更するように彼の回答で述べました。私は常に Char だけを使用するので、少なくとも私の実装ではこれは非常に可能です。何が起こったのか私は驚いた。

100 万回の呼び出しにかかる時間は、1.88 秒から 0.22 秒に短縮されました。

そして驚いたことに、元の Pos/PosEx ルーチンの時間は、Delim パラメータを Char に変更すると、0.29 秒から 0.44 秒に短縮されました。

率直に言って、Delphi のオプティマイザにはがっかりしています。その Delim は定数パラメーターです。オプティマイザーは、同じ変換がループ内で発生していることに気付き、それを移動して、一度だけ実行されるようにする必要があります。

コード生成パラメーターを再確認します。はい、最適化はTrueで文字列形式はオフにチェックしています。

要するに、Andrea の修正を加えた新しい PChar ルーチンは、私のオリジナルよりも約 25% 高速です (.22 対 .29)。

ここで他のコメントをフォローアップして、テストしたいと思います。

最適化をオフにして文字列形式のチェックをオンにすると、時間が 0.22 から 0.30 に増加するだけです。オリジナルにほぼ同じものを追加します。

アセンブラ コードを使用すること、または Pos や PosEx などのアセンブラで記述されたルーチンを呼び出すことの利点は、設定したコード生成オプションの影響を受けないことです。それらは常に同じ方法で実行され、事前に最適化され、肥大化することはありません。

ここ数日、マイクロ最適化のコードを比較する最良の方法は、CPU ウィンドウでアセンブラー コードを見て比較することだと再確認しました。Embarcadero がそのウィンドウをもう少し使いやすくして、クリップボードに部分的にコピーしたり、その一部を印刷したりできるようにしてくれたらいいのにと思います。

また、この投稿の前半で AQTime を不当に非難しました。新しいルーチンに余分な時間が追加されたのは、AQTime によって追加されたインストルメンテーションが原因だと考えていました。戻って String の代わりに Char パラメーターを使用して確認したところ、while ループは (2.66 から) 0.30 秒に短縮され、inc ラインは (0.47 から) 0.14 秒に短縮されました。インクラインも下がるのは奇妙です。しかし、私はすでにこのすべてのテストに疲れています。

文字単位でループするという Carl のアイデアを取り入れて、そのコードをそのアイデアで書き直しました。.22 秒から .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 コミュニティに改めて感謝します。

4

7 に答える 7

12

「Delim」に期待されるものは大きく異なります。単一の文字であることが予想される場合は、文字列を 1 文字ずつ、理想的には PChar を介してステップ実行し、具体的にテストする方がはるかに優れています。

長い文字列の場合、Boyer-Moore および同様の検索には、スキップ テーブルのセットアップ フェーズがあり、テーブルを一度作成して、その後の各検索でそれらを再利用するのが最善の方法です。つまり、呼び出しの間に状態が必要であり、この関数は代わりにオブジェクトのメソッドとして使用する方がよいでしょう。

Delphi で行を解析する最速の方法について、以前に質問したこの回答に興味があるかもしれません。（しかし、質問をしたのはあなただと思います！それにもかかわらず、あなたの問題を解決する際に、Delimが通常どのように見えるかに応じて、あなたが使用しているようなPosExを使用するのではなく、解析について説明した方法に固執します。）

更新: OK、これを見て約 40 分を費やしました。区切り文字が文字になることがわかっている場合は、ほとんどの場合、2 番目のバージョン (つまり PChar スキャン) の方が適していますがDelim、文字として渡す必要があります。執筆時点では、PLine^Char 型の式を文字列に変換して、Delim と比較しています。それは非常に遅くなります。文字列にインデックスを付けてDelim[1]も、やや遅くなります。

ただし、行の大きさと、引き出したい区切られたピースの数によっては、トークン化ルーチン内の不要な区切られたピースをスキップするよりも、再開可能なアプローチを使用したほうがよい場合があります。現在ミニ ベンチマークで行っているように、連続して増加するインデックスで GetTok を呼び出すと、O(n*n) のパフォーマンスが得られます。ここで、n は区切られたセクションの数です。スキャンの状態を保存して次の反復のために復元するか、抽出されたすべてのアイテムを配列にパックすると、これを O(n) に変えることができます。

すべてのトークン化を 1 回実行し、配列を返すバージョンを次に示します。ただし、配列の大きさを知るために、2 回トークン化する必要があります。一方、文字列を抽出する必要があるのは 2 番目のトークン化だけです。

// 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 のリンクとベンチマークの結果を更新しました。)

于 2009-11-08T03:54:15.290 に答える
11

新しい関数 (PChar を使用する関数) は、「Delim」をStringではなくCharとして宣言する必要があります。現在の実装では、コンパイラは 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 }
于 2009-11-08T09:43:14.597 に答える
9

Delphi は非常に効率的なコードにコンパイルされます。私の経験では、アセンブラでうまくやるのは非常に困難でした。

文字列の先頭に PChar (まだ存在しますよね? Delphi とは 4.0 前後で別れました) を指定し、n-1 が見つかるまで "|" をカウントしながらインクリメントする必要があると思います。そのうちの。PosEx を繰り返し呼び出すよりも高速になると思います。

その位置をメモしてから、次のパイプに到達するまでポインターをさらに増やします。部分文字列を引き出します。終わり。

推測にすぎませんが、これがこの問題を解決できる最速に近かったとしても驚かないでしょう。

編集：これが私が念頭に置いていたことです。残念ながら、このコードはコンパイルもテストもされていませんが、私の意図を示すはずです。

特に、Delim は単一の文字として扱われます。これが要件を満たしている場合、大きな違いが生じると思います。PLine の文字は 1 回だけテストされます。最後に、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;
于 2009-11-07T19:08:40.607 に答える
2

アセンブラを使用すると、マイクロ最適化になります。アルゴリズムを最適化することで得られる利益ははるかに大きくなります。仕事をしないことは、常に可能な限り最速の方法で仕事をすることよりも優れています。

1 つの例は、同じ行の複数のトークンが必要な場所がプログラム内にある場合です。インデックスを作成できるトークンの配列を返す別のプロシージャは、関数を複数回呼び出すよりも高速である必要があります。特に、プロシージャがすべてのトークンを返すのではなく、必要な数だけを返すようにする場合はそうです。

しかし、一般的に、カールの答え (+1) に同意しPCharます。スキャンに a を使用すると、現在のコードよりもおそらく高速になります。

于 2009-11-07T19:33:25.483 に答える
1

これは、私が個人のライブラリにかなり長い間持っていた機能であり、私は広く使用しています。これが最新バージョンだと思います。私は過去にさまざまな理由で最適化された複数のバージョンを持っていました。これは引用符で囲まれた文字列を考慮に入れようとしますが、そのコードが削除されると、関数が少し速くなります。

私は実際に他の多くのルーチンを持っています。CountSectionsとParseSectionPOSはいくつかの例です。

残念ながら、このルーチンはansi/pcharベースのみです。ユニコードに移行するのは難しいとは思いませんが。多分私はすでにそれをしました...私はそれをチェックしなければなりません。

注：このルーチンは、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 }
于 2009-11-08T01:08:53.350 に答える
1

私は常にアルゴリズムを非難する人ではありませんが、ソースの最初の部分を見ると、問題は文字列 N の場合、文字列 1..n-1 の POS/posexes も実行することです。

これは、N 個のアイテムの場合、合計 (n, n-1,n-2...1) POSes (=+/- 0.5*N^2) を実行することを意味しますが、必要なのは N 個だけです。

VAR パラメータによって渡されるレコードなど、最後に見つかった結果の位置を単純にキャッシュすると、多くのことが得られます。

type
TLastPosition = record elementnr : integer; // 最後の tokennumber elementpos: integer; // 最後に一致した文字インデックス end;

そして何か

tokennum=(lastposition.elementnr+1) の場合、newpos:=posex(delim,line,lastposition.elementpos) を開始します。終わり;

残念ながら、今はそれを書く時間がありませんが、あなたがその考えを理解してくれることを願っています.

于 2009-11-09T13:00:00.530 に答える
1

あなたのコードでは、これが最適化できる唯一の行だと思います：

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

そこで新しい長さを計算すると、少し速くなるかもしれませんが、探している 10% にはなりません。

あなたのトークン化アルゴリズムはかなり問題ないようです。それを最適化するために、本番データの代表的なサブセットを使用してプロファイラー (AutomatedQAのAQTimeなど) を実行します。それはあなたを最も弱い場所に導きます。

近い唯一の RTL 関数は、クラス ユニットの次の関数です。

procedure TStrings.SetDelimitedText(const Value: string);

トークン化しますが、QuoteCharとDelimiterの両方を使用しますが、 Delimiter のみを使用します。

System ユニットでSetString関数を使用します。これは、PChar/PAnsiChar/PUnicodeChar と長さに基づいて文字列の内容を設定する非常に高速な方法です。

これにより、改善も得られる可能性があります。一方、コピーも非常に高速です。

于 2009-11-08T03:21:21.570 に答える