使用 LINQ 查找对称差集

Question

我有两个集合a和b。 我想计算在a或b中，但不是同时在两者中的项的集合（逻辑异或）。 通过LINQ，我可以得到以下结果：

IEnumerable<T> Delta<T>(IEnumerable<T> a, IEnumerable<T> b)
{
    return a.Except (b).Union (b.Except (a));
}

我想知道是否有其他更有效或更紧凑的方法来生成两个集合之间的差异。

编辑1：Jon Skeet发布了一种不保留项目顺序的解决方案，依赖于HashSet。我想知道是否有其他方法可以在输出中保留a和b的顺序。

- Pierre Arnaud

---

如果a或b包含重复项会怎么样？ - Cameron MacFarland

在我的情况下，a 和 b 不包含重复项，因此这对我来说不是一个问题。 - Pierre Arnaud

Answer 1

直接使用 HashSet<T> - 它有一个 SymmetricExceptWith 方法：

HashSet<T> data = new HashSet<T>(a);
data.SymmetricExceptWith(b);

编辑：如果您想保持顺序，这里有一个替代方案：

HashSet<T> data = new HashSet<T>(a);
data.IntersectWith(b);
foreach (T t in a.Concat(b))
{
    if (!data.Contains(t))
    {
        yield return t;
    }
}

这有以下重要的区别：

• Both a and b are iterated over twice. In some cases that could be a very bad thing - you could call ToList on each of them to start with to retain a buffer.

• If there are duplicates in either a or b, they will be yielded multiple times. If you wanted to avoid this you could keep a set of already-yielded values. At this point, it would be equivalent to:

  a.Concat(b).Except(a.Intersect(b))
  

这样做仍然只需要两个集合操作，而不是你原始代码中的三个。

- Jon Skeet

---

谢谢Jon的快速回复。只要你不关心项目的原始顺序，HashSet就可以很好地工作。如果我想保留a和b中项目的顺序差异怎么办？ - Pierre Arnaud

@Pierre：我已经编辑了我的答案，加入了另外几个选项。 - Jon Skeet

非常感谢您的时间。在我的情况下，a和b不包含重复项，因此这不是一个问题。您提出的LINQ表达式比涉及HashSet的代码片段更易读（因此更易维护）。我喜欢它！ - Pierre Arnaud

Answer 2

假设a.Except(b)和b.Except(a)是不相交的，您可以使用concat代替union，从而节省一个集合运算符（并且concat更有效率）。

return a.Except (b).Concat (b.Except (a));

这仍然会两次遍历每个列表。

- Cameron MacFarland

---

谢谢你，你是对的，“Concat”会比“Union”更快，因为我的输入是不相交的；我忽略了这一点。 - Pierre Arnaud

Answer 3

我们公司的一个项目也有类似的需求，所以我们编写了这个扩展：

public class EnumerablePair<T> : IReadOnlyCollection<T>
{
    private IReadOnlyCollection<T> _Left;
    private IReadOnlyCollection<T> _Right;
    private IEnumerable<T> _Union;
    private int _Count;
    public EnumerablePair(IEnumerable<T> left, IEnumerable<T> right)
    {
        _Left = left?.ToList() ?? Enumerable.Empty<T>().ToList();
        _Right = right?.ToList() ?? Enumerable.Empty<T>().ToList();
        _Count = Left.Count + Right.Count;
        _Union = Left.Union(Right);
    }

    public int Count => _Count;
    public IReadOnlyCollection<T> Left { get => _Left; }
    public IReadOnlyCollection<T> Right { get => _Right; }

    public IEnumerator<T> GetEnumerator()
    {
        return _Union.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _Union.GetEnumerator();
    }
}

public static class EnumerableExtension
{
    public static EnumerablePair<T> ExclusiveDisjunction<T>(this IEnumerable<T> leftOperand, IEnumerable<T> rightOperand, IEqualityComparer<T> comparer = null)
    {
        if (leftOperand == null)
            throw new ArgumentNullException(nameof(leftOperand), $"{nameof(leftOperand)} is null.");
        if (rightOperand == null)
            throw new ArgumentNullException(nameof(rightOperand), $"{nameof(rightOperand)} is null.");

        // TODO : Can be optimized if one of the IEnumerable parameters is empty.

        bool leftIsBigger = leftOperand.Count() > rightOperand.Count();
        var biggestOperand = leftIsBigger ? leftOperand.ToList() : rightOperand.ToList();
        var smallestOperand = leftIsBigger ? rightOperand.ToList() : leftOperand.ToList();

        var except1 = biggestOperand.ToList();
        var except2 = Enumerable.Empty<T>().ToList();

        Func<T, T, bool> areEquals;
        if (comparer != null)
            areEquals = (one, theOther) => comparer.Equals(one, theOther);
        else
            areEquals = (one, theOther) => one?.Equals(theOther) ?? theOther == null;

        foreach (T t in smallestOperand)
            if (except1.RemoveAll(item => areEquals(item, t)) == 0)
                except2.Add(t);

        if (leftIsBigger)
            return new EnumerablePair<T>(except1, except2);
        return new EnumerablePair<T>(except2, except1);
    }
}

它比较两个集合的元素（使用IEqualityComparer或不使用，由您选择）。

• 返回的对象是一个EnumerablePair<T>，其中包含在leftOperand或rightOperand中但不在两者中都有的对象（XOR）。
• EnumerablePair<T>.Left包含在leftOperand中但不在rightOperand中的对象。
• EnumerablePair<T>.Right包含在rightOperand中但不在leftOperand中的对象。

您可以这样使用扩展：

var xorList = list1.ExclusiveDisjunction(list2);
var leftXor = xorList.Left;
var rightXor = xorList.Right;

xorList、leftXor 和 rightXor 都是 IEnumerable<T>。

- Xav987