在Delphi中初始化数组的更快方法

Question

我试图在我的Delphi应用程序中挤压每一点性能,现在我开始使用一个与动态数组一起工作的程序.最慢的一行是

SetLength(结果,Len);

用于初始化动态数组.当我查看SetLength过程的代码时,我发现它远非最佳.呼叫顺序如下:

_DynArraySetLength - > DynArraySetLength

DynArraySetLength获取数组长度(初始化为零),然后使用ReallocMem,这对于启动也是不必要的.

我一直在做SetLength来初始化动态数组.也许我错过了什么？有更快的方法吗？

编辑:描述主算法将占用大量空间,实际上是不必要的,因为它试图优化它的一小部分.一般而言,它是车辆路径问题的证明(http://en.wikipedia.org/wiki/Vehicle_routing_problem).我确实需要数以万计的分配,因为我必须保留所有数据,并将其分开保存.Probalby如果我能想到一些聪明的数据结构会有所帮助,但我能想到的任何东西都会大大增加代码的复杂性.基本上我已经在算法级别上做了我所能做的一切,所以现在我正试图从低级别的东西中获得我能做的一切.所以这是一个相当狭隘的问题:是否有可能增加这个特定的电话.我认为要做到这一点,我需要根据SetLength代码编写自己的初始化函数.并使其内联.

Answer 1

这是一个更多的评论,但由于在评论中发布大量代码并不漂亮,我在此处发布.

有时,如果您不知道最终会有多少元素,那么编写这样的代码可能很诱人:

var
  Arr: array of cardinal;

procedure AddElement(const NewElement: cardinal);
begin
  SetLength(Arr, length(Arr) + 1);
  Arr[high(Arr)] := NewElement;
end;

这非常糟糕,因为每次添加新元素时都需要重新分配内存.更好的方法(如果可能)是找到元素数量的上限,例如MAX_ELEMENTS = 100000; 然后最初设置长度:

SetLength(Arr, MAX_ELEMENTS);

然后你创建一个变量

var
  ActualNumberOfElements: cardinal = 0;

和写

procedure AddElement(const NewElement: cardinal);
begin
  Arr[ActualNumberOfElements] := NewElement;
  inc(ActualNumberOfElements);
end;

完成填充数组后,只需截断它:

SetLength(Arr, ActualNumberOfElements);

Answer 2

麦克斯写道：

我对一个执行一次 SetLength( Result, Len ) 的函数进行了无数次调用。

检查一下你如何使用你的函数：你真的需要对这个分配函数进行无数次不同的调用吗？你能像弗朗索瓦建议的那样，重新设计你的代码以减少调用次数吗？

如果您确实需要对函数进行无数次不同的调用，并且需要加快速度，我认为您将需要保留动态数组并使用不同的结构。

但在这样做之前，并进入彻底的调试地狱之前，我会强烈加入 Francois 的建议，并尝试重新设计代码。

也许您可以告诉我们更多有关您的算法的信息？是关于处理图形 3D 结构吗？

[编辑] 好吧，如果是为了解决 NP 完全问题，我会尽量避免分配。

大多数时候，您可以为数组/堆栈/结构的大小给出上限 - 例如：#cities、#vehicles + #drivers、#roads * #cities ...

对于这些部分，我建议分配一次尽可能大的数组，并手动处理仅使用前 n 行等的事实。

考虑到之后可以节省的计算时间，甚至以 n^2 或 n^3 的形式分配结构也是可以接受的。

优化 SetLength ：您的建议是有道理的。

然而，如果动态数组非常适合编写 Delphi 代码 - 主要是因为它们的“自动构造函数”语义 - 恕我直言，它们不太适合高性能计算 - 它严重依赖 RTTI，引用计数现在可以给你带来惊喜然后...
您建议的是动态数组语义的更改。尝试看看“更改数据类型”的解决方案是否真的无法编写和调试。