从列表中删除重复项的最有效方法

Question

假设我有一个包含重复值的列表，并且我想要删除这些重复项。

List<int> myList = new List<int>(Enumerable.Range(0, 10000));

// adding a few duplicates here
myList.Add(1); 
myList.Add(2);
myList.Add(3);

我已经找到了三种解决方法：

List<int> result1 = new HashSet<int>(myList).ToList(); //3700 ticks
List<int> result2 = myList.Distinct().ToList(); //4700 ticks
List<int> result3 = myList.GroupBy(x => x).Select(grp => grp.First()).ToList(); //18800 ticks
//referring to pinturic's comment:
List<int> result4 = new SortedSet<int>(myList).ToList(); //18000 ticks

在大多数stackoverflow上的答案中，Distinct方法被展示为“正确的方法”，但是HashSet始终更快！

我的问题是：当我使用HashSet方法时，是否有任何需要注意的事项？还有其他更有效的方法吗？

- fubo

Answer 1

这两种方法之间存在很大的区别：

List<int> Result1 = new HashSet<int>(myList).ToList(); //3700 ticks
List<int> Result2 = myList.Distinct().ToList(); //4700 ticks

第一个方法可以（有可能）改变返回的List<>元素的顺序：Result1元素不会按照myList的顺序排列。第二个方法保持原始排序。

也许没有比第一个方法更快的方法。

也许没有比第二个方法更“正确”的方法（基于排序的某种定义）。

（第三个方法与第二个方法类似，只是更慢。）

出于好奇，Distinct()是：

// Reference source http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,712
public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source) {
    if (source == null) throw Error.ArgumentNull("source");
    return DistinctIterator<TSource>(source, null);
}

// Reference source http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,722
static IEnumerable<TSource> DistinctIterator<TSource>(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer) {
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource element in source)
        if (set.Add(element)) yield return element;
}

最终，Distinct() 方法会使用内部实现的 HashSet<>（名为 Set<>）来检查项目的唯一性。

为了完整起见，我将添加一个链接到问题Does C# Distinct() method keep original ordering of sequence intact?

- xanatos

---

谢谢您确认我的假设。在“正确”的意义上，我指的是被认可的答案。 - fubo

最终一切取决于你是否想保持有序。 - xanatos

@fubo Distinct 使用 IEqualityComparer<>，而 HashSet<> 也使用相同的。 - xanatos

@pinturic - SortedSet 方法在我的基准测试中需要大约 18000 个时钟周期，和第三种方法一样慢。 - fubo

-1 Distinct() 返回一个无序集合。具体实现保留顺序的事实是巧合的 - 你是否已经检查它在所有的Mono/Unity/Xamarin/XBox CLRs上都能正常工作？ - BlueRaja - Danny Pflughoeft