Существует ли быстрая стандартная программа GetToken для Delphi?

Это функция, которой я пользовался в своей личной библиотеке в течение достаточно долгого времени и которой я активно пользуюсь. Я считаю, что это самая актуальная версия. В прошлом у меня было несколько версий, оптимизированных по разным причинам. Этот пытается учесть строки в кавычках, но если этот код будет удален, это сделает функцию немного быстрее.

На самом деле у меня есть ряд других подпрограмм, CountSections и ParseSectionPOS являются парой примеров.

К сожалению, эта процедура основана только на 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 }

Имеет большое значение, каким должен быть "Делим". Если ожидается, что это будет одиночный символ, вам будет гораздо лучше переходить от одного символа к другому, в идеале с помощью PChar, и специально тестировать.

Если это длинная строка, поисковые запросы Бойера-Мура и подобные им имеют набор -up для пропуска таблиц, и лучший способ - создать таблицы один раз и повторно использовать их для каждой последующей находки. Это означает, что вам нужно состояние между вызовами, и эту функцию лучше использовать как метод объекта.

Возможно, вас заинтересует ответ, который я дал на вопрос некоторое время назад, о самом быстром способе разобрать строку в 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

В зависимости от характеристик ваших данных,

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 для сканирования, вероятно, будет быстрее, чем ваш текущий код.

В вашем коде, я думаю, это единственная строка, которую можно оптимизировать:

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

Если вы вычислите новую длину там, она может стать немного быстрее, но не на 10%, которые вы ищите.

Ваш алгоритм токенизации кажется вполне нормальным. Для оптимизации я бы пропустил его через профилировщик (например, AQTime от AutomatedQA) с репрезентативным подмножеством ваших производственных данных. Это укажет вам на самое слабое место.

Единственная функция RTL, которая подходит близко, - это функция в модуле классов:

procedure TStrings.SetDelimitedText(const Value: string);

Она токенизирует, но использует как QuoteChar , так и Delimiter ], но вы используете только разделитель.

Он использует функцию SetString в системном модуле, что является довольно быстрым способом установки содержимого строки на основе PChar / PAnsiChar / PUnicodeChar и length.

Это тоже может помочь вам; с другой стороны, Копирование тоже действительно быстрое.

Я не тот человек, который всегда обвиняет алгоритм, но если я посмотрю на первую часть источника, проблема в том, что для строки N вы снова выполняете POS / Posexes для строки 1..n-1.

Это означает, что для N элементов вы выполняете sum (n, n-1, n-2 ... 1) POSes (= + / - 0,5 * N ^ 2), а требуется только N.

Если вы просто кэшируете позицию последнего найденного результата, например, в записи, переданной с помощью параметра VAR, вы можете получить много.

типа
TLastPosition = запись elementnr: целое число; // номер последнего токена elementpos: целое число; // индекс символа последнего совпадения конец;

и затем что-то

if tokennum = (lastposition.elementnr + 1), то начать newpos: = Posex (разделитель, строка, lastposition.elementpos); end;

К сожалению, сейчас у меня нет времени писать это, но я надеюсь, что вы поняли идею