有没有办法检查那个列表是否是另一个列表的子集？
具体来说，我有以下内容：
List<double> t1 = new List<double> { 1, 3, 5 };
List<double> t2 = new List<double> { 1, 5 };
10个回答
284
bool isSubset = !t2.Except(t1).Any();
- Cameron MacFarland
5
1我已经创建了扩展方法http://geekswithblogs.net/mnf/archive/2011/05/13/issubsetof-list-extension.aspx。 - Michael Freidgeim
@Bul Ikana 这段代码的工作原理很简单，如果没有提供IEqualityComparer，则扩展方法内部调用重写对象类方法的Equals和GetHashCode。 - Mrinal Kamboj
2如果列表的长度分别为n和m，那么这个算法的时间复杂度是多少？ - Colonel Panic
3如果把这句话简化为一个名为ContainsAll的linq方法就好了。 - Sebastian Patten
我想知道使用交集是否更快 -
t1.Intersect(t2).Count() == t2.Count() - Scott Baker71
如果处理集合，请使用 HashSet 代替 List。然后，您可以简单地使用 IsSubsetOf()
HashSet<double> t1 = new HashSet<double>{1,3,5};
HashSet<double> t2 = new HashSet<double>{1,5};
bool isSubset = t2.IsSubsetOf(t1);
很遗憾它没有使用LINQ。 :-(
如果您需要使用列表，则@Jared的解决方案可以使用，但需要注意的是您需要删除任何存在的重复元素。
- tvanfosson
4
4没问题。如果你需要进行集合操作，请使用专门设计用于此目的的类。Cameron 的解决方案很有创意，但不如 HashSet 那么清晰易懂/表达明确。 - technophile
2我不同意，因为问题明确要求“使用LINQ”。 - JaredPar
11那又怎样？向别人展示正确的道路不是比他们想要走的路更好吗？ - Jonathan Allen
列表维护其顺序，但集合不会。如果顺序很重要，这将导致不正确的结果。 - StayOnTarget
22
这个解决方案比其他发布在这里的方案都要高效得多，尤其是顶部的解决方案：
bool isSubset = t2.All(elem => t1.Contains(elem));
如果您能在t2中找到一个单独的元素不在t1中，那么您就知道t2不是t1的子集。这种方法的优点是它在原地完成，不需要分配额外的空间，与使用.Except或.Intersect的解决方案不同。此外，当它找到违反子集条件的单个元素时，该解决方案能够立即中断，而其他解决方案则继续搜索。以下是最优长版的解决方案，在我的测试中只比上述速记解决方案略快。
bool isSubset = true;
foreach (var element in t2) {
if (!t1.Contains(element)) {
isSubset = false;
break;
}
}
我对所有解决方案进行了一些基本的性能分析，结果非常显著。这两个解决方案比使用.Except()和.Intersect()方法快大约100倍，并且不使用额外的内存。
- user2325458
8
2这正是
!t2.Except(t1).Any() 所做的。Linq 是从后往前工作的。Any() 会询问一个 IEnumerable 是否至少有一个元素。在这种情况下，t2.Except(t1) 只会发出 t2 中第一个不在 t1 中的元素。如果 t2 的第一个元素不在 t1 中，则它会最快完成，如果 t2 的所有元素都在 t1 中，则它运行时间最长。 - abto1在进行某种基准测试时，我发现当你取
t1={1,2,3,...9999}和t2={9999,9998,99997...9000}时，你会得到以下测量结果：!t2.Except(t1).Any(): 1ms -> t2.All(e => t1.Contains(e)): 702ms。而且随着范围的增大，情况会变得更糟。 - abto3这不是 Linq 的工作方式。
t2.Except(t1) 返回的是 IEnumerable 而不是 Collection。只有当你完全遍历它才会发出所有可能的项，例如通过 ToArray() 或 ToList()，或者在内部不中断使用 foreach。搜索“linq deferred execution”以了解更多关于该概念的信息。 - abto1我完全了解Linq中延迟执行的工作原理。你可以尽情地推迟执行，但是当你想确定t2是否是t1的子集时，你需要遍历整个列表才能弄清楚。这是无法避免的事实。 - user2325458
3让我们以你的评论为例。
t2={1,2,3,4,5,6,7,8} t1={2,4,6,8} t2.Except(t1) => t2 的第一个元素是 1 => 1 与 t1 的差异为 1（与 {2,4,6,8} 匹配）=> Except() 返回第一个元素 1 => Any() 获得一个元素 => Any() 结果为 true => 不再检查 t2 中的其他元素。 - abto显示剩余3条评论
13
如果你正在进行单元测试，你也可以利用 CollectionAssert.IsSubsetOf 方法：
CollectionAssert.IsSubsetOf(subset, superset);
在上述情况中，这意味着：
CollectionAssert.IsSubsetOf(t2, t1);
- Géza
8
我花了一些时间使用BenchmarkDotNet对此答案中的3个可行解决方案进行基准测试。
!t2.Except(t1).Any()调用 Except().Any()t2.IsSubsetOf(t1)调用 HashSett2.All(elem => t1.Contains(elem))调用 All(=>Contains)
我变化了3个参数：
- 超集的数量
- 子集的长度
- 项目的可变性
所有超集都是随机长度，并包含范围内的项[0; Variability)。子集具有固定长度，并包含范围在[0; Variability)之间的项。
胜利者是 All(=>Contains) 方法 - 它有时比使用 HashSets 快30倍，比Except().Any() 快50倍。
代码可以在Github上找到。
更新如评论中@Gert Arnold所述，我的基准测试中有一个错误。我在每次迭代中调用了ToHashSet()。因此，我还建立了一个预先构建的哈希集合集合，并添加了一个名为prebuilt HashSet的纯哈希集测试。它不是绝对的赢家，有时会输给All(=>Contains)算法。我觉得这一点在超集中的可变性（和重复项）上。当值的可变性低时 - 哈希集合获胜，因为它从数据中删除了它。
最终表格如下：
| Method | SupersetsInIteration | SubsetLength | Variability | Mean | Error | StdDev | Median |
|------------------- |--------------------- |------------- |------------ |--------------:|-------------:|-------------:|--------------:|
| Except().Any() | 1000 | 10 | 100 | 1,485.89 μs | 7.363 μs | 6.887 μs | 1,488.36 μs |
| ToHashSet() | 1000 | 10 | 100 | 1,015.59 μs | 5.099 μs | 4.770 μs | 1,015.43 μs |
| prebuilt HashSet | 1000 | 10 | 100 | 38.76 μs | 0.065 μs | 0.054 μs | 38.78 μs |
| All(=>Contains) | 1000 | 10 | 100 | 105.46 μs | 0.320 μs | 0.267 μs | 105.38 μs |
| Except().Any() | 1000 | 10 | 10000 | 1,912.17 μs | 38.180 μs | 87.725 μs | 1,890.72 μs |
| ToHashSet() | 1000 | 10 | 10000 | 1,038.70 μs | 20.028 μs | 40.459 μs | 1,019.35 μs |
| prebuilt HashSet | 1000 | 10 | 10000 | 28.22 μs | 0.165 μs | 0.155 μs | 28.24 μs |
| All(=>Contains) | 1000 | 10 | 10000 | 81.47 μs | 0.117 μs | 0.109 μs | 81.45 μs |
| Except().Any() | 1000 | 50 | 100 | 4,888.22 μs | 81.268 μs | 76.019 μs | 4,854.42 μs |
| ToHashSet() | 1000 | 50 | 100 | 4,323.23 μs | 21.424 μs | 18.992 μs | 4,315.16 μs |
| prebuilt HashSet | 1000 | 50 | 100 | 186.53 μs | 1.257 μs | 1.176 μs | 186.35 μs |
| All(=>Contains) | 1000 | 50 | 100 | 1,173.37 μs | 2.667 μs | 2.227 μs | 1,173.08 μs |
| Except().Any() | 1000 | 50 | 10000 | 7,148.22 μs | 20.545 μs | 19.218 μs | 7,138.22 μs |
| ToHashSet() | 1000 | 50 | 10000 | 4,576.69 μs | 20.955 μs | 17.499 μs | 4,574.34 μs |
| prebuilt HashSet | 1000 | 50 | 10000 | 33.87 μs | 0.160 μs | 0.142 μs | 33.85 μs |
| All(=>Contains) | 1000 | 50 | 10000 | 131.34 μs | 0.569 μs | 0.475 μs | 131.24 μs |
| Except().Any() | 10000 | 10 | 100 | 14,798.42 μs | 120.423 μs | 112.643 μs | 14,775.43 μs |
| ToHashSet() | 10000 | 10 | 100 | 10,263.52 μs | 64.082 μs | 59.942 μs | 10,265.58 μs |
| prebuilt HashSet | 10000 | 10 | 100 | 1,241.19 μs | 4.248 μs | 3.973 μs | 1,241.75 μs |
| All(=>Contains) | 10000 | 10 | 100 | 1,058.41 μs | 6.766 μs | 6.329 μs | 1,059.22 μs |
| Except().Any() | 10000 | 10 | 10000 | 16,318.65 μs | 97.878 μs | 91.555 μs | 16,310.02 μs |
| ToHashSet() | 10000 | 10 | 10000 | 10,393.23 μs | 68.236 μs | 63.828 μs | 10,386.27 μs |
| prebuilt HashSet | 10000 | 10 | 10000 | 1,087.21 μs | 2.812 μs | 2.631 μs | 1,085.89 μs |
| All(=>Contains) | 10000 | 10 | 10000 | 847.88 μs | 1.536 μs | 1.436 μs | 847.34 μs |
| Except().Any() | 10000 | 50 | 100 | 48,257.76 μs | 232.573 μs | 181.578 μs | 48,236.31 μs |
| ToHashSet() | 10000 | 50 | 100 | 43,938.46 μs | 994.200 μs | 2,687.877 μs | 42,877.97 μs |
| prebuilt HashSet | 10000 | 50 | 100 | 4,634.98 μs | 16.757 μs | 15.675 μs | 4,643.17 μs |
| All(=>Contains) | 10000 | 50 | 100 | 10,256.62 μs | 26.440 μs | 24.732 μs | 10,243.34 μs |
| Except().Any() | 10000 | 50 | 10000 | 73,192.15 μs | 479.584 μs | 425.139 μs | 73,077.26 μs |
| ToHashSet() | 10000 | 50 | 10000 | 45,880.72 μs | 141.497 μs | 125.433 μs | 45,860.50 μs |
| prebuilt HashSet | 10000 | 50 | 10000 | 1,620.61 μs | 3.507 μs | 3.280 μs | 1,620.52 μs |
| All(=>Contains) | 10000 | 50 | 10000 | 1,460.01 μs | 1.819 μs | 1.702 μs | 1,459.49 μs |
| Except().Any() | 100000 | 10 | 100 | 149,047.91 μs | 1,696.388 μs | 1,586.803 μs | 149,063.20 μs |
| ToHashSet() | 100000 | 10 | 100 | 100,657.74 μs | 150.890 μs | 117.805 μs | 100,654.39 μs |
| prebuilt HashSet | 100000 | 10 | 100 | 12,753.33 μs | 17.257 μs | 15.298 μs | 12,749.85 μs |
| All(=>Contains) | 100000 | 10 | 100 | 11,238.79 μs | 54.228 μs | 50.725 μs | 11,247.03 μs |
| Except().Any() | 100000 | 10 | 10000 | 163,277.55 μs | 1,096.107 μs | 1,025.299 μs | 163,556.98 μs |
| ToHashSet() | 100000 | 10 | 10000 | 99,927.78 μs | 403.811 μs | 337.201 μs | 99,812.12 μs |
| prebuilt HashSet | 100000 | 10 | 10000 | 11,671.99 μs | 6.753 μs | 5.986 μs | 11,672.28 μs |
| All(=>Contains) | 100000 | 10 | 10000 | 8,217.51 μs | 67.959 μs | 56.749 μs | 8,225.85 μs |
| Except().Any() | 100000 | 50 | 100 | 493,925.76 μs | 2,169.048 μs | 1,922.805 μs | 493,386.70 μs |
| ToHashSet() | 100000 | 50 | 100 | 432,214.15 μs | 1,261.673 μs | 1,180.169 μs | 431,624.50 μs |
| prebuilt HashSet | 100000 | 50 | 100 | 49,593.29 μs | 75.300 μs | 66.751 μs | 49,598.45 μs |
| All(=>Contains) | 100000 | 50 | 100 | 98,662.71 μs | 119.057 μs | 111.366 μs | 98,656.00 μs |
| Except().Any() | 100000 | 50 | 10000 | 733,526.81 μs | 8,728.516 μs | 8,164.659 μs | 733,455.20 μs |
| ToHashSet() | 100000 | 50 | 10000 | 460,166.27 μs | 7,227.011 μs | 6,760.150 μs | 457,359.70 μs |
| prebuilt HashSet | 100000 | 50 | 10000 | 17,443.96 μs | 10.839 μs | 9.608 μs | 17,443.40 μs |
| All(=>Contains) | 100000 | 50 | 10000 | 14,222.31 μs | 47.090 μs | 44.048 μs | 14,217.94 μs |
- zetroot
2
比较并不公平。您在测量的代码中包含了
ToHashSet()。如果您创建哈希集并仅比较 IsSubsetOf，结果会大不相同。毫无疑问，HashSet 将轻松获胜。 - Gert Arnold好的，谢谢！我会在全局设置中重新运行准备好的哈希集测试。我已将其包含在基准代码中，因为我们通常不在常规业务代码中使用此特定数据结构，但我会检查一下。 - zetroot
6
@Cameron将其解决方案作为扩展方法：
public static bool IsSubsetOf<T>(this IEnumerable<T> a, IEnumerable<T> b)
{
return !a.Except(b).Any();
}
使用方法：
bool isSubset = t2.IsSubsetOf(t1);
这与@Michael博客上发布的类似，但不完全相同。
- Neil
1
在@Cameron和@Neil的回答基础上，我编写了一个扩展方法，使用与Enumerable类相同的术语。
/// <summary>
/// Determines whether a sequence contains the specified elements by using the default equality comparer.
/// </summary>
/// <typeparam name="TSource">The type of the elements of source.</typeparam>
/// <param name="source">A sequence in which to locate the values.</param>
/// <param name="values">The values to locate in the sequence.</param>
/// <returns>true if the source sequence contains elements that have the specified values; otherwise, false.</returns>
public static bool ContainsAll<TSource>(this IEnumerable<TSource> source, IEnumerable<TSource> values)
{
return !values.Except(source).Any();
}
- sclarke81
0
假设我们有两个数组，array1和array2，我们想要检查所有array1的值是否存在于array2中：
array1.All(ar1 => array2.Any(ar2 => ar2.Equals(ar1)));
注意：如果相等性可以用其他方式描述，则可以替换
ar2.Equals(ar1)。- Valdas Zaramba
-1
在这里，我们检查子列表（即
t2）中是否存在任何未包含在父列表（即t1）中的元素。如果不存在这样的元素，则该列表是另一个列表的子集。
例如：bool isSubset = !(t2.Any(x => !t1.Contains(x)));
- Lucifer
1
“not Any not”与普通的“All”相同。 - jeromej
-1
试试这个
static bool IsSubSet<A>(A[] set, A[] toCheck) {
return set.Length == (toCheck.Intersect(set)).Count();
}
这里的想法是Intersect只会返回两个数组中都存在的值。此时，如果结果集的长度与原始集合相同，则“set”中的所有元素也在“check”中，因此“set”是“toCheck”的子集。
注意：如果“set”中有重复项，则我的解决方案无法正常工作。我不想窃取其他人的票数，所以不会更改它。
提示：我投了Cameron的答案。
- JaredPar
2
4如果第二个“集合”包含重复元素，则此方法仅适用于它们确实是集合，但不适用于列表。您可能希望使用HashSet<double>以确保它具有集合的语义。 - tvanfosson
只有当两个数组都包含彼此不包含的元素时，程序才不起作用。 - da_berni
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接