6

考虑这个测试应用程序：

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

4 回答 4

12

使用已有的：

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发生更改，则该更改会影响您的枚举结果，而如果您不支持惰性求值，则情况并非如此。如果您要枚举多次，则每次的结果可能都不同（即最新的）。

于 2015-09-03T14:06:41.463 回答
4

Jens 的解决方案会起作用，但它的运行时间相当慢，为 O(n 2 )。

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

快速排序的运行时间为 O(n log n) + O(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 倍）！

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

于 2015-09-03T13:10:43.433 回答
3

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

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;
于 2015-09-03T12:23:30.393 回答
0

使用中间列表：

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;

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

于 2015-09-03T12:01:49.560 回答