が高速GetToken日常のためのDelphi?

Question

私のプログラムでは、工程単位百万文字列の特殊性から、例えば"|"を別々のトークン内の文字列になります。している機能の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 }

私はこのたび開発した機能が使っていたDelphi4.で、非常に効率的なPosExルーチンが独自に開発したFastcodeは、StrUtils図書館をご利用いただけます:standardとexpress。

私は最近アデ2009年、私の文字列はすべてのUnicodeで扱います。このGetTok機能が作品がより確かなものになるはずだ。

ごあいを通じて新たな図書館デ2009年多くの新機能を追加します。

しかしながGetTokenのような機能が必要で、新しいデイの様々なfastcodeプロジェクトか、Google検索の他 Zarko Gajic：デ分割/トークナイザの機能, ないとして最適化したとして何を持っています。

の改善にも、10%が目立った。知っているインタビューを受けたことがあStringLists、常にトークンを分離が大きなオーバーヘッドメモリー-ワイスといったすべての作業に変換するかいずになります。

フッ。にその後のこの冗談、私の質問をするのは:

いず非常に高速実装のGetTokenします。アセンブラに最適化した版が最適であることが?

ない場合は、他の最適化を行うまで見ることができます自分のコード以上になるというのだろうか。

---

フォローアップ:バリー-ケリー上に質問を聞いてみることにした年前の約最適化の解析を行ファイルです。その時はなかったのでもう私のGetTok通常利用されなかったのを読み込みまたは構文解析.では今だけは私のオーバーヘッドのマGetTok日常のないこの質問です。までカール-Smotriczとハーモニーランドのパスポートの回答にも思わなかったのを接続します。では明らかではもったい登録があります。メポインティングです。

あり、私のDelimは単一の文字で明らかにしていくつかの主要な最適化できます。私のPosやPosExのGetTokルーチン(上)が眩いという考えのもとによって全然違いますので、文字による文字検索ではなく、ビットのようなコード:

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

行っていく皆さんの応答して様々な提案を比較します。そんなポスト。

---

混乱:大丈夫、私に戸惑う.

ったカールとハーモニーランドのパスポートとの勧告を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秒です。半百万円のTokenNum=1にコピーした0.10秒です。の600,000PosEx話した0.03秒です。

その時間も通常とAQTimeの実行と同じます。AQTime報告する私の新しい"高速"日常のた3.65秒、9回すこともできます。原因によるAQTimeした最初のループ：

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

さらに、処刑された18百万円、報告されたので2.66秒です。の株式会社ライン、実施された16百万円、たといわれる0.47秒です。

今思ったんで何が起きているのです。また同様の問題がAQTimeうえ、昨年: なぜCharInSetよりも早く場合。

再れたバリー-ケリーの人cluedいます。基本的には、instrumentingプロファイラのようにAQTimeないための仕事microoptimization.を加え、オーバーヘッド各線が沢の結果を得ることが明らかにされます。34万回線を行った新たな"最適化コード"を圧倒する数百万回線の独自のコードだそうでない架からのPosやPosExがありました。

ハーモニーランドのパスポートしてくれたサンプルコードを使用QueryPerformanceCounterチェックした内容に間違いがないか確認し、その場合だった気がします。

大丈夫、同じっQueryPerformanceCounterることを証明する私の新しいルーチンはより迅速ない9倍になってAQTimeいます。そこでん:

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秒です。

今は完全にbefuddled!誰でもできるので教えてくだPChar手続きは遅くとも8 9倍になっ!?

---

謎を解消！アンドレアスと彼の答えを変更しDelimパラメータから文字列を文字に置き換わります。私は常に使用でChar、少なくとも私のこの実装は可能です。驚きかった。

時間の1万下がったから1.88秒.22秒です。

と驚くほどの時間を作っPos/PosEx日常かが今後の検討課題になって.29に.44秒の時に変更でDelimパラメータを文字に置き換わります。

正直、私は失望Delphiのオプティマイザ.そのDelimは一定のパラメータとします。バージョンのオプティマイザは気づいて同一の変換が起こっているのループとして移動で行うだけである。

ダブルチェックマーコード生成パラメータは、そのきっかけをつくっていきたい真の最適化および文字列形式のチェック。

ボトムラインの新しいPCharルーチンとアンドレアの修正は約25%高速化によってオリジナル（.22対.29).

いに関するフォローアップその他のコメントここでは、試験を行います。

---

Off最適化およびon文字列形式のみで確認の時間から.22ます。30.を加えて同一のオリジナルです。

の利用アセンブラコードは、呼び出しルーチンを書アセンブラのようなPosやPosExはその対象となどのコード生成オプションされます。それらは常に走行も同じように事前に最適化された非肥大化。

いて再確認最終日に、最良の方法と比較コードmicrooptimizationによる比較し、アセンブラコードのCPUます。れていただければと思いまEmbarcaderoがそのウィンドウから少し便利に、よりコピー部分をクリップボードまたは印刷部門です。

また、不当に叩きAQTime前のこと、考えるような追加の新作のみでの計測が追加されます。今からチェックのCharのパラメータの代わりに文字列の中にループは.30秒から2.66）、株式会社ラインは.14秒から.47).不思議なことに、株式会社ラインのみが先行してます。がようになっていくからこの試験です。

---

ったカールのループを文字列により、rewroteをコードするアイデアです。でも、改善を.19秒ます。22.なので、あちらこちらではのこれまで:

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比較し、同じ種類、整数またはバイトのいずれかになります。

ものということか嬉しいです。

今回もまた、StackOverflow Delphiます。

Answer 1

として "DELIM" を宣言する必要がありますあなたの新しい関数（PChar型との1）のシャアのといないの Stringとしての。あなたの現在の実装では、コンパイラは、「DELIM」とそれを比較する文字列にPLINE ^文字を変換する必要があります。そして、それは巨大なパフォーマンスヒットをされたタイトなループ内で起こります。

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 }

Answer 2

で大きな差をなんと"Delim"期待されます。だが予想され単一の文字だかないほうがよいステッピングを通じて、文字列の文字による文字が理想をPChar、試験に注目する必要があると主張した。

までの長い文字列、Boyer-Mooreよび類似検索にセットアップ相のためのスキップテーブル、および最良の方法も、テーブルは、一度に再生し、そうです。が必要な状態との間の通話は、この機能がないほうがよい方法として、オブジェクトです。

おに興味を持っているかもしれに この答えを行いました問いかけにはなお時間、インターネットには想像もつかな解析のために回線をご利用いただけます:standardとexpress。 もいたように、これまでとは違ったのですが要求されることの問題です！しかしながら、問題点の解決に、hewるかに記載の解析、 ない 使用PosExのような使用によっては、何Delim通常ようになります。●)

---

更新:OKを使った約40分のみです。がわかっている場合は、それを区切り文字は文字には、ほとんどいないほうがよいと第二版（PCharクレジットカードにチャーが伝授しなければならな Delim しています。時には、変換する PLine^ 表現型の文字を文字列との比較Delim.ることは非常に遅;でも指数付けの文字列 Delim[1] もやや遅れている。

しかし、場合によって大きさの線において、どのように多くの区切りの作品にしたいの抜きないほうがよいとresumableアプローチよりも飛び不要な区切り内部のtokenizing。お問い合わせいただいた場合のGetTokとを順次増や指標にいるかのような現在のようにごミニベンチマークょO(n-n)は、nの数に区切ります。変えることができるO(n)の場合の保存の状態をスキャンを回復することで繰り返し、パックすべて抽出した項目を、配列になります。

このバージョンはすべてのtokenizationば、配列を返します.でtokenize()回も知るために、どのように大型の配列になります。一方、第二tokenizationニーズの抽出文字列:

// 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;

こちらresumableます。の負荷店舗のバッファの現在位置の区切り文字があって、コストも

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

の特性に応じて、コーディネイトスタイルで、見るかどうかの区切り文字が文字などのお仕事で異なるアプローチで可能になります。

(失敗したのですが、私の前のプログラム、僕測定同業スタイル。更新したのふリンクアンドベンチマーク結果になります。

Answer 3

デ統非常に効率的なコード私の経験をそろえることはなかなか困難ですがどのようにアセンブラ.

と思いきっ点PChar(そのものなのでしょう。別れの方法とデルフィ周辺4.0)の先頭に文字列を増加させながら数え"|""sまでですがその場で発音を確認することがn-1です。思うよりも早く呼び出しPosExを繰り返す。

りますのでご注意下になるように、その増加のポインタがありまでに発しなければなりません。次のパイプです。抜きのお部分文字列.行われます。

私だけの顔がくださればこkm圏内にあり迅速にこの問題を解決しました。

編集： ここでは、違っていたことに気づきました。このコードは、アートワークuncompiled、潜在的に秘なることを明確に示すべきであるいうことを意味する。

特に、Delimれており、単一のcharいと考えている世界のた場合は差額をその基準を満たし、文字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;

Answer 4

アセンブラを使用すると、マイクロ最適だろう。アルゴリズムを最適化することによりいたことにはるかに大きな利益があります。 、最速の方法で仕事をして、すべての時間を仕事ビートを行っていない。

あなたは同じラインのいくつかのトークンを必要とするプログラム内の場所を持っている場合は、

一つの例は以下のようになります。あなたは、その後のインデックスを使用して、手順はすべてのトークンを返さないようにしましょう場合は特に、複数回、あなたの関数を呼び出すよりも高速でなければなりませんが、あなたが必要としてのみなど、多くのことができます。

トークンの配列を返します別の手順

しかし、一般的に、私はおそらく、あなたの現在のコードよりも高速になりスキャン用PCharを使用して、カールの回答（1）と一致します。

Answer 5

これは私が広範囲に使用かなりの時間のための私の個人的なライブラリに持っていた機能です。私は、これはそれの最新バージョンであると考えています。私は、異なる様々な理由のために最適化されている過去の複数のバージョンを持っていました。この1は考慮に引用符で囲まれた文字列を取るしようとしますが、そのコードが削除された場合には、機能がわずかに少し速くなります。

私は実際には他のルーチン、CountSectionsと例のカップルであることParseSectionPOSの数を持っています。

Unfortuatelyこのルーチンは唯一のもと、ANSI / PChar型です。私はunicodeにそれを移動するのは難しいだろうとは思いませんが。たぶん私はすでに、私はそれをチェックする必要があります...ことをやりました。

注：このルーチンは、1 ParseNumのインデックスに基づいています。

。

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 }

Answer 6

コードで、このラインを最適化することができ:

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

場計算の新しい長さのもの、それが少し速くないが、10%にしたものです。

おtokenizingアルゴリズムのようんOKです。を最適化し、実行してプロファイラなど AQTime からAutomatedQA)の代表のサブセットの生産データです。いま最も弱いスポットです。

の労働教養機能付近はこの授業の単位

procedure TStrings.SetDelimitedText(const Value: string);

でtokenizesものの両方を使用 QuoteChar や 区切り文字, ものだけを使用になります。

使用する SetString 機能システムユニットは速い方法の設定のコンテンツの文字列に基づくPChar/PAnsiChar/PUnicodeCharおよび長さです。

がんの一部改善など一方で、 コピー 本当に速います。

Answer 7

私はいつもアルゴリズムを責める人ではないんだけど、私はソースの最初の部分を見れば、 問題は、文字列Nのために、あなたも再び文字列1..nの-1用POS / posexesを行うということです。

これは、あなたがサムを行い、N項目手段（N、N-1、N-2 ... 1）ポーズ（= + / - 0.5 * N ^ 2）。、のみNが必要とされている間、

あなたは、単に最後に見つかった結果の位置をキャッシュした場合、例えばVARパラメータで渡されたレコードで、あなたは多くのことを得ることができます。

入力      TLastPosition =記録                        elementnr：整数; //最後tokennumber                        elementpos：整数;最後の試合の//文字インデックス                        終わり;

、その後何か

もしtokennum =（lastposition.elementnr + 1）、次いで     ベギン       newpos：= POSEX（DELIM、ライン、lastposition.elementpos）。     終了;

残念ながら、私はそれを書くために、今の時間を持っていないが、私はあなたのアイデアを得る願っています。