Delphi中字符串的快速填充

Question

Delphi中字符串的快速填充

14

我试图加速应用程序中的某个例程，而我的性能分析工具 AQTime 确认了其中一个方法是瓶颈。这个方法已经跟我们在一起多年了，是“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;

目前我正在优化的程序部分中，这个方法被调用了约35,000次，占用了惊人的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％。是否有更简单的方法进一步优化这个方法？

- Svein Bringsli

你有没有关于每个RTL函数在你的函数中所占用时间的数据？比如说，分配内存所占百分比和字符复制所占百分比各是多少？ - Rob Kennedy

你是在使用D2009或更高版本吗？也就是说，你是在使用string=ansistring还是unicode字符串？ - PhiS

这个函数的典型输入是什么？如果你有一组有限的真实世界输入，那么算法可以被调整成一种可能对于一般情况来说更慢但对于你来说更快的方式。Wodzu有一个极端的例子。 - JosephStyons

通常，长度在5-15个字符的字符串会被填充到20-50个字符。 - Svein Bringsli

填充字符每次都不同吗？是一个填充字符还是多个，例如：'.'，'0'，'#'。 - Wodzu

主要是空格和零，但它会有所变化。不管怎样，现在它已经足够快了。它只占总运行时间的2％，所以我会把时间花在其他地方 :-) - Svein Bringsli

9个回答

6

另一个想法 - 如果这是Delphi 2009或2010，则在项目，选项，Delphi编译器，编译，代码生成中禁用“字符串格式检查”。

- gabr

4

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;

编辑：我进行了一些测试，发现我的函数比你改进后的cwLeftPad要慢。但是我还发现了一些问题 - 除非你在运行PC XT或格式化千兆字符串，否则你的CPU不可能需要5秒来执行35k cwLeftPad函数。

我使用了这段简单的代码进行测试：

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

针对您的原始cwLeftPad函数，我得到了255毫秒的执行时间，而您改进后的cwLeftPad函数只需要8毫秒，而我的版本则需要16毫秒。

- gabr

总运行时间为5.4秒。字符串填充函数占了其中的13%。虽然这只有0.7秒，但如果你看到0.008，仍然相当高。 - Rob Kennedy

可能8ms是所有cwLeftPad调用在执行时间内累积的时间。 - Runner

8毫秒是35,000个字符串赋值（来自常量 - 我认为非常快）和35,000个cwLeftPad调用。 - gabr

gabr，我在做一个小测试项目时也遇到了和你一样的问题。字符串甚至被填充到更短的长度（25个字符），这使得两种方法更加相等。我开始相信分析器在跟我开玩笑。有一件事可能会澄清事情，那就是问题中的数字来自调试版本，在该版本中，我习惯性地关闭代码生成优化。当我重复测试并开启优化时，旧方法占用总运行时间的约20％，而新版本仅占总时间的略微超过2％。 - Svein Bringsli

sveinbringsli：大警告！不要信任 AQTime 进行微优化。请参见：https://dev59.com/q3RC5IYBdhLWcg3wVvYt - lkessler

2

现在每次都调用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;

- Sebastian P.R. Gingter

你可以通过在 System 单元中的 StringOfChar 程序副本上使用内联指令来避免调用开销。或者，如果你懂一点汇编语言，你可以直接将汇编代码插入到 cwLeftPad 函数中，而不需要 PUSH 和 POP 语句的开销。 - lkessler

2

你可以使用查找数组来进一步加快此例程的速度。

当然，这取决于你的要求。如果你不介意浪费一些内存......我想该函数被调用了35k次，但它没有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.

问题是：这值得费心吗？;-)

- Wodzu

如果我想用零而不是点来填充呢？ :-) - Svein Bringsli

正如我在答案中所说，如果您知道要填充哪个字符，您可以为其构建特定的数组。您需要更详细的示例来允许多个字符吗？ :) - Wodzu

1

你是对的，我道歉。我没有好好阅读你的介绍，只看了代码。但是，无论如何，你为什么还要在函数中留下aChar参数呢？ :-) - Svein Bringsli

啊！谢谢@sveinbringsli，我没注意到 :) - Wodzu

仅供参考：实际上，这不是线程安全的函数和方法。所以我投票支持Rob的答案，即使这种方法可能是安全的。提高1毫秒的速度并不重要。此外，缺乏任何输入参数检查和对数组的不安全访问。 - Dima Zorin

谢谢您的评论。当我发布这个答案时，我很难记得。我认为你的一些观点是正确的。通过声明一个常量PaddingArray，可以轻松地获得线程安全性。至于1ms，我认为它可能有意义，特别是对于35k次运行，它将节省3.5秒的时间。当然，如果我的基准测试没有缺陷。我不记得我是如何测量这些时间的，我应该把基准测试代码公开发布。 - Wodzu

1

这是我的解决方案。我使用StringOfChar而不是FillChar，因为它可以处理Unicode字符串/字符：

function PadLeft(const Str: string; Ch: Char; Count: Integer): string;
begin
  if Length(Str) < Count then
  begin
    Result := StringOfChar(Ch, Count);
    Move(Str[1], Result[Count - Length(Str) + 1], Length(Str) * SizeOf(Char));
  end
  else Result := Str;
end;

function PadRight(const Str: string; Ch: Char; Count: Integer): string;
begin
  if Length(Str) < Count then
  begin
    Result := StringOfChar(Ch, Count);
    Move(Str[1], Result[1], Length(Str) * SizeOf(Char));
  end
  else Result := Str;
end;

- timidwolf25

1

如果您预先分配字符串，可以获得显着更好的性能。

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

- JosephStyons

是的，我现在做的就是这样。非常类似于Rob的答案（当我看到你的答案时，我已经接受了他的答案）。 - Svein Bringsli

@JosephStyons 相比哪个版本有显著的提升？请看我的基准测试。 - Wodzu

@Wodzu，与他最初的帖子相比，这是一个巨大的改进。像你在示例中所做的那样预缓存结果无疑会更快...就像你所说的那样，“值得吗”。 - JosephStyons

1

使用StringOfChar分配一个与字符串和填充长度相同的全新字符串，然后使用move将现有文本复制到其后面可能会更快。
我的想法是在上面创建两个新字符串（一个使用FillChar，另一个使用加号）。这需要两个内存分配和字符串伪对象的构造。这将很慢。为了避免额外的内存操作，做一些冗余填充可能会更快一些。
如果您分配了内存空间，然后进行FillChar和Move，可能会更快，但额外的函数调用可能会减慢速度。
这些事情通常是试错的！

- sinibar

没有“额外的函数调用”；StringOfChar 无论如何都会调用 FillChar。 - Rob Kennedy

1

很好！所以SetLength()，Fillchar(左侧)，Move(右侧)应该更快。说实话，我已经有几年没有编写Delphi程序了，我完全不记得StringOfChar函数了。我现在注意到初始字符串是按值传递的。如果我没记错（也许不是这样），在Delphi中这意味着它被克隆了。把它作为引用传递可能值得一试。编码标准人员可能会因此想要打死你，但这应该会更快。 - sinibar

@sinibar - 按引用传递：是的，aString 应该作为 const 传递。否则会有不必要的引用计数管理（但没有克隆）。 - Uli Gerhardt

0

如果你将原始字符串的长度存储在一个变量中，它会更快一些：

function PadLeft(const Str: string; Ch: Char; Count: Integer): string;
var
  Len: Integer;
begin
  Len := Length(Str);
  if Len < Count then
  begin
    Result := StringOfChar(Ch, Count);
    Move(Str[1], Result[Count - Len + 1], Len * SizeOf(Char));
  end
  else Result := Str;
end;

function PadRight(const Str: string; Ch: Char; Count: Integer): string;
var
  Len: Integer;
begin
  Len := Length(Str);
  if Len < Count then
  begin
    Result := StringOfChar(Ch, Count);
    Move(Str[1], Result[1], Len * SizeOf(Char));
  end
  else Result := Str;
end;

- timidwolf25

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob Kennedy · Accepted Answer

你的新函数包含三个字符串，输入、StringOfChar 的结果和函数结果。其中一个在函数返回时被销毁了。您可以使用两个字符串来完成此操作，而不会销毁或重新分配任何内容。

分配总所需长度的字符串。
用填充字符填充其第一部分。
用输入字符串填充其余部分。

以下是示例：

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及以后是否提供了基于双字节字符的FillChar函数，如果提供了，我也不知道它被称为什么名字。因此，我已经更改了函数签名，明确使用AnsiString。如果您需要WideString或UnicodeString，则必须找到能处理两个字节字符的FillChar替代函数。（由于Delphi 2009之后的FillChar不能处理完整的Char值，所以FillChar名称有些混淆。）

另一个需要考虑的问题是是否真的需要那么频繁地调用该函数。最快的代码是从未运行的代码。