在 Delphi 中从 TList 开头删除大块项目的有效方法是什么

Question

从 TList 中删除 (0) 的成本很高，因为所有后续项都需要向下移动。如果我需要从更大列表的开头删除大量项目，最快的方法是什么？

Answer 1

从 TList 开头删除大量元素的成本很高。尽管类名具有欺骗性，但 TList 实际上是一个数组。在 TList 中，没有删除范围的功能 - 每个项目必须单独删除，然后列表的其余部分向下移动。对于较大的范围，这将引发大量的重新分配和完整的列表移动。

如果您有更现代的 Delphi，您可以使用通用列表类 TList并利用 DeleteRange 方法。该文档包含以下重要说明：

这是一个 O(ACount) 操作。

在 Delphi 2006 中，您可以编写具有同等性能特征的代码，如下所示：

procedure DeleteRange(List: TList; AIndex, ACount: Integer);
var
  i: Integer;
  NewCount: Integer;
begin
  NewCount := List.Count-ACount;
  Assert(AIndex>=0);
  Assert(ACount>=0);
  Assert(NewCount>=0);
  for i := AIndex to NewCount-1 do
    List[i] := List[i+ACount]
  List.Count := NewCount;
end;

Answer 2

正如 Marcelo 已经说过的，您可以复制整个块，但您可以使用 TList.List 作为参数，通过一次调用 Move() 来移动整个块，而不是逐项执行该操作。

请注意，TList.List 是一个 PPointerList (^TPointerList; TPointerList = array[0..MaxListSize - 1] of Pointer;)较旧的 Delphi 版本并在 Delphi XE2 中成为 TPointerList (TPointerList = array of Pointer;)，因此您应该使用正确的间接寻址

TList(aList).List^[index] // for older Delphi's

：

TList(aList).List[index]  // for Delphi XE2

Answer 3

由于 TList 是一个指针数组，因此在 XE2 中执行此操作的方法如下。

Delphi 2006 上的实现类似，但我无法编写代码，因为我没有 2006。

// I have 1000000 items, and I want to delete the first 5000
// Copy the pointer array items up the array
CopyMemory(@myList.List[0],
  @myList.List[5000],
  SizeOf(Pointer) * (myList.Count - 5000));
// Reset the count. Delphi cooperates as long as we're shrinking
myList.Count := myList.Count - 5000;
// You now have tons of unused memory at the end, it's fine
// but if you want to clean house
myList.Capacity := myList.Count;

只要指针指向的所有内容都在其他地方进行内存管理，就不会发生泄漏。

这是证明：

type
  TMyObject = class
    index: Integer;
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  myList: TList;
  i: Integer;
  myObject: TMyObject;
begin
  // Create a list with 1000000 entries
  myList := TList.Create;
  for i := 1 to 1000000 do
  begin
    myObject := TMyObject.Create;
    myObject.index := i;
    myList.Add(myObject);
  end;
  // Delete the first 5000
  CopyMemory(@myList.List[0],
    @myList.List[5000],
    SizeOf(Pointer) * (myList.Count - 5000));
  myList.Count := myList.Count - 5000;
  myList.Capacity := myList.Count;
  // Show the new count
  ShowMessage(IntToStr(myList.Count));
  // Shows that my array now has objects 5001 and up
  for i := 0 to 5 do
  begin
    myObject := TMyObject(myList.Items[i]);
    ShowMessage(IntToStr(myObject.index));
  end;
end;

该证明存在严重内存泄漏，但我们创建对象只是为了显示值。

Answer 4

如果顺序很重要，并且您有 N 个项目需要在前面删除：

for I := 0 to List.Count - N - 1 do
    list[I] := list[I + N];
for I := list.Count - 1 downto list.Count - N do
    list.Delete(I)

我还没有很好地思考这段代码，因此您需要检查是否存在差一错误等。

如果顺序不重要，您可以简单地将最后 N 项与前 N 项交换，然后按上述方式删除最后 N 项。

Answer 5

这里有一个想法：如果您知道列表中的所有项目都已分配，则可以将要删除的项目置零，然后只需调用 TList.Pack()，它会找出空位在哪里，并尽可能有效地将其他所有项目移到一边。不过，这需要扫描所有项目，因此它可能不是您想要的，但它也不使用删除（从而阻止 Nitofy 调用）。 Pack 的实现在 D2006 和 XE2 之间没有发生任何变化，因此您可以依赖它的效率。

请注意，要删除要删除的项目，您可以使用 List[aIndex] := nil 但这仍会强制调用 Notify()，因此 List.List[aIndex] ： = nil 可能会更快。

Answer 6

首先，使用 BeginUpdate 和 EndUpdate 来防止通过删除每个项目来更新 TList 的 UI。

第二：尝试先删除列表中最下面的项目。换句话说，从列表中从下到上删除项目对其他项目的效率较低。