Đệm nhanh của một chuỗi trong Delphi

Question

Tôi đã cố gắng tăng tốc một thói quen nhất định trong một ứng dụng, và hồ sơ của tôi, AQTime, đã xác định một phương pháp đặc biệt là một nút cổ chai. Phương pháp này đã gắn bó với chúng tôi trong nhiều năm qua, và là một phần của một -unit "misc":

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; 

Trong một phần của chương trình mà tôi đang tối ưu hóa tại thời điểm phương pháp này được gọi là ~ 35k lần, và phải mất 56% thời gian thực hiện!

Thật dễ dàng để thấy rằng đó là một cách khủng khiếp sang trái-pad một chuỗi, vì vậy tôi thay thế nó với

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

đó đã cải thiện đáng kể. Tổng thời gian chạy từ 10,2 giây đến 5,4 giây. Tuyệt vời! Nhưng, cwLeftPad vẫn chiếm khoảng 13% tổng thời gian chạy. Có cách nào dễ dàng để tối ưu hóa phương pháp này hơn nữa không?

Answer 1

Chức năng mới của bạn bao gồm ba chuỗi, đầu vào, kết quả từ StringOfChar và kết quả hàm. Một trong số chúng bị phá hủy khi hàm của bạn trả về. Bạn có thể làm điều đó trong hai, không có gì bị phá hủy hoặc tái phân bổ.

1. Phân bổ chuỗi có tổng chiều dài yêu cầu.
2. Điền phần đầu tiên của nó bằng ký tự đệm.
3. Điền phần còn lại của nó bằng chuỗi đầu vào.

Dưới đây là một ví dụ:

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; 

Tôi không biết liệu Delphi năm 2009 và sau đó cung cấp một tương đương hai byte Char dựa trên FillChar, và nếu họ làm, tôi không biết những gì nó được gọi, vì vậy tôi đã thay đổi chữ ký của hàm để sử dụng AnsiString một cách rõ ràng. Nếu bạn cần WideString hoặc UnicodeString, bạn sẽ phải tìm thay thế FillChar xử lý các ký tự hai byte. (FillChar có một cái tên khó hiểu như của Delphi 2009 vì nó không xử lý các giá trị Char đầy đủ kích cỡ.)

Một điều cần xem xét là liệu bạn có thực sự cần gọi hàm đó thường xuyên như vậy ngay từ đầu. Mã nhanh nhất là mã không bao giờ chạy.

Answer 2

StringOfChar rất nhanh và tôi nghi ngờ bạn có thể cải thiện mã này rất nhiều. Tuy nhiên, hãy thử cái này, có thể nó nhanh hơn:

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: Tôi đã làm một số thử nghiệm và chức năng của tôi chậm hơn cwLeftPad cải thiện của bạn. Nhưng tôi tìm thấy một cái gì đó khác - không có cách nào CPU của bạn cần 5 giây để thực hiện 35k cwLeftPad chức năng ngoại trừ nếu bạn đang chạy trên PC XT hoặc định dạng chuỗi gigabyte.

Tôi đã thử nghiệm với mã này đơn giản

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

và tôi đã nhận 255 mili giây cho cwLeftPad ban đầu của bạn, 8 mili giây cho cwLeftPad cải thiện và 16 mili giây cho phiên bản của tôi.

Answer 3

Có thể sử dụng StringOfChar nhanh hơn để phân bổ chuỗi hoàn toàn mới với chiều dài chuỗi và phần đệm và sau đó sử dụng di chuyển để sao chép văn bản hiện có trên mặt sau của chuỗi.
Suy nghĩ của tôi là bạn tạo hai chuỗi mới ở trên (một với FillChar và một với dấu cộng).Điều này đòi hỏi hai bộ nhớ cấp phát và cấu trúc của đối tượng giả chuỗi. Điều này sẽ chậm. Nó có thể nhanh hơn để lãng phí một vài chu kỳ CPU làm một số dư thừa để tránh các hoạt động bộ nhớ bổ sung.
Nó có thể còn nhanh hơn nếu bạn phân bổ không gian bộ nhớ sau đó đã làm một FillChar và một Move, nhưng cuộc gọi fn thêm có thể làm chậm mà xuống.
Những điều này thường là dùng thử và lỗi!

Answer 4

Bạn gọi StringOfChar mọi lúc. Tất nhiên phương pháp này kiểm tra nếu nó có cái gì để làm và nhảy ra nếu chiều dài đủ nhỏ, nhưng có thể cuộc gọi đến StringOfChar là tốn thời gian, bởi vì nội bộ nó thực hiện một cuộc gọi khác trước khi nhảy ra ngoài.

Vì vậy, ý tưởng đầu tiên của tôi sẽ nhảy ra khỏi một mình nếu không có gì để làm là:

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

Một suy nghĩ - nếu điều này là Delphi 2009 hoặc 2010, vô hiệu hóa "Chuỗi định dạng kiểm tra" trong dự án, lựa chọn , Biên dịch Delphi, Biên dịch, Tạo mã.

Answer 6

Bạn có thể nhận được hiệu suất tốt hơn đáng kể nếu bạn phân bổ trước chuỗi.

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; 

Và đây là một mẫu đó là hữu ích cho việc so sánh:

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; 

Sử dụng rằng mẫu chuẩn, tôi nhận được kết quả như sau:

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

Bạn có thể tăng tốc độ thói quen này thậm chí nhiều hơn bằng cách sử dụng mảng tra cứu.

Tất nhiên nó phụ thuộc vào yêu cầu của bạn. Nếu bạn không nhớ lãng phí một số bộ nhớ ... Tôi đoán rằng chức năng này được gọi là 35 k lần nhưng nó không có 35000 độ dài đệm khác nhau và nhiều ký tự khác nhau. Vì vậy, nếu bạn biết (hoặc bạn có thể ước tính một cách nhanh chóng) phạm vi của paddings và các ký tự đệm bạn có thể xây dựng một mảng hai chiều trong đó bao gồm các tham số đó. Vì lợi ích của sự đơn giản, tôi giả định rằng bạn có 10 độ dài đệm khác nhau và bạn đang đệm với một ký tự - '.', Do đó, ví dụ nó sẽ là mảng một chiều.

Bạn thực hiện nó như thế này:

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; 

Dưới đây là kết quả 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. 

chuẩn Cập nhật:

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. 

Câu hỏi đặt ra là: liệu nó có giá trị những rắc rối ?; -)