arrays - 如何有效地处理数组中的多次插入？

Question

我有一个动态分配的整数数组，我想在其中的任意位置插入整数。许多整数，例如超过 250 万。

我的代码目前如下所示:

type
  TIntegerArr = array of Integer;

var
  FCount: Integer;
  FSortedList: TIntegerArr;

procedure Insert(_Value: Integer; _InsertPos: integer);
var
  OldList: TIntegerArr;
begin
  OldList := FSortedList;
  if Length(FSortedList) < FCount + 1 then begin
    OldList := FSortedList;
    FSortedList := nil;
    SetLength(FSortedList, FCount + 100);
    CopyMemory(@FSortedList[0], @OldList[0], SizeOf(Integer) * _InsertPos);
  end;
  MoveMemory(@FSortedList[_InsertPos + 1], @OldList[_InsertPos], SizeOf(Integer) * (FCount - _InsertPos));
  FSortedList[_InsertPos] := _Value;
  Inc(FCount);
end;

(真正的代码是具有 FSortedList 和 FCount 作为字段的类的方法。)

使用临时列表并使用 Move 而不是 for 循环来移动数据，已经大大提高了性能，因为它可以防止数组在必须增长时被复制两次(一次在现有数组的 SetLength 中，另一次在 SetLength 中)移动的时间)。

但最坏的情况 Insert(SomeValue, 0) 仍然总是移动所有现有值。

到目前为止，我正在考虑在数组的开头引入偏移量，这样每次在前面插入新值时都不必移动所有现有值，只有当偏移量达到时我才可以这样做0. 例如:

// simple case: inserting at Position 0:
if FOffset = 0 then begin
  // [...] reallocate a new array as above
  Move(@FSortedList[100], @OldList, SizeOf(Integer) * _InsertPos);
  FOffset := 100;
end;
Dec(FOffset);
FSortedList[FOffset] := _NewValue;

(此代码未经测试，可能有错误)当然可以扩展以检查插入点是否更接近开头或结尾，并根据情况将第一个或最后一个值移动一个位置，以便平均只需移动 1/4 的条目而不是目前的 1/2。

另一种选择是实现稀疏数组。我记得在 1990 年代的某个商业图书馆中看到过这样的实现，但不记得是哪个(TurboPower？)。

此过程是某些排序和索引代码的核心，这些代码适用于不同大小的数组，从几十个条目到上面提到的数百万个条目。

目前该程序运行了大约 2 小时(在我的优化之前，它接近 5 小时)，并且我已经知道数组中的条目数量将至少增加一倍。由于数组越大，插入性能就越差，我怀疑条目数量增加一倍，运行时间至少会增加四倍。

我想要一些关于如何调整性能的建议。内存消耗目前不是一个大问题，但运行时间绝对是一个问题。

(这是 Delphi 2007，但除非较新的 Delphi 版本已经具有用于执行上述操作的优化库，否则应该不会产生太大差异。Classes.TList 未优化。)

Edit1:刚刚找到了我上面提到的稀疏数组实现:它是 TurboPower SysTools 的 StColl。

Edit2:好的，一些背景知识:我的程序读取当前包含 240 万个条目的 DBase 表，并从这些条目生成几个新表。新表在创建后进行规范化并建立索引(出于性能原因，我在插入数据之前不会生成索引，相信我，我先尝试过。)。该数组是为生成的表提供内部排序的核心代码段。新记录仅追加到表中，但它们的 RecNo 按排序顺序插入到数组中。

Answer 1

查看您的程序后，我立即发现了一些缺陷。为了看到进展，我首先测量了最坏情况下现有程序的速度(始终在 0 位置添加数字)。

n:=500000;
for i:=0 to n-1
 do Insert(i, 0);

测量:n=500000 47.6 毫秒

A) 简单性

我从你的程序中删除了一些不必要的行(OldList完全没有必要，SetLength保留内存)。

改进 A:

procedure Insert(_Value: Integer; _InsertPos: integer);
begin
 if Length(FSortedList) < FCount + 1
    then SetLength(FSortedList, FCount + 100);
  Move(FSortedList[_InsertPos], FSortedList[_InsertPos+1], SizeOf(Integer) * (FCount - _InsertPos));
  FSortedList[_InsertPos] := _Value;
  Inc(FCount);
end;

速度增益6%(44.8 毫秒)

B) 一切都很重要

if Length(FSortedList) < FCount + 1 
   then SetLength(FSortedList, FCount + 100);

• 提示 1:每次插入时都会调用 Length 函数
• 提示2:每次计算FCount+1
• 提示 3:过程参数为 const(通过引用)
• 提示 4:引入 FCapacity 变量
• 提示 5:仅将长度增加 100 将导致大量重新分配(250 万个数组上的 25.000 次)。正如你所说，内存不是问题，那么为什么不预先分配全部或至少大的内存呢？

改进 B:

procedure Insert(const _Value, _InsertPos: integer);
begin
 if FCount = FCapacity
    then begin
     Inc(FCapacity, 100000);
     SetLength(FSortedList, FCapacity);
    end;
 Move(FSortedList[_InsertPos], FSortedList[_InsertPos+1], SizeOf(Integer) * (FCount - _InsertPos));
 FSortedList[_InsertPos] := _Value;
 Inc(FCount);
end;

速度增益1%(44.3 毫秒)。

提示:您可以实现一些渐进算法，而不是 Inc by 100000。

C) 瓶颈

如果我们现在看一下程序，什么都没有剩下，只有大量的内存移动。如果我们不能改变算法，我们就必须改进内存移动。

实际上存在快速移动挑战(fastcode.sourceforge.net)

我准备了一个 zip 文件，其中包含您需要的文件(3 个文件，源代码)。链接>>> http://www.dakte.org/_stackoverflow/files/delphi-fastcode.zip

• 将 fastcodeCPUID.pas 和 fastmove.pas 添加到您的项目中!
• 插入使用 fastmove.pas；
• 瞧!没有其他需要改变的!

我的机器速度提高了近 50%(取决于您使用的 CPU)。

原始程序

n         ms graph
---------------------------------
100000   1.8 *
200000   7.6 ***
300000  17.0 *******
400000  30.1 *************
500000  47.6 ********************

改进，无需快速移动 (-7%)

n         ms graph
---------------------------------
100000   1.6 *
200000   6.9 ***
300000  15.7 ******
400000  28.2 ***********
500000  44.3 ******************

改进，快速移动 (-46%)

n         ms graph
---------------------------------
100000   0.8 *
200000   3.8 **
300000   9.0 ****
400000  16.3 *******
500000  25.7 ***********

最后评论:

 if FCount = FCapacity
    then begin
     if FCapacity<100000
        then FCapacity:=100000  
        else FCapacity:=FCapacity*2;
     SetLength(FSortedList, FCapacity);
    end;

正如我所说，您可以添加一些渐进的 FCapacity 增加。这是一些经典的 Grow 实现(只需根据需要添加更多 if 或将 100000 更改为更合适的值)。

D) 更新 2:数组为 ^TArray

type
  PIntegerArr3 = ^TIntegerArr3y;
  TIntegerArr3y = array[0..1] of Integer;

var
 FCapacity3,
 FCount3: Integer;
 FSortedList3: PIntegerArr3;

procedure ResizeArr3(var aCurrentArr: PIntegerArr3; const aNewCapacity: Integer);
var lNewArr: PIntegerArr3;

begin
 GetMem(lNewArr, aNewCapacity*SizeOf(Integer));

 if FCount3>0 // copy data too
  then begin
    if aNewCapacity<FCount3
       then FCount3:=aNewCapacity; // shrink
    Move(aCurrentArr^[0], lNewArr^[0], FCount3*SizeOf(Integer));
  end;

 FreeMem(aCurrentArr, FCapacity3*SizeOf(Integer));
 FCapacity3:=aNewCapacity;
 aCurrentArr:=lNewArr;
end;

procedure FreeArr3;
begin
 if FCapacity3>0
  then begin
    FreeMem(FSortedList3, FCapacity3*SizeOf(Integer));
    FSortedList3:=nil;
  end;
end;

procedure Insert3(const _Value, _InsertPos: integer);
begin
 if FCount3 = FCapacity3
    then ResizeArr3(FSortedList3, FCapacity3 + 100000);
 Move(FSortedList3^[_InsertPos], FSortedList3^[_InsertPos+1], SizeOf(Integer) * (FCount3 - _InsertPos));
 FSortedList3^[_InsertPos] := _Value;
 Inc(FCount3);
end;

从步骤 C) 获得的速度无!

结论:FastMove或算法改变，已达到内存移动速度的“物理”极限!

我使用的是 Delphi XE3，在 System.pas 中，第 5307 行:

(* ***** BEGIN LICENSE BLOCK *****
 *
 * The assembly function Move is licensed under the CodeGear license terms.
 *
 * The initial developer of the original code is Fastcode
 *
 * Portions created by the initial developer are Copyright (C) 2002-2004
 * the initial developer. All Rights Reserved.
 *
 * Contributor(s): John O'Harrow
 *
 * ***** END LICENSE BLOCK ***** *)

procedure Move(const Source; var Dest; Count: NativeInt);

实际上，Delphi 中已经准备好了一些 Fastcode 例程，但包括那些直接从他们的网站(或从我上面包含的链接)下载的例程，差异最大，几乎 50%(奇怪)。