在创建3个IEnumerables的并集时，实现O（n）性能的最简单方法是什么？

说a，b，c都是List ，我想创建一个未排序的联合。 虽然性能不是超级关键，但它们每个可能有10,000个条目，所以我很想避免使用O（n ^ 2）解决方案。

AFAICT MSDN文档没有说明关于union的性能特征，就不同类型而言。

我的直觉说，如果我只是做一个。 a.Union(b).Union(c) ，这将需要O（n ^ 2）时间，但是new Hashset(a).Union(b).Union(c)将是O（n）。

有没有人有任何文件或指标来确认或否认这一假设？

Answer 1

您应该使用Enumerable.Union因为它与HashSet方法一样高效。 复杂度为O（n + m），因为：

Enumerable.Union

当枚举此方法返回的对象时， Union e 按该顺序计算第一个和第二个，并产生尚未产生的每个元素。

源代码在这里 。

---

Ivan是对的，如果你使用带有多个集合的Enumerable.Union会有一个开销，因为必须为每个链式调用创建一个新集合。 因此，如果您使用以下方法之一，它可能会更有效（就内存消耗而言）：

1. Concat + Distinct ：

    a.Concat(b).Concat(c)...Concat(x).Distinct() 

2. Union + Concat

    a.Union(b.Concat(c)...Concat(x)) 

3. 采用IEnumerable HashSet构造函数 （fe with int ）：

    new HashSet(a.Concat(b).Concat(c)...Concat(x)) 

前两者之间的差异可以忽略不计。 第三种方法不使用延迟执行，它在内存中创建HashSet<> 。 这是一种优秀而有效的方法1.如果您需要此集合类型或2.如果这是查询的最终操作。 但是如果你需要对这个链式查询进行进一步的操作，你应该更喜欢Concat + Distinct或Union + Concat 。

Answer 2

虽然@Tim Schmelter关于Enumerable.Union方法的线性时间复杂度是正确的，但链接多个Union运算符具有隐藏的开销，每个Union运算符在内部创建一个哈希集，该哈希集基本上复制了前一个运算符（加上其他项）的哈希集，因此与单个HashSet方法相比，使用更多内存。

如果我们考虑到Union只是Concat + Distinct的快捷方式，那么具有与HashSet相同的时间/空间复杂度的可伸缩LINQ解决方案将是：

 a.Concat(b).Concat(c)...Concat(x).Distinct() 

Answer 3

Union是O（n）。

a.Union(b).Union(c)在大多数实现中的效率低于a.Union(b.Concat(c))因为它为第一个union操作创建一个哈希集，然后为另一个a.Union(b.Concat(c))创建另一个哈希集，如同其他答案说。 这两者最终都会使用一系列IEnumerator对象，这会增加成本，因为会增加更多的资源。

a.Union(b).Union(c)在.NET Core中效率更高，因为第二个.Union()操作产生一个知道a ， b和c的单个对象，它将为整个创建一个哈希集操作，以及避免IEnumerator对象链。