Relleno rápido de una cadena en Delphi

Question

Estaba tratando de acelerar cierta rutina en una aplicación, y mi perfilador, AQTime, identificó un método en particular como un cuello de botella. El método ha estado con nosotros durante años, y es parte de un -unit "misceláneos":

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; 

En la parte del programa que estoy optimizando al momento en que el método se llama ~ 35k veces, y ¡requirió un asombroso 56% del tiempo de ejecución!

Es fácil ver que es una manera horrible de la izquierda-pad una cadena, así que lo reemplazó con

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

que dio un impulso significativo. El tiempo de ejecución total pasó de 10,2 segundos a 5,4 segundos. ¡Increíble! Pero, cwLeftPad todavía representa aproximadamente el 13% del tiempo total de ejecución. ¿Hay alguna manera fácil de optimizar este método aún más?

Answer 1

Su nueva función implica tres cadenas, la entrada, el resultado de StringOfChar, y el resultado de la función. Uno de ellos se destruye cuando regresa tu función. Podrías hacerlo en dos, sin que nada sea destruido o reasignado.

1. Asigne una cadena de la longitud total requerida.
2. Llena la primera parte con tu carácter de relleno.
3. Llene el resto con la cadena de entrada.

He aquí un ejemplo:

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; 

No sé si Delphi 2009 y posteriormente se convirtió en un equivalente de doble byte a base de Char de FillChar, y si lo hacen, no sé qué se llama, por lo que he cambiado la firma de la función para utilizar AnsiString de forma explícita. Si necesita WideString o UnicodeString, tendrá que encontrar el reemplazo FillChar que maneja caracteres de dos bytes. (FillChar tiene un nombre confuso a partir de Delphi 2009, ya que no maneja los valores de Char de tamaño completo.)

Otra cosa a considerar es si realmente necesita llamar a esa función tan a menudo en primer lugar. El código más rápido es el código que nunca se ejecuta.

Answer 2

StringOfChar es muy rápido y dudo que pueda mejorar este código mucho. Aún así, intente éste, tal vez es más rápido:

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: Hice algunas pruebas y mi función es más lento que su mejora cwLeftPad. Pero encontré otra cosa: no hay forma de que su CPU necesite 5 segundos para ejecutar las funciones de 35k cwLeftPad, excepto si está ejecutando PC XT o formateando cadenas de gigabytes.

Probé con este simple código

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

y me dieron 255 milisegundos para su cwLeftPad originales, 8 milisegundos para su mejora cwLeftPad y 16 milisegundos para mi versión.

Answer 3

Es posible que sea más rápido usar StringOfChar para asignar una cadena completamente nueva a la longitud de la cadena y el relleno y luego usar mover para copiar el texto existente sobre la parte posterior.
Mi pensamiento es que creas dos cadenas nuevas arriba (una con FillChar y otra con el signo más).Esto requiere dos asignaciones de memoria y construcciones del pseudoobjeto de cadena. Esto será lento. Puede ser más rápido desperdiciar algunos ciclos de CPU realizando un llenado redundante para evitar las operaciones de memoria adicionales.
Puede ser incluso más rápido si se colocan en el espacio de memoria y luego hizo un FillChar y un movimiento, pero la llamada fn adicional puede ralentizar eso.
¡Estas cosas a menudo son de prueba y error!

Answer 4

Llama a StringOfChar cada vez. Por supuesto, este método comprueba si tiene algo que ver y salta si la duración es lo suficientemente pequeña, pero tal vez la llamada a StringOfChar lleva mucho tiempo, porque internamente hace otra llamada antes de saltar.

Así que mi primera idea sería saltar a cabo por mí mismo si no hay nada que hacer:

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

Otro pensamiento - si se trata de Delphi 2009 o 2010, desactivar "formato de cadena comprobación" en el proyecto, Opciones , Delphi Compiler, compilación, generación de código.

Answer 6

Puede obtener un mejor rendimiento dramáticamente si asigna previamente la cadena.

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; 

Y aquí es una plantilla que es útil para las comparaciones que hacen:

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; 

Uso de esa plantilla de referencia, consigo los siguientes resultados:

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

Puede acelerar esta rutina incluso más usando la matriz de búsqueda.

Por supuesto, depende de sus requisitos. Si no te importa perder memoria ... Supongo que la función se llama 35 veces pero no tiene 35000 diferentes longitudes de relleno y muchos caracteres diferentes.

Así que si usted sabe (o que son capaces de estimar de alguna manera rápida) la gama de rellenos y los caracteres de relleno se puede construir una matriz de dos dimensiones que incluyen esos parámetros. En aras de la simplicidad, supongo que tiene 10 diferentes longitudes de relleno y está rellenando con un carácter - '.', Por lo que en el ejemplo será una matriz unidimensional.

se implementa de esta manera:

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; 

Aquí están los resultados de referencia:

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. 

puntos de referencia Actualizado:

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 pregunta es: ¿vale la pena la molestia ?; -)