Быстрое заполнение строки в Delphi

Question

Я пытался ускорить определенную процедуру в приложении, а мой профилировщик AQTime идентифицировал один метод, в частности, как узкое место. Этот метод был с нами на протяжении многих лет, и является частью «MISC» -Unit:

function cwLeftPad(aString:string; aCharCount:integer; aChar:char): string; 
var 
    i,vLength:integer; 
begin 
    Result := aString; 
    vLength := Length(aString); 
    for I := (vLength + 1) to aCharCount do  
    Result := aChar + Result; 
end; 

В рамках программы, что я оптимизируя на данный момент метод был назван ~ 35K раз, и это потребовало ошеломляющих 56% времени выполнения!

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

function cwLeftPad(const aString:string; aCharCount:integer; aChar:char): string; 
begin 
    Result := StringOfChar(aChar, aCharCount-length(aString))+aString; 
end; 

что дало значительный импульс. Общее время работы от 10,2 с до 5,4 сек. Потрясающие! Но cwLeftPad по-прежнему составляет около 13% от общего времени работы. Есть ли простой способ оптимизировать этот метод?

Answer 1

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

1. Выделите строку общей требуемой длины.
2. Заполните первую порцию символа прокладки.
3. Заполните оставшуюся часть входной строкой.

Вот пример:

function cwLeftPad(const aString: AnsiString; aCharCount: Integer; aChar: AnsiChar): AnsiString; 
var 
    PadCount: Integer; 
begin 
    PadCount := ACharCount - Length(AString); 
    if PadCount > 0 then begin 
    SetLength(Result, ACharCount); 
    FillChar(Result[1], PadCount, AChar); 
    Move(AString[1], Result[PadCount + 1], Length(AString)); 
    end else 
    Result := AString; 
end; 

Я не знаю, является ли Delphi 2009, а затем обеспечить эквивалентный двухбайтной Char-обоснованную FillChar, и если они делают, я не знаю, что он называется, поэтому я изменил подпись функции, чтобы явно использовать AnsiString. Если вам нужна WideString или UnicodeString, вам нужно будет найти замену FillChar, которая обрабатывает двухбайтовые символы. (FillChar имеет запутанное имя на Delphi 2009, так как оно не обрабатывает значения полного значения Char.)

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

Answer 2

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

function cwLeftPad(aString:string; aCharCount:integer; aChar:char): string; 
var 
    i,vLength:integer; 
    origSize: integer; 
begin 
    Result := aString; 
    origSize := Length(Result); 
    if aCharCount <= origSize then 
    Exit; 
    SetLength(Result, aCharCount); 
    Move(Result[1], Result[aCharCount-origSize+1], origSize * SizeOf(char)); 
    for i := 1 to aCharCount - origSize do 
    Result[i] := aChar; 
end; 

EDIT: Я сделал некоторые испытания и моя функция медленнее, чем ваш улучшенной cwLeftPad. Но я нашел что-то еще - вам не нужно 5 секунд для выполнения 35k функций cwLeftPad, кроме случаев, когда вы работаете на ПК XT или форматируете гигабайтные строки.

я тестировал с помощью этого простого кода

for i := 1 to 35000 do begin 
    a := 'abcd1234'; 
    b := cwLeftPad(a, 73, '.'); 
end; 

и я получил 255 миллисекунд для исходного cwLeftPad, 8 миллисекунд для вашей улучшенной cwLeftPad и 16 миллисекунд для моей версии.

Answer 3

Возможно, быстрее использовать StringOfChar для выделения совершенно новой строки длины строки и дополнения, а затем использовать перемещение для копирования существующего текста за его спину.
Мое мышление состоит в том, что вы создаете две новые строки выше (одна с FillChar и одна с плюсом).Для этого требуется два выделения памяти и конструкции псевдо-объекта строки. Это будет медленным. Может быть, быстрее отработать несколько циклов процессора, делая избыточное заполнение, чтобы избежать дополнительных операций с памятью.
Это может быть еще быстрее, если вы выделили пространство памяти, а затем FillChar и Move, но дополнительный вызов fn может замедлить это.
Эти вещи часто проходят проб и ошибок!

Answer 4

Вы вызываете StringOfChar каждый раз сейчас. Конечно, этот метод проверяет, есть ли у него что-то делать и выпрыгивает, если длина достаточно мала, но, может быть, вызов StringOfChar требует много времени, потому что внутри он выполняет другой вызов перед выпрыгиванием.

Так что моя первая идея была бы выскочить на себя, если нет ничего, чтобы сделать:

function cwLeftPad(const aString: string; aCharCount: Integer; aChar: Char;): string; 
var 
    l_restLength: Integer; 
begin 
    Result := aString; 
    l_restLength := aCharCount - Length(aString); 
    if (l_restLength < 1) then 
    exit; 

    Result := StringOfChar(aChar, l_restLength) + aString; 
end; 

Answer 5

Еще одна мысль - если это Delphi 2009 или 2010, отключить «формат строки проверки» в проекте, параметры , Компилятор Delphi, Компиляция, Генерация кода.

Answer 6

Вы можете получить значительно лучшую производительность, если предварительно выделите строку.

function cwLeftPadMine 
{$IFDEF VER210} //delphi 2010 
(aString: ansistring; aCharCount: integer; aChar: ansichar): ansistring; 
{$ELSE} 
(aString: string; aCharCount: integer; aChar: char): string; 
{$ENDIF} 
var 
    i,n,padCount: integer; 
begin 
    padCount := aCharCount - Length(aString); 

    if padCount > 0 then begin 
    //go ahead and set Result to what it's final length will be 
    SetLength(Result,aCharCount); 
    //pre-fill with our pad character 
    FillChar(Result[1],aCharCount,aChar); 

    //begin after the padding should stop, and restore the original to the end 
    n := 1; 
    for i := padCount+1 to aCharCount do begin 
     Result[i] := aString[n]; 
    end; 
    end 
    else begin 
    Result := aString; 
    end; 
end; 

А вот шаблон, который полезен для делать сравнения:

procedure TForm1.btnPadTestClick(Sender: TObject); 
const 
    c_EvalCount = 5000; //how many times will we run the test? 
    c_PadHowMany = 1000; //how many characters will we pad 
    c_PadChar = 'x'; //what is our pad character? 
var 
    startTime, endTime, freq: Int64; 
    i: integer; 
    secondsTaken: double; 
    padIt: string; 
begin 
    //store the input locally 
    padIt := edtPadInput.Text; 

    //display the results on the screen for reference 
    //(but we aren't testing performance, yet) 
    edtPadOutput.Text := cwLeftPad(padIt,c_PadHowMany,c_PadChar); 

    //get the frequency interval of the OS timer  
    QueryPerformanceFrequency(freq); 

    //get the time before our test begins 
    QueryPerformanceCounter(startTime); 

    //repeat the test as many times as we like 
    for i := 0 to c_EvalCount - 1 do begin 
    cwLeftPad(padIt,c_PadHowMany,c_PadChar); 
    end; 

    //get the time after the tests are done 
    QueryPerformanceCounter(endTime); 

    //translate internal time to # of seconds and display evals/second 
    secondsTaken := (endTime - startTime)/freq; 
    if secondsTaken > 0 then begin 
    ShowMessage('Eval/sec = ' + FormatFloat('#,###,###,###,##0', 
     (c_EvalCount/secondsTaken))); 
    end 
    else begin 
    ShowMessage('No time has passed'); 
    end; 
end; 

Используя этот эталонный шаблон, я получаю следующие результаты:

The original: 5,000/second 
Your first revision: 2.4 million/second 
My version: 3.9 million/second 
Rob Kennedy's version: 3.9 million/second 

Answer 7

Вы можете ускорить эту процедуру еще больше, используя массив поиска.

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

Так что, если вы знаете (или можете оценить каким-то быстрым способом) диапазон прокладок и штриховых знаков, вы можете построить двумерный массив, который включает эти параметры. Для простоты я предполагаю, что у вас есть 10 различных отступов, и вы заполняете одним символом - «.», Поэтому в примере это будет одномерный массив.

Вы реализуете это так:

type 
    TPaddingArray = array of String; 

var 
    PaddingArray: TPaddingArray; 
    TestString: String; 

function cwLeftPad4(const aString:string; const aCharCount:integer; const aChar:char; var anArray: TPaddingArray): string; 
begin 
    Result := anArray[aCharCount-length(aString)] + aString; 
end; 

begin 
    //fill up the array 
    SetLength(StrArray, 10); 
    PaddingArray[0] := ''; 
    PaddingArray[1] := '.'; 
    PaddingArray[2] := '..'; 
    PaddingArray[3] := '...'; 
    PaddingArray[4] := '....'; 
    PaddingArray[5] := '.....'; 
    PaddingArray[6] := '......'; 
    PaddingArray[7] := '.......'; 
    PaddingArray[8] := '........'; 
    PaddingArray[9] := '.........'; 

    //and you call it.. 
    TestString := cwLeftPad4('Some string', 20, '.', PaddingArray); 
end; 

Ниже приведены результаты тестов:

Time1 - oryginal cwLeftPad   : 27,0043604142394 ms. 
Time2 - your modyfication cwLeftPad : 9,25971967336897 ms. 
Time3 - Rob Kennedy's version  : 7,64538131122457 ms. 
Time4 - cwLeftPad4     : 6,6417059620664 ms. 

Обновленные ориентиры:

Time1 - oryginal cwLeftPad   : 26,8360194218451 ms. 
Time2 - your modyfication cwLeftPad : 9,69653117046119 ms. 
Time3 - Rob Kennedy's version  : 7,71149259179622 ms. 
Time4 - cwLeftPad4     : 6,58248533610693 ms. 
Time5 - JosephStyons's version  : 8,76641780969192 ms. 

вопрос: является ли это стоит хлопот ?; -)