代码之家 › 专栏 › 技术社区 › Jens Mühlenhoff

如何从列表中删除所有重复项?

spring4d delphi-xe7 unique delphi list

Jens Mühlenhoff · 技术社区 · 9 年前

考虑此测试应用程序:

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
begin
  // How to implement this function?
end;

var
  Enumerable: IEnumerable<Integer>;
  UniqueEnumerable: IEnumerable<Integer>;
begin
  Enumerable := TCollections.CreateList<Integer>([1, 1, 2, 3, 3, 3, 4]);
  UniqueEnumerable := RemoveDuplicates(Enumerable);
  UniqueEnumerable.ForEach(
    procedure(const I: Integer)
    begin
      WriteLn(I);
    end);
  ReadLn;
end.

我如何实施 RemoveDuplicates 函数(这称为 nub 在Haskell)?

4 回复 | 直到 9 年前

Stefan Glienke 9 年前

使用现有内容:

uses
  Spring.Collections,
  Spring.collections.Extensions;

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
begin
  Result := TDistinctIterator<Integer>.Create(Input, nil);
end;

这支持惰性求值(意味着在处理生成的可枚举对象之前,不会处理Input)。它在内部使用哈希集(当前实现为Dictionary)来跟踪已经找到的项(这发生在枚举器内部)。

为什么这很重要?因为如果发生以下情况,任何执行完整枚举的操作都可能会导致不必要的性能影响 Input 这涉及到其他昂贵的操作,而这些操作可能远远超过其他删除重复项的方法(如将其放入列表并排序)的任何好处。此外,IEnumerable也不能保证是有限的。

如果在调用此函数和枚举结果之间 输入 已更改,该更改会影响枚举的结果,而如果您不支持惰性求值,则不会发生这种情况。如果您枚举了多次,则每次的结果可能不同(即最新)。

Johan 9 年前

Jens的解决方案是可行的,但它的运行时间相当慢,即O(n ^2. ).

如果你有一个长长的清单,一个更好的选择是
-对列表排序
-将每个项目与其后续项目进行比较。

快速排序的运行时间为O(n log n)+搜索的运行时间O(n logn)。

请参见以下内容伪代码(现在无法访问Delphi)。

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
var
  List: IList<Integer>;
  i: integer;
begin
  List := TCollections.CreateList<Integer>;
  List.Assign(Input); //Copy input list to output.
  List.Sort;
  for i:= List.Count-1 downto 1 do begin
    if List[i] = List[i-1] then List.delete(i); 
    //if Comparer<T>.Equals(List[i], List[i-1]) then ....
  end; {for i}
end;

问题
这种方法的问题是输出的顺序可能与输入的顺序不同。这可能是问题,也可能不是问题。

好处(或为什么字典很烂)
如果分类是一种廉价的操作,这将是最快的方法。
字典的使用为哈希带来了很高的恒定成本。
尽管哈希运算是O(1),但对于大密钥来说,它可能会非常昂贵,因为哈希将始终处理整个密钥,而一旦检测到差异,排序比较就会停止。进一步注意,哈希运算比简单的比较要昂贵得多(大约慢30倍到100倍)!

只有当列表庞大时,格言的渐进运行时间才会更好。

Wosi 9 年前

出于性能原因,我建议使用 ~~已排序列表~~ 词典

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
var
  Dictionary: IDictionary<integer, integer>;
  Item: integer;
begin
  Dictionary := TCollections.CreateDictionary<integer,integer>;
  for Item in Input do
    Dictionary.AddOrSetValue(Item, 0);     

  Result := Dictionary.Keys;
end;

Jens Mühlenhoff 9 年前

使用中间列表:

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
var
  List: IList<Integer>;
begin
  List := TCollections.CreateList<Integer>;
  Input.ForEach(
    procedure(const I: Integer)
    begin
      if not List.Contains(I) then
        List.Add(I);
    end);
  Result := List;
end;

这显然不是最佳的解决方案,请参阅其他答案以获得更好的替代方案。