除了与Distinct有类似的效果？

Question

我刚刚发现Except()将从第一个列表中删除第二个列表中的所有元素,但它也会使返回结果中的所有元素都不同.

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

任何人都可以向我解释为什么这是行为,如果可能的话,请指出解释这个问题的文档？

Answer 1

该Except功能的文档说明:

通过使用默认的相等比较器来比较值,生成两个序列的集合差异.

两组的设定差异被定义为第一组中未出现在第二组中的成员.

这里的重要词是set,定义为:

...一个抽象的数据结构,可以存储某些值,没有任何特定的顺序,也没有重复的值......

因为它Except被记录为基于集合的操作,所以它还具有使结果值不同的效果.

Answer 2

你写了：

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

执行此操作时，仍然使用secondList.

例如：

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)
{
    return ExceptAll(first, second, null);
}

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 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 的变体）

Answer 3

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

\n

\n
• A.Except(B);[1, 2]格雷格·比奇（Greg Beech）在回应中解释称，回归
\n
• A.ExceptAll(B);来自 Alex Siepman 的回复，返回[1, 2, 2, 3, 3]（我发现这个名字不明确）。
\n
• A.Where(v => !B.Contains(v))来自 OP 解决退货问题[1, 2, 2]
\n

\n

我认为 OP 解决方法是所需的行为，而这个行为尚未得到处理。

\n

OP 解决方案的主要问题是List<T>.Contains(T)及时O(n)（对于大小相等的 A 和 B）和在内存中Where制定O(n)解决方案。O(n\xc2\xb2)O(1)

\n

O(n)我们可以通过使用哈希集在时间和O(n)内存中做到这一点：

\n

// I accept any better name for this method\npublic static IEnumerable<TSource> ExceptFrom<TSource>(\n    IEnumerable<TSource> first,\n    IEnumerable<TSource> second,\n    IEqualityComparer<TSource> comparer)\n{\n    if (first == null)\n        throw new ArgumentNullException(nameof(first));\n\n    if (second == null)\n        throw new ArgumentNullException(nameof(second));\n\n    var secondSet = second as HashSet<TSource> ?? // this trick ignore the comparer\n                    second.ToHashSet(comparer ?? EqualityComparer<TSource>.Default);\n\n    // Contains is O(1) for HashSet.\n    return first.Where(v => !secondSet.Contains(v));\n}\n

\n