2

我编写了这个函数来从 TList 后代中删除重复项，现在我想知道这是否会在某些条件下给我带来问题，以及它在性能方面的表现如何。

它似乎适用于对象指针

function TListClass.RemoveDups: integer;
var
  total,i,j:integer;
begin
  total:=0;
  i := 0;
  while i < count do begin
    j := i+1;
    while j < count do begin
      if items[i]=items[j] then begin
       remove(items[j]);
       inc(total);
      end
      else
        inc(j);
    end;
    inc(i);
  end;
  result:=total;
end;

更新： 这工作更快吗？

function TDrawObjectList.RemoveDups: integer;
var
  total,i,j:integer;
  templist:TLIST;
begin
  templist:=TList.Create;
  total:=0;
  i := 0;
  while i < count do
    if templist.IndexOf(items[i])=-1 then begin
      templist.add(i);
      inc(i);
    end else begin
      remove(items[i]);
      inc(total);
    end;
  result:=total;
  templist.Free;
end;

你确实需要另一个列表。

4

2 回答 2

1

只是假设：

接口

如果您在 TInterfaceList 中具有仅在该列表中的接口对象，则可以检查对象的引用计数。只需向后循环列表并删除 refcount > 1 的所有对象。

自定义计数器

如果您可以编辑这些对象，您可以在没有接口的情况下执行相同的操作。当对象被添加到列表时增加一个计数器，当它们被删除时减少它。

当然，这仅在您实际上可以为这些对象添加计数器时才有效，但是您的问题中的界限并不完全清楚，所以我不知道这是否允许。

优点是您不需要寻找其他项目，插入时不需要，删除重复项时不需要。在排序列表中查找重复项可能会更快（如评论中所述），但根本不必搜索甚至会击败最快的查找。

于 2012-10-23T15:11:37.113 回答
1

如前所述，解决方案是 O(N^2)，这使得它在大量项目（1000 秒）上非常慢，但只要计数保持低，它就是最好的选择，因为它简单且易于实施。Where's pre-sorted 和其他解决方案需要更多的代码并且更容易出现实现错误。

这可能是相同的代码以不同的、更紧凑的形式编写的。它遍历列表的所有元素，并为每个元素删除当前元素右侧的重复项。只要在反向循环中完成，删除是安全的。

function TListClass.RemoveDups: Integer;
var
  I, K: Integer;
begin
  Result := 0;
  for I := 0 to Count - 1 do //Compare to everything on the right
  for K := Count - 1 downto I+1 do //Reverse loop allows to Remove items safely
    if Items[K] = Items[I] then
    begin
      Remove(Items[K]);
      Inc(Result);
    end;
end;

如果您真的最终得到 5000 个项目列表，我建议您稍后再进行优化。此外，如上所述，如果您在将项目添加到列表时检查重复项，则可以保存：

  • 检查重复项会及时分发，因此对用户来说不会那么明显
  • 如果发现骗子，你可以希望早点退出
于 2012-10-23T10:11:07.660 回答