0

我的原始代码在这里..

function AddNumStrings(Str1, Str2: string): string;
var
  i: integer;
  carryStr: string;
  worker: integer;
  workerStr: string;
begin
  Result:= inttostr(length(Str1));
  Result:= '';
  carryStr:= '0';

  // make numbers the same length
  while length(Str1) < length(Str2) do Str1:= '0' + Str1;
  while length(Str1) > length(Str2) do Str2:= '0' + Str2;

  i:= 0;
  while i < length(Str1) do begin
    worker:= strtoint(copy(Str1, length(Str1) - i, 1)) + strtoint(copy(Str2, length(Str2) - i, 1)) + strtoint(carryStr);
    if worker > 9 then begin
      workerStr:= inttostr(worker);
      carryStr:= copy(workerStr, 1, 1);
      Result:= copy(workerStr, 2, 1) + Result;
    end else begin
      Result:= inttostr(worker) + Result;
      carryStr:= '0';
    end;

    inc(i);
  end; { while }
  if carryStr <> '0' then Result:= carryStr + Result;
  Application.ProcessMessages;
end;

function yeni(s1, s2: string): string;
var
  j, i, k: integer;
  c: char;
  s: string;
begin
  k:= length(s2);
  j:= length(s1) - length(s2);
  for i:= j downto 1 do begin
    c:= s1[i];
    k:= k + 1;
    if (c <> '9') and (c <> '0') then begin
      s:= copy(s1, i, k);
      s:= AddNumStrings(s, s2);
      Setlength(s1, i - 1);
      Result:= s1 + s;
      break;
    end;

    Application.ProcessMessages;
  end;

  procedure TForm1.Button13Click(Sender: TObject);
  var
    i, k: integer;
    s: Ansistring;
  begin
    s:= '1111';
    for i:= 1 to 1000000 do begin
      for k:= 1 to 120 do begin
        s:= yeni(s, '4');
      end;
    end;
  end;

end.

最后，我的字符串s长度必须为 1,000,000,000。但我想这需要68天。如何加快此代码的速度？

4

3 回答 3

5

您的代码因Shlemiel The Painter's Algorithm的变体而窒息。每次像这样将两个字符串相加时，Delphi RTL 必须增加字符串的大小，这可能涉及分配一个新的、更大的字符串并复制旧字符串，然后释放旧字符串。当你这样做 1000 万次时，所有的内存复制和重新分配都会加起来。

要让它快速运行，您需要做的是预先确定完成的字符串有多长，然后调用SetLength并s从头开始分配您的大字符串。之后，跟踪尚未“填充”的最高字符的索引。您的每个IntToStr调用都会产生一个新字符串；插入|字符，然后复制IntToStr结果，随时更新索引。这应该会大大减少此代码运行所需的时间。

于 2013-10-23T19:29:14.697 回答
3

您正在尝试使用字符串进行任意精度算术。
这是一个坏主意。

请改用 bigint 库。它使用整数数组来完成这项工作。
一个不错的可以在以下位置下载：http: //www.delphiforfun.org/Programs/Library/big_integers.htm

或根据 LURD 的建议：https ://code.google.com/p/gmp-wrapper-for-delphi/

于 2013-10-23T20:24:16.197 回答
1

显然这是一个愚蠢的例子，但你可以做一些事情：

  1. 知道调用 Delphi 函数时会发生什么
  2. 了解您的数据
  3. 将内容移出循环
  4. 不要跳，除非它可以预测

让我详细说明

知道调用 Delphi 函数时会发生什么 当
调用 RTL 函数时，string:= string + someotherstring
Delphi 会执行一个concat操作。这涉及调整字符串分配的大小（如果需要）并将字符串（如果需要）移动到内存中的新位置。
如果您多次执行此操作，所有存储分配将开始累加。事实上，如果您将函数加倍到 20,000,000 次运行，您会发现运行时间增加了一倍以上。
因此，您可以避免这种废话，并将那些昂贵的功能移出循环。

了解您的数据
任何乘法都 将s[index] = 0是 0。您可以使用这些知识来加快速度。有人称之为作弊；在这种情况下，这可能是真的，但在更复杂的情况下，知道您的数据将做什么可以让您获得非常好的加速。
此外，您知道将一位数乘以 9 永远不会产生 > 81 的结果，因此您不需要检查超过 2 个字符。

将东西移出循环
一旦你知道了你的数据，你就可以把东西移出循环，所以你不需要做很多次，你只做一次。
即使循环外的东西比循环内的东西花费的时间长 10,000 倍。这仍然是一个很好的交易。

除非它是可预测的，否则不要跳跃
在这种情况下，这不适用，因为该函数将在输出稳定的零流时迅速稳定下来，但无论如何我将其放入用于演示目的。
事实上，if这里会比没有更快，if因为跳转会破坏依赖链。

代码示例

procedure TForm1.Button4Click(Sender: TObject); 
const
  NumberOfCharsForKToSettleTo0 = 10;
  ManyTimes = 10 * 1000 * 1000 
var
  i,j,k,l:integer;
  s:string;
begin
  //preallocate the length of the string
  SetLength(s, 4 + (ManyTimes * length('|1')) + NumberOfCharsForKToSettleTo0);
  s:='1369';
  l:= 4;
  for i:=1 to ManyTimes do begin
    j:=i mod 9;
    //k:=strtoint(s[Length(s)])*j; don't use strtoint
    k:= ord(s[l]) - ord('0');
    k:= k*j;
    //s:=s+'|'+inttostr(k);
    inc(l);
    s[l]:= '|';
    inc(l);
    s[l]:= chr(k div 10+ord('0'));
    inc(l,integer(k>9));  //avoid jumps/ifs that are hard to predict.
    s[l]:= chr(k+ord('0'));
  end;
end;
于 2013-10-23T19:34:08.167 回答