从列表中获取唯一的项

Question

什么是从列表中获取所有不同项的最快/最有效的方法？

我有一个List<string>，其中可能有多个重复项，我只想得到列表中的唯一值。

- domgreen

---

这个问题的标题是误导性的。选择独特的项目意味着从列表中选择只出现一次的项目，而不是选择每个不同的元素仅一次。 对于给定的 ["A", "B", "C", "C", "D", "D"] 列表，独特的项目将返回["A","B"]，而不同的项目将返回 ["A", "B", "C", "D"]。 - Eduardo Pignatelli

@EduardoPignatelli 挺挑剔的，但问题可以重新措辞得更加明确。通常情况下，这个问题的意图是：“给定一个值列表，如何获取其中不重复的值列表？” - Suncat2000

Answer 1

您可以使用Distinct方法返回一个不重复的IEnumerable<T>集合：

var uniqueItems = yourList.Distinct();

如果你需要返回唯一项的序列作为 List<T>，你可以调用 ToList 方法：

var uniqueItemsList = yourList.Distinct().ToList();

- LukeH

---

原帖中想要一个快速高效的方法，但这不是。调用 yourList.Distinct().ToList() 会对可枚举对象进行两次完整迭代，并且还要基于 IEqualityComparer，比 GetHashCode 更慢。 - Noldorin

这比 HashSet<T> 更快/更有效吗？我不这么认为。虽然我不打算给它点踩 :-) - Vinay Sajip

我知道这是旧消息，但它很容易在谷歌上找到，并且你错了（至少从.NET 4开始 - 我没有在旧版本中检查过）。yourList.Distinct().ToList() 只枚举一次，而 new HashSet<T>(yourList).ToList() 则进行两次枚举。HashSet 和 Distinct 的内部 Set 类的实现几乎相同。它们都使用 GetHashCode，并且都使用 IEqualityComparer（因为相等的哈希码通常不能保证相等的对象）。 - reavowed

性能基准测试能否支持或反驳我的说法？你可以通过在Reflector（或其他.NET反编译器）中查看System.Linq.Enumerable.DistinctIterator<T>和System.Linq.Set<T>来验证我的说法，与性能无关。 - reavowed

@IainM：抱歉，你是对的。我误解了你的帖子，并认为它们在速度上是相似的。但我仍然非常感兴趣他们是否真的如此。我怀疑差异仍然存在，尽管自.NET 4.0以来可能已经减少。 - Noldorin

Answer 2

使用HashSet<T>。例如：

var items = "A B A D A C".Split(' ');
var unique_items = new HashSet<string>(items);
foreach (string s in unique_items)
    Console.WriteLine(s);

打印

A
B
D
C

- Vinay Sajip

---

必须同意，其他人解决问题，而你解决原因 :) - Noon Silk

一个 HashSet 不会维护任何顺序，这可能与原帖作者的需求有关系也可能无关。 - LukeH

谢谢大家，我不需要对项目进行排序。这很好用。 - domgreen

Answer 3

你可以使用来自LINQ的Distinct扩展方法，以便帮助去重。

- aku

Answer 4

在.Net 2.0中，我非常确定这个解决方案：

public IEnumerable<T> Distinct<T>(IEnumerable<T> source)
{
     List<T> uniques = new List<T>();
     foreach (T item in source)
     {
         if (!uniques.Contains(item)) uniques.Add(item);
     }
     return uniques;
}

- Murilo Beltrame

---

请使用比List更快的随机访问集合，例如Dictionary或HashSet。因为如果“source”包含许多重复项的100,000个项，则在每个100,000次迭代中，您将扫描大约100,000个项目的列表，这意味着您正在扫描大约100,000 * 100,000个项目。二次时间复杂度可能会变得非常慢。 - Timo

Answer 5

除了LINQ的Distinct扩展方法外，您可以使用一个HashSet<T>对象来初始化您的集合。这很可能比LINQ更有效，因为它使用哈希码（GetHashCode）而不是IEqualityComparer。实际上，如果适用于您的情况，我会直接使用HashSet来存储项目。

- Noldorin

---

一个 HashSet 不会维护任何顺序，这可能对 OP 有影响也可能没有。 - LukeH

@Luke：即使如此，在调用“Distinct”之后排序也没有意义... - Noldorin

@Luke：这个问题要求最快/最有效的解决方案，不需要保持顺序。 - Vinay Sajip

@Noldorin：为什么不呢？Distinct应该/确实按顺序迭代列表（尽管我不确定这是否在任何规范中都得到了保证）。 - LukeH

@Luke：哦，我在考虑索引。而且，尽管这是一个开放性问题，但效率在OP中提到了，而顺序没有提到——如果您想要良好的性能，那么HashSet就是正确的选择。 - Noldorin