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

Question

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

delphidelphi-2006tlist

10

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

（注：TList是Delphi编程语言中用于存储对象的类。）

- rossmcm

你确定后续的项目需要下移吗？如果它被实现为链表，那么这是非常便宜的。不过这个评论并不能代替获取问题的有效答案。 - baash05

删除后的项目顺序是否重要？ - Marcelo Cantos

1

@baash05：我相信TList是作为一个数组实现的。 - Marcelo Cantos

4

查看这个问题有更快的TList实现吗？获取一些提示。 - RRUZ

@baash05 TList 存储数据集中记录编号的索引。TList 的顺序决定了 UI 中记录的显示顺序。删除的顺序并不重要。如果 TList 被实现为数组，我可以通过移动并调整计数来完成吗？ - rossmcm

6个回答

4

正如Marcelo所说的那样，你可以复制整个块，但是你可以使用TList.List作为参数，一次调用Move()来移动整个块，而不是逐项操作。

需要注意的是，在旧版本的Delphi中，TList.List是一个PPointerList（^TPointerList; TPointerList = array[0..MaxListSize - 1] of Pointer;），而在Delphi XE2中变成了TPointerList（TPointerList = array of Pointer;），因此你应该使用正确的间接引用：

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

并且

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

- PatrickvL

1

那可能会破坏 TList.Notify，但这可能并不重要。 - David Heffernan

1

即便如此，它可能足够快，以证明额外的复杂性是有价值的。 - afrazier

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;

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

- Marcus Adams

1

我认为拥有自己的TList类，并将上述内容实现为该类的方法会非常不错。 - Warren P

1

这里有一个想法：如果你知道列表中的所有项目都已分配，那么你可以将要删除的项目设置为nil，然后调用TList.Pack()，它会找出空位并尽可能高效地移动其他所有项目。虽然这需要扫描所有项目，所以可能不是你想要的，但它不使用Delete（因此防止了Nitofy调用）。Pack的实现在D2006和XE2之间没有改变，因此你可以依赖它的效率。

请注意，要将要删除的项目设置为nil，你可以使用List[aIndex] := nil，但这仍然会强制进行Notify()调用，因此List.List[aIndex] := nil可能更快。

- PatrickvL

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个项目。

- Marcelo Cantos

删除顺序不重要。您是否可以为TList“SetLength”？-这比调用N次删除更快。 - rossmcm

@ross 是的，你可以这样做。只需执行 List.Count := ... 即可。 - David Heffernan

+1 这是一个很好的答案，但如果使用 List.Count 就更完美了。 - David Heffernan

0

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

其次：尝试从列表中最低的位置开始删除项目。换句话说，从下到上删除项目对其他项目的效率更高。

- Galaxydreams

4

TList没有BeginUpdate或EndUpdate。 - David Heffernan

还有就是没有“TList的UI”；TList不是一个图形组件。而且我不太确定第二段说了什么 - 你能编辑一下你的回答吗？ - Ken White

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Heffernan · Accepted Answer

从一个TList的开头删除大量元素是代价昂贵的。尽管类名可能会让人产生误解，但实际上，TList是一个数组。在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;