Quick padding di una stringa in Delphi

Question

Stavo cercando di velocizzare una certa routine in un'applicazione, e il mio profiler, AQTime, ha identificato un metodo in particolare come collo di bottiglia. Il metodo è stato con noi per anni, e fa parte di un -Unità "Varie":

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; 

Nella parte del programma che sto ottimizzando in questo momento il metodo è stato chiamato ~ 35k volte, e ci è voluto un incredibile 56% del tempo di esecuzione!

E 'facile vedere che si tratta di un modo orribile a sinistra-pad una stringa, quindi ho sostituito con

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

che ha dato un notevole impulso. Il tempo totale di esecuzione è passato da 10,2 secondi a 5,4 secondi. Eccezionale! Ma, cwLeftPad rappresenta ancora circa il 13% del tempo totale di esecuzione. C'è un modo semplice per ottimizzare ulteriormente questo metodo?

Answer 1

La nuova funzione comprende tre stringhe, l'input, il risultato da StringOfChar e il risultato della funzione. Uno di questi viene distrutto quando ritorna la tua funzione. Potresti farlo in due, senza che nulla venga distrutto o riallocato.

1. Assegnare una stringa della lunghezza totale richiesta.
2. Riempi la prima parte con il carattere di riempimento.
3. Completa il resto con la stringa di input.

Ecco un esempio:

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; 

Io non so se Delphi 2009 e in seguito fornire un equivalente doppio byte Char a base di fillchar, e se lo fanno, io non so cosa si chiama così ho cambiato la firma della funzione per usare AnsiString in modo esplicito. Se hai bisogno di WideString o UnicodeString, dovrai trovare la sostituzione FillChar che gestisce i caratteri a due byte. (FillChar ha un nome confuso a partire da Delphi 2009 poiché non gestisce i valori Char a grandezza naturale.)

Un'altra cosa da considerare è se è davvero necessario chiamare tale funzione così spesso in primo luogo. Il codice più veloce è il codice che non viene mai eseguito.

Answer 2

StringOfChar è molto veloce e dubito che si possa migliorare molto questo codice. Eppure, provate questo, forse è più veloce:

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: ho fatto alcuni test e la mia funzione è più lento del vostro migliorato cwLeftPad. Ma ho trovato qualcos'altro: non c'è bisogno che la tua CPU abbia bisogno di 5 secondi per eseguire le funzioni di 35k cwLeftPad eccetto se stai lavorando su PC XT o formattando le stringhe di gigabyte.

ho provato con questo semplice codice

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

e ho ottenuto 255 millisecondi per l'originale cwLeftPad, 8 millisecondi per il vostro migliore cwLeftPad e 16 millisecondi per la mia versione.

Answer 3

È possibile che sia più veloce utilizzare StringOfChar per allocare una stringa completamente nuova per la lunghezza di stringa e riempimento e quindi utilizzare sposta per copiare il testo esistente sul retro.
Il mio pensiero è che si creano due nuove stringhe sopra (una con FillChar e una con il segno più).Ciò richiede due allocazioni di memoria e costruzioni dello pseudo-oggetto della stringa. Questo sarà lento. Potrebbe essere più veloce sprecare alcuni cicli della CPU facendo del riempimento ridondante per evitare le operazioni extra di memoria.
Potrebbe essere ancora più veloce se hai allocato lo spazio di memoria, quindi hai fatto un FillChar e un Move, ma la chiamata fn extra potrebbe rallentarlo.
Queste cose sono spesso tentativi ed errori!

Answer 4

Si chiama StringOfChar ogni volta. Ovviamente questo metodo controlla se ha qualcosa da fare e salta fuori se la lunghezza è abbastanza piccola, ma forse la chiamata a StringOfChar richiede molto tempo, perché internamente fa un'altra chiamata prima di saltare fuori.

Quindi la mia prima idea sarebbe quella di saltare fuori da solo se non c'è niente da fare:

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

Un altro pensiero - se questo è Delphi 2009 o 2010, disabilitare "formato di stringa controllo" nel progetto, Opzioni , Compilatore Delphi, compilazione, generazione di codice.

Answer 6

È possibile ottenere prestazioni notevolmente migliori se si preassegna la stringa.

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; 

Ed ecco un modello che è utile per i confronti che fanno:

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; 

utilizzando tale modello di riferimento, ottengo i seguenti risultati:

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

È possibile accelerare questa routine ancora di più utilizzando la matrice di ricerca.

Naturalmente dipende dalle vostre esigenze. Se non ti dispiace sprecare un po 'di memoria ... Immagino che la funzione sia chiamata 35 k volte ma non ha 35000 diverse lunghezze di imbottitura e molti caratteri diversi.

Quindi, se si conosce (o si è in grado di stimare in un modo rapido) l'intervallo di paddings e di padding, è possibile creare un array bidimensionale che includa tali parametri. Per semplicità suppongo che tu abbia 10 diverse lunghezze di padding e che tu stia eseguendo il padding con un carattere - '.', Quindi, ad esempio, sarà un array monodimensionale.

Si implementa così:

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; 

Ecco i risultati dei benchmark:

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. 

benchmark Aggiornato:

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. 

La domanda è: vale la pena il fastidio ?; -)