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

Question

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

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

我的直觉说,如果我这样做a.Union(b).Union(c),这将花费O(n ^ 2)时间,但new Hashset<t>(a).Union(b).Union(c)将是O(n).

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

Answer 1

您应该使用Enumerable.Union它,因为它与HashSet方法一样有效.复杂度为O(n + m),因为:

Enumerable.Union

当枚举此方法返回的对象时,Union<TSource> 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. HashSet<T>带IEnumerable<T>(fe with int)的构造函数:

   new HashSet<int>(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具有相同时间/空间复杂度的可扩展LINQ解决方案HashSet将是:

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