使用Linq确定一个序列是否包含另一个序列的所有元素

Question

给定两组值：

var subset = new[] { 2, 4, 6, 8 };

var superset = new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

如何确定 superset 是否包含所有 subset 元素？

我想到了这个方法：

superset.Intersect(subset).Count() == subset.Count()

这是最合乎逻辑和高效的方法吗？

- Bryan Watts

Answer 1

怎么样，不是任何一个？

bool contained = !subset.Except(superset).Any();

- David B

---

+1 Any() 的效率比 Count() 要高得多。 - JaredPar

比计数好多了。如果我没记错的话，这也会在找到第一个不匹配项时停止。 - configurator

Answer 2

所以，我的另一个答案很容易使用。但它是O(n*m)的解决方案。

这里有一个稍微不那么友好的O(n+m)解决方案。如果超集非常大，则应使用此解决方案。它避免了反复枚举超集。

HashSet<int> hashSet = new HashSet<int>(superset);
bool contained = subset.All(i => hashSet.Contains(i));

- David B

---

为什么在另一个解决方案中会重复枚举超集？https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,899 - user1121956

@user1121956，我之前做了不同的权衡，但你提供的链接表明我错了。 - Amy B

有趣的是，.net core版本基于HashSet<T>，因此您在此答案中提供的解决方案实际上类似于HashSet<T>的IsSuperSetOf实现。有兴趣的人可以比较Hashset<T>的IsSuperSetOf和IsSubsetOf的性能。 https://source.dot.net/#System.Linq/System/Linq/Except.cs,e289e6c98881b2b8,references https://source.dot.net/#System.Private.CoreLib/HashSet.cs,02e583c455a1c955,references https://source.dot.net/#System.Private.CoreLib/HashSet.cs,bb79d6d73e1765e7,references - user1121956

Answer 3

我有一个扩展方法，它使用现有的Contains()方法。我觉得这比使用Instersect()或Except()更直观。

public static bool ContainsAll<T>(this IEnumerable<T> source, IEnumerable<T> values)
{
    return values.All(value => source.Contains(value));
}

- Anders

---

这将潜在地为每个“value”处理“source”的所有值，这可能非常昂贵。 “Except”解决方案仅处理每个源和目标值一次，从而使其成为更高效的解决方案。 - Bryan Watts

从语义上讲，它们是相等的：对于相同的输入，它们将产生相同的输出。然而，Except 的 LINQ 实现会迭代源序列一次，存储值（我认为是作为哈希集合），然后迭代目标序列一次，从集合中删除其项。LINQ 高度优化以实现最小迭代。 - Bryan Watts

LINQ通常会针对最小迭代进行优化，即使是带有lambda表达式的方法，例如OrderBy。现在，在这些lambda表达式中执行的操作可能非常低效，但这取决于你自己 :-) 我喜欢你的可读性；我正在考虑添加你的扩展方法与Except实现，以获得两全其美的效果。 - Bryan Watts

最佳方案：public static bool ContainsAll<T>(this IEnumerable<T> haystack, IEnumerable<T> needles) { return !needles.Except(haystack).Any(); } - Felix Alcala

如果集合长度不同，此ContainsAll方法应被称为“ContainsEvery”，它将返回false。 - superlogical

Answer 4

你可以使用 Except，如果结果计数为0，则表示操作成功。

请在 MSDN 上查看参数的详细信息。

示例：

subset.Except(superset).Count() == 0

- leppie

---

使用!Any()比Count() == 0更有效率。Count()将遍历整个可枚举对象，而Any()只会查找第一个元素。 - JaredPar