9

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

4

6 回答 6

9

从 a 的开头删除大量元素TList是昂贵的。虽然类名好骗，但aTList实际上是一个数组。TList没有删除范围的工具——必须单独删除每个项目，然后将列表的其余部分向下移动。对于将引发大量重新分配和完整列表移动的大范围。

如果您有更现代的 Delphi，您可以使用通用列表类TList<T>并利用该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;
于 2011-12-01T22:39:29.270 回答
4

正如 Marcelo 已经说过的，您可以复制整个块，但不是逐项进行，您可以通过调用 Move() 来移动整个块，并将其TList.List用作参数。

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

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

和

TList(aList).List[index]  // for Delphi XE2
于 2011-12-01T22:50:33.920 回答
2

这是您在 XE2 中的操作方法，因为 TList 是一个指针数组。

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;

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

于 2011-12-02T00:24:22.483 回答
1

如果订单很重要，并且前面有 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 项。

于 2011-12-01T22:26:12.550 回答
1

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

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

于 2011-12-02T08:23:04.700 回答
0

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

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

于 2011-12-01T22:18:14.543 回答