delphi - 从列表中删除重复项

Question

我编写这个函数是为了从 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;

您确实需要另一个列表。

Answer 1

如上所述，解决方案是 O(N^2)，这使得它在一大组项目(1000s)上非常慢，但只要计数保持较低，它就是最好的选择，因为它简单且易于实现。哪里是预排序的，其他解决方案需要更多代码并且更容易出现实现错误。

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

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 个，我建议您稍后再进行优化。另外，如上所述，如果您在将项目添加到列表时检查重复项，则可以保存:

• 检查重复项会及时分发，因此用户不会注意到
• 如果发现受骗者，您可以尽早退出