嵌套与链式联合

Question

从逻辑上讲，以下都是相同的：

var foo = (  A.Union(B).Union(C).Union(D)  ).ToList();
var bar = (  A.Union(B.Union(C.Union(D)))  ).ToList();
var baz = (  D.Union(C.Union(B.Union(A)))  ).ToList();

它们的末尾应该 return 完全相同的列表。

它们之间有什么区别（如果有的话）？

我猜想唯一的区别是与性能相关的问题，即您多久迭代一次每个集合？然后 foo 和 baz 具有完全相同的性能 - 迭代 A 4 次，但只迭代 D 一次？

对吗？

是否有任何其他有趣的属性可能会导致您关心做一个而不是另一个？

Answer 1

None 这些解决方案多次迭代其参数。此外，参数按照它们在文本中给出的顺序迭代，即 A、B、C、D for foo 和 [=17] =]，D，C，B，A baz。

您可以使用一个简单的生成器来演示这一点，该生成器会在您迭代时 returns 打印项目：

class VisibleIterator : IEnumerable<string> {
    private readonly string name;
    public VisibleIterator(string name) {
        this.name = name;
    }
    public IEnumerator<string> GetEnumerator() {
        for (var i = 0 ; i != 4 ; i++) {
            var res = name+i;
            Console.WriteLine(res);
            yield return res;
        }
    }
    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}

Demo.

集合没有被多次枚举的原因是 UnionIterator<T>，Union<T> 后面的代码，保留了一个已经访问过的项目的哈希集：

static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) {
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource element in first)
        if (set.Add(element)) yield return element;
    foreach (TSource element in second)
        if (set.Add(element)) yield return element;
}

UnionIterator<T>里面Set<TSource> set的大小可能会导致性能上的小差异。在您的每个示例中都会有三个这样的集合 - 每个 Union 调用一个。 Top-level set 总是以 Union 结果的所有成员结束。不过，中间 set 可能包含更多或更少的项目，具体取决于您组合集合的顺序以及每个集合中项目的相对数量。

Answer 2

虽然 dasblinkenlight 是正确的，每个项目都恰好迭代一次，但这三个版本可能仍然存在可衡量的性能差异，具体取决于您的对象。

这些项目将被插入到不同数量的哈希集中，具体取决于它们在联合树中的位置。

虽然名义上插入 Hashset 是 O(1)，但它确实有成本，而且在实践中它并不总是不变的，具体取决于您的对象的详细信息。

当一个项目被插入到哈希集中时，GetHashCode 被调用，并且需要使用 Equals 将项目与集合中具有相同 int 哈希码的任何其他对象进行比较。对于极其复杂的对象，GetHashCode 可能很昂贵。如果item hashkeys没有广泛分布，那么可能会调用Equals，这可能会很昂贵。

以下演示基于@dasblinkenlight 的回答显示 GetHashCode 被调用的次数不同，具体取决于 Union 顺序。我没有演示 Equals 在哈希冲突的情况下被调用，但如果你愿意，你可以尝试一下。

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

public class Test {
    public static void Main() {
            var A = new VisibleIterator("A");
            var B = new VisibleIterator("B");
            var C = new VisibleIterator("C");
            var D = new VisibleIterator("D");
            Console.WriteLine("--- A.Union(B).Union(C).Union(D)");
            var foo = (A.Union(B).Union(C).Union(D)).ToList();
            Console.WriteLine("--- A.Union(B.Union(C.Union(D)))");
            var bar = (A.Union(B.Union(C.Union(D)))).ToList();
            Console.WriteLine("--- D.Union(C.Union(B.Union(A)))");
            var baz = (D.Union(C.Union(B.Union(A)))).ToList();
    }
}

    class VisibleIterator : IEnumerable<VisibleHasher> {
        private readonly string name;
        public VisibleIterator(string name) {
            this.name = name;
        }
        public IEnumerator<VisibleHasher> GetEnumerator() {
            for (var i = 0 ; i != 4 ; i++) {
                var res = name+i;
                Console.WriteLine("Iterating " + res);
                yield return new VisibleHasher(res);
            }
        }
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
    }

    class VisibleHasher {
        private readonly string val;

        public VisibleHasher(String val) {
            this.val = val;
        }

        public override int GetHashCode() {
            Console.WriteLine("Hashing '" + val + "'");
            return val.GetHashCode();
        }
    }

Demo（基于 dasblinkenlight 的回答）

替代方法

如果您认为这些哈希插入的成本可能很高，那么以下应保证每个项目一次哈希插入：

A.Concat(B).Concat(C).Concat(D).Distinct().ToList()

嵌套与链式联合

Nested vs. Chained Unions

linq

performance

ienumerable

替代方法