除了具有类似于Distinct的效果吗？

Question

我刚刚发现Except()会从第一个列表中删除所有在第二个列表中的元素，但它也使返回结果中的所有元素变得独特。

我使用的简单方法是Where(v => !secondList.Contains(v))

有人可以解释一下这种行为的原因，并如果可能的话，指导我去哪里查找相关文档吗？

- Stephan

Answer 1

Except函数的文档说明如下：

使用默认的相等比较器来比较值，生成两个序列的差集。

两个集合的差集被定义为第一个集合中不在第二个集合中出现的成员。

这里重要的是集合（set）一词，其定义如下：

...可以存储某些值的抽象数据结构，没有特定顺序，且没有重复值...

因为Except被文档描述为基于集合的操作，因此它还具有使结果值不同的效果。

- Greg Beech

---

好的，这样就更有意义了。我已经很久没有学过集合数学了。谢谢。 - Stephan

@Stephan - 虽然我必须说，这个文档记录的行为对我来说感觉有些奇怪，因为 IEnumerable<T> 是一个序列而不是一个集合，所以将一个通用的扩展方法用于序列并具有集合语义有些奇怪。但话又说回来，我想从 IEnumerable<T> 中拥有一个具有序列语义的 Except 方法和从 ISet<T> 中拥有一个具有集合语义的 Except 方法甚至更糟糕，因为 ISet<T> 继承自 IEnumerable<T>，因此语义将取决于编译器如何绑定扩展方法。 - Greg Beech

@Greg，Mono似乎在这个问题上出现了错误（这实际上是我通过StackOverflow发现的第二个Mono Enumerable bug）。它会返回第一个元素出现的次数。我的问题是，如果这是一个集合差异，为什么文档显示Enumerable.Except保留第一个元素的顺序（它还说它返回“一个序列”）？集合不保留顺序。Enumerable.Except是否有保证呢？ - Matthew Flaschen

@Matthew - 我猜对于文档中的小序列，顺序可能会被保留，因为集合通常采用混合方法实现，使用列表来处理小容量，并在容量增长时转换为桶实现，以在两种情况下都提供良好的性能。但我认为这只是一个实现细节，而不是一个契约，我不会依赖Except的输出按任何特定顺序排列，因为文档没有说明它会按顺序排列，并且暗示它不会这样做。 - Greg Beech

我同意这感觉很奇怪，这让我有点困惑。在IEnumerable上调用“Except”，我错误地以为它只会枚举并删除第二个列表中匹配的值。我没有真正预料到它会改变可枚举对象的目的，变成一个集合。 - Stephan

Answer 2

你写到：

我正在使用的简单方法是 Where(v => !secondList.Contains(v))

当你这样做时，仍然会使用 secondList 进行 Distinct。

例如：

var firstStrings = new [] { "1", null, null, null, "3", "3" };
var secondStrings = new [] { "1", "1", "1", null, null, "4" };
var resultStrings = firstStrings.Where(v => !secondStrings.Contains(v)); // 3, 3  

我创建了一个扩展方法，使得不需要去重。使用示例：

var result2Strings = firstStrings.ExceptAll(secondStrings).ToList(); // null, 3, 3

这是它的功能：

这是源代码：

public static IEnumerable<TSource> ExceptAll<TSource>(
    this IEnumerable<TSource> first,
    IEnumerable<TSource> second)
{
    // Do not call reuse the overload method because that is a slower imlementation
    if (first == null) { throw new ArgumentNullException("first"); }
    if (second == null) { throw new ArgumentNullException("second"); }

    var secondList = second.ToList();
    return first.Where(s => !secondList.Remove(s));
}

public static IEnumerable<TSource> ExceptAll<TSource>(
    this IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource> comparer)
{
    if (first == null) { throw new ArgumentNullException("first"); }
    if (second == null) { throw new ArgumentNullException("second"); }
    var comparerUsed = comparer ?? EqualityComparer<TSource>.Default;

    var secondList = second.ToList();
    foreach (var item in first)
    {
        if (secondList.Contains(item, comparerUsed))
        {
            secondList.Remove(item);
        }
        else
        {
            yield return item;
        }
    }
}

编辑：根据DigEmAll的评论，有更快的实现方式

public static IEnumerable<TSource> ExceptAll<TSource>(
    this IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource> comparer = null)
{
    if (first == null) { throw new ArgumentNullException(nameof(first)); }
    if (second == null) { throw new ArgumentNullException(nameof(second)); }


    var secondCounts = new Dictionary<TSource, int>(comparer ?? EqualityComparer<TSource>.Default);
    int count;
    int nullCount = 0;
        
    // Count the values from second
    foreach (var item in second)
    {
        if (item == null)
        {
            nullCount++;
        }
        else
        {
            if (secondCounts.TryGetValue(item, out count))
            {
                secondCounts[item] = count + 1;
            }
            else
            {
                secondCounts.Add(item, 1);
            } 
        }
    }

    // Yield the values from first
    foreach (var item in first)
    {
        if (item == null)
        {
            nullCount--;
            if (nullCount < 0)
            {
                yield return item;
            } 
        }
        else
        {
            if (secondCounts.TryGetValue(item, out count))
            {
                if (count == 0)
                {
                    secondCounts.Remove(item);
                    yield return item;
                }
                else
                {
                    secondCounts[item] = count - 1;
                }
            }
            else
            {
                yield return item;
            }
        }
    }
}

更多信息请参见我的博客（还有Intersect和Union的变体）

- Alex Siepman

---

这是一种非常低效的选择，因为在列表中搜索每个项目非常昂贵，而从列表中删除项目也是如此。 "Distinct"语言使用HashSet，因此效率要高得多。 您可以轻松修改其实现以在不降低效率的情况下产生源中重复的元素。 - Servy

我同意@Servy的观点，Contains和Remove都是O(n)操作，并且你正在循环中执行它们。 - Magnus

@Servy: 对于他（指Alex）特殊的Except实现，他不能使用哈希集合，因为这样会消除第二个列表中的重复项。不过仍然有可能大大提高复杂度，例如通过构建一个字典，记录每个项目的出现次数，并减少其出现次数而不是从列表中删除该项目... - digEmAll

@AlexSiepman 这不是 OP 中描述的功能。所描述的功能是从源中删除存在于第二个序列中的所有项，但不执行使源中所有剩余项都不同的附加操作。无论如何，问题并不要求提供替代实现，而是要求解释 Except 方法的作用及原因。简而言之，您正在回答与所问无关的问题。 - Servy

@digEmAll 再次感谢您的评论。我根据您的建议再次更改了代码。我没有使用专用值来替换空值，因为很难找到通用的专用值。例如：可空枚举。我只是添加了一个 nullcounter。现在代码很长，需要分割以提高可读性。但这将在我将其用于生产时进行。 - Alex Siepman

Answer 3

给定 A = [1, 2, 2, 3, 3, 3] 和 B = [3]。

• A.Except(B); 返回 [1, 2]，正如 Greg Beech 在 他的回答 中所解释的。
• A.ExceptAll(B); 来自 Alex Siepman 的回答，返回 [1, 2, 2, 3, 3]（我认为名称不够清晰）。
• A.Where(v => !B.Contains(v)) 是 OP 的解决方法，返回 [1, 2, 2]

我认为 OP 的解决方法是期望的行为，并且这个还没有得到处理。

OP工作方式的主要问题在于List<T>.Contains(T)是O(n)，而Where也是O(n)，使得解决方案在时间上为O(n²)（对于等效大小的A和B），而在内存上为O(1)。我们可以通过使用哈希集将其优化为O(n)时间复杂度和O(n)空间复杂度：

// I accept any better name for this method
public static IEnumerable<TSource> ExceptFrom<TSource>(
    IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource> comparer)
{
    if (first == null)
        throw new ArgumentNullException(nameof(first));

    if (second == null)
        throw new ArgumentNullException(nameof(second));

    var secondSet = second as HashSet<TSource> ?? // this trick ignore the comparer
                    second.ToHashSet(comparer ?? EqualityComparer<TSource>.Default);

    // Contains is O(1) for HashSet.
    return first.Where(v => !secondSet.Contains(v));
}

- Orace