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

Question

考虑这个测试应用：

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 功能（在 Haskell 中称为 nub）？

Answer 1

使用中间列表：

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;

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

Answer 2

出于性能原因，我建议使用~~排序列表~~字典。

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;

Answer 3

Jens 的解决方案可行，但它的运行时间相当慢，为 O(n²)。

如果您的清单很长，更好的选择是
- 排序列表
- 将每个项目与其后续项目进行比较。

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

查看以下伪代码（现在无法访问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 倍）！

只有当列表很大时，更好的渐近运行字典才会开始。

Answer 4

使用已有的：

uses
  Spring.Collections,
  Spring.collections.Extensions;

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

这支持惰性求值（意味着在处理结果枚举之前不处理输入）。它在内部使用哈希集（目前实现为字典）来跟踪已经找到的项目（这发生在枚举器内部）。

为什么这很重要？因为如果 Input 涉及其他昂贵的操作，那么任何执行完整枚举的操作都可能导致不必要的性能影响，这些操作可能远远超过其他删除重复项的方法（例如将其放入列表并对其进行排序）的任何好处。也不能保证 IEnumerable 是有限的。

如果在调用此函数和枚举结果之间更改了 Input，则该更改会影响您的枚举结果，而如果您不支持惰性求值，则不会出现这种情况。如果您枚举多次，每次的结果可能不同（即最新）。

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

How to remove all duplicates from a list?

delphi

list

unique

spring4d

delphi-xe7