Есть ли быстрая процедура 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 } 

Я разработал эту функцию, когда я использую Delphi 4. Он вызывает очень эффективную процедуру PosEx, которая первоначально была разработана FASTCODE и теперь включен в библиотеку Delphi в StrUtils.

Недавно я обновился до Delphi 2009, и мои строки все Unicode. Эта функция GetTok по-прежнему работает и работает хорошо.

Я прошел через новые библиотеки в Delphi 2009 и есть много новых функций и дополнений к нему.

Но я не видел функцию GetToken, как мне нужно, в любой из новых библиотек Delphi, в различных проектах fastcode, и я не могу найти ничего с поиском Google, кроме Zarko Gajic's: Delphi Split/Tokenizer Functions, который не так оптимизирован, как что у меня уже есть.

Любые улучшения, даже 10% будут заметны в моей программе. Я знаю, что альтернатива - это StringLists и всегда держать токены раздельными, но у этого есть большие накладные расходы памяти, и я не уверен, что я сделал все это, чтобы преобразовать, будет ли это быстрее.

Whew. Итак, после всего этого долгого разговора, мой вопрос действительно таков:

Знаете ли вы о каких-либо очень быстрых реализациях процедуры GetToken? Оптимизированная версия ассемблера была бы идеальной?

Если нет, есть ли какие-либо оптимизации, которые вы можете увидеть в моем коде выше, что может улучшить?

---

Followup: Барри Келли упоминается вопрос, который я задал год назад об оптимизации парсинг строк в файле. В то время я даже не думал о моей программе GetTok, которая не использовалась для чтения или разбора. Только сейчас я увидел накладные расходы на мою процедуру GetTok, которая заставила меня задать этот вопрос. До ответов Карла Смотрича и Барри я никогда не думал о подключении этих двух. Так очевидно, но он просто не регистрировался. Спасибо что подметил это.

Да, мой Делим - это один символ, поэтому, очевидно, у меня есть некоторые основные оптимизации, которые я могу сделать. Мое использование 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 000 звонков PosEx заняли всего 0,03 секунды.

Затем я приурочил свою новую подпрограмму с AQTime для того же запуска и точно так же звонил. AQTime сообщает, что моя новая «быстрая» процедура заняла 3,65 секунды, что в 9 раз больше. Виновника согласно AQTime был первый цикл:

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

в то время как линия, которая была выполнена 18 миллионов раз, было сообщено на 2,66 секунды. Было сказано, что линия inc, выполненная 16 миллионов раз, занимает 0,47 секунды.

Теперь я думал, что знаю, что здесь происходит. У меня была аналогичная проблема с AQTime в вопросе, который я задал в прошлом году: Why is CharInSet faster than Case statement?

Опять же, это был Барри Келли, который меня привлек. В принципе, инструмент-профилировщик, такой как AQTime, не обязательно выполняет работу по микрооптимизации. Он добавляет накладные расходы каждой строке, которая может затушить результаты, которые четко показаны в этих числах. 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; 

Таким образом, это проверит 1000 000 звонков в GetTok.

Моя старая процедура с вызовами Pos и ​​PosEx заняла 0,29 секунды. Новый с PChars занял 2.07 секунды.

Теперь я полностью одурачен! Может ли кто-нибудь сказать мне, почему процедура PChar не только медленнее, но и в 8-9 раз медленнее !?

---

Тайна решена! Андреас сказал в своем ответе, чтобы изменить параметр Delim от строки до Char. Я всегда буду использовать только Char, так что по крайней мере для моей реализации это очень возможно. Я был поражен тем, что произошло.

Время для 1 миллиона звонков снизилось с 1,88 секунды до 0,22 секунды.

И удивительно, что время для моей исходной процедуры Pos/PosEx увеличилось с 0,29 до 0,44 секунды, когда я изменил параметр Delim на Char.

Честно говоря, я разочарован оптимизатором Delphi. Этот разделитель является постоянным параметром. Оптимизатор должен заметить, что одно и то же преобразование происходит в цикле и должно было перемещать его так, чтобы оно выполнялось только один раз.

Двойная проверка параметров генерации кода, да У меня есть Оптимизация Проверка True и String формата Off.

Суть в том, что новая процедура 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 секунды (от .47). Странно, что линия inc также снизится. Но я уже устал от всего этого тестирования.

---

Я принял идею Карла о зацикливании персонажей и переписал этот код с этой идеей. Это делает еще одно улучшение, вплоть до 0,19 секунды с 0,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, который должен быть того же типа, Integer или Byte, в зависимости от того быстрее.

Но скажем, я счастлив.

Еще раз спасибо сообществу StackOverflow Delphi.

Answer 1

Вашей новой функции (один с PChar) следует объявить «Делим» как 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 } 

Answer 2

Delphi компилирует ОЧЕНЬ эффективный код; по моему опыту, было очень сложно сделать лучше в ассемблере.

Я думаю, вы должны просто указать PChar (они все еще существуют, не так ли? Я расстался с Delphi вокруг 4.0) в начале строки и увеличил ее при подсчете «|», пока вы не найдено n-1 из них. Я подозреваю, что это будет быстрее, чем вызов PosEx.

Обратите внимание на это положение, затем увеличьте указатель еще до тех пор, пока вы не нажмете следующий трубопровод. Вытяните подстроку. Готово.

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

EDIT: Вот что я имел в виду. Этот код, увы, не скомпилирован и не проверен, но должен продемонстрировать, что я имел в виду.

В частности, 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; 

Answer 3

Использование ассемблера было бы микро-оптимизацией. Оптимизация алгоритма достигается гораздо большим успехом. Не делайте работы, делая работу как можно быстрее, каждый раз.

Один пример был бы, если у вас есть места в вашей программе, где вам нужно несколько токенов одной строки. Другая процедура, которая возвращает массив токенов, которые вы можете индексировать, должна быть быстрее, чем вызов вашей функции более одного раза, особенно если вы позволите процедуре не возвращать все токены, а только столько, сколько вам нужно.

Но в целом я согласен с ответом Карла (+1), используя PChar для сканирования, вероятно, будет быстрее, чем ваш текущий код.

Answer 4

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

У меня на самом деле есть несколько других подпрограмм, 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 } 

Answer 5

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

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

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

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

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

procedure TStrings.SetDelimitedText(const Value: string); 

Это размечает, но использует как QuoteChar и Разделитель, но использовать только Разделитель.

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

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

Answer 6

Имеет большое значение то, что ожидается «Делим». Если ожидается, что он будет единственным персонажем, вам намного лучше пройти по символу строки по символу, в идеале через PChar и тестировать именно.

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

Вы могли бы быть заинтересованы в 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 и результаты тестов.)

Answer 7

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

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

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

тип
TLastPosition = record elementnr: integer; // last tokennumber elementpos: integer; // символьный индекс последнего совпадения end;

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

, если tokennum = (lastposition.elementnr + 1), а затем начинают newpos: = posex (DELIM, линии, lastposition.elementpos); конец;

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