2

我是一个德尔福程序员。在一个程序中，我必须生成具有不同“分支”长度的二维数组。它们非常大，操作需要几秒钟（烦人）。

例如：

var a: array of array of Word;
  i: Integer;

begin
   SetLength(a, 5000000);
   for i := 0 to 4999999 do
      SetLength(a[i], Diff_Values);
end;

我知道命令 SetLength(a, dim1, dim2) 但不适用。甚至没有为 dim2 设置最小值（> 0）并从那里继续，因为 dim2 的最小值为 0（某些“分支”可以为空）。

那么，有没有办法让它快点呢？不仅提高了 5..10%，而且真的很快……

谢谢你。

4

4 回答 4

5

在处理大量数据时，需要做很多工作，这为可以完成的时间量设定了理论上的最小值。

对于 500 万次迭代中的每一次，您需要：

  • 以某种方式确定“分支”的大小
  • 从内存管理器分配一个适当大小的新数组
  • 将新数组使用的所有内存清零（SetLength 会自动为您执行此操作）

第 1 步完全在您的控制之下，并且可能会被优化。但是，如果您使用的是现代版本的 Delphi，则 2 和 3 的速度差不多。（如果您使用的是旧版本，您可能会从安装 FastMM 和 FastCode 中受益，这可以加快这些操作。）

如果合适，您可能会做的另一件事是延迟初始化。与其尝试一次分配所有 500 万个数组，不如先做SetLength(a, 5000000);。然后当你需要到达一个“分支”时，首先检查它的长度是否=0。如果是，它还没有被初始化，所以将它初始化为适当的长度。总体而言，这并没有节省时间，实际上总共会花费更长的时间，但它确实分散了初始化时间，因此用户不会注意到。

如果您的初始化已经尽可能快，并且您的情况是不能在这里使用延迟初始化，那么您基本上就不走运了。这就是处理大量数据的代价。

于 2011-03-29T17:35:41.683 回答
2

我刚刚测试了您的确切代码，使用常数 for Diff_Values，将其GetTickCount()用于基本计时。如果Diff_Values是186它需要 1466 毫秒，如果Diff_Values是187它失败了Out of Memory。你知道，Out of Memory意思是Out of Address Space，不是真的Out of Memory。

在我看来，你分配了这么多数据，你的内存用完了，Windows 开始分页，这就是它很慢的原因。在我的系统上，我有足够的 RAM 供进程根据需要分配；它确实如此，直到它失败。

可能的解决方案

  • 显而易见的一点：不要分配那么多！
  • 找出一种将所有数据分配到一个连续内存块的方法：有助于解决地址空间碎片。类似于如何在“分支”上分配具有固定大小的二维数组，但如果您的“分支”具有不同的大小，则需要根据您的数据计算出不同的数学公式。
  • 查看其他数据结构，可能是那些缓存在磁盘上的数据结构（以打破 2Gb 地址空间限制）。
于 2011-03-29T17:54:19.947 回答
2

除了 Mason 的观点之外，这里还有一些需要考虑的想法：

如果分支长度在分配后从未改变，并且您对将存储在所有分支中的数组中的项目总数有上限，那么您可以通过分配一大块内存来节省一些时间并自己划分该块中的“分支”。您的数组将成为一维指针数组，并且该数组中的每个条目都指向该分支数据的开头。您使用单个指针变量跟踪大块中已用空间的“结束”，当您需要为新的“分支”保留空间时，您将当前的“结束”指针值作为新的开始分支并根据分支所需的空间量增加“结束”指针。大学教师'

这种技术将需要更多地使用指针，但它提供了消除所有堆分配开销的潜力，或者至少用与您的特定使用模式相匹配的专用非常简单、非常快速的子分配器替换通用堆分配。执行起来应该更快，但编写和测试需要更多时间。

此技术还将避免堆碎片并将所有内存的释放减少到单个释放（而不是当前模型中的数百万个单独分配）。

另一个要考虑的提示：如果您总是对每个新分配的数组“分支”做的第一件事是将数据分配到每个插槽中，那么您可以消除 Mason 示例中的第 3 步 - 如果全部都不需要将内存清零您要做的是立即将真实数据分配给它。这会将您的内存写入操作减少一半。

于 2011-03-29T18:04:27.560 回答
1

假设您可以将整个数据结构放入一个连续的内存块中，您可以一次性完成分配，然后接管索引。

注意：即使您无法将数据放入单个连续的内存块中，您仍然可以通过分配多个大块然后将它们拼凑在一起来使用此技术。

首先形成一个辅助数组，colIndex，它包含每行第一列的索引。将长度设置colIndex为RowCount+1。你通过设置colIndex[0] := 0然后构建它colIndex[i+1] := colIndex[i] + ColCount[i]。在一个 for 循环中执行此操作，该循环最多包含RowCount. 因此，在最后一个条目中colIndex[RowCount]，您存储了元素的总数。

现在将 a 的长度设置为colIndex[RowCount]。这可能需要一点时间，但它会比你以前做的更快。

现在您需要编写几个索引器。将它们放入课堂或记录中。

吸气剂看起来像这样：

 function GetItem(row, col: Integer): Word;
 begin
   Result := a[colIndex[row]+col];
 end;

二传手很明显。您可以内联这些访问方法以提高性能。为了方便对象的客户，将它们作为索引属性公开。

您需要添加一些代码来检查 和 的row有效性col。您需要使用colIndex后者。{$IFOPT R+}如果您想模拟本机索引的范围检查，可以将此检查设为可选。

当然，如果您想在初始实例化后更改任何列数，这完全不是入门！

于 2011-03-29T17:45:10.180 回答