检查一个数组是否是另一个数组的子集

对于如何检查该列表是否是另一个列表的子集，有什么想法吗？

具体来说，我有

List<double> t1 = new List<double> { 1, 3, 5 };
List<double> t2 = new List<double> { 1, 5 };

如何使用 LINQ 检查 t2是否是 t1的子集？

58849 次浏览
小开

试试这个

static bool IsSubSet<A>(A[] set, A[] toCheck) {
return set.Length == (toCheck.Intersect(set)).Count();
}

这里的想法是 Intersect 只返回两个数组中的值。此时，如果结果集的长度与原始集相同，那么“ set”中的所有元素也都在“ check”中，因此“ set”是“ toCheck”的子集

注意: 如果“ set”有重复的内容，我的解决方案就不起作用。我不会因为不想窃取别人的选票而改变它。

提示: 我投票支持卡梅伦的回答。

小开

如果使用集合，请使用 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 的解决方案将使用一个警告，即您需要删除存在的任何重复元素。

小开
最佳答案 
bool isSubset = !t2.Except(t1).Any();
小开

@ Cameron 的扩展方案:

public static bool IsSubsetOf<T>(this IEnumerable<T> a, IEnumerable<T> b)
{
return !a.Except(b).Any();
}

用法:

bool isSubset = t2.IsSubsetOf(t1);

(这是相似的，但不完全相同的一个发布在@Michael 的博客)

小开

如果你是 单元测试，你也可以使用 CollectionAssert.IsSubsetOf方法:

CollectionAssert.IsSubsetOf(subset, superset);

在上述情况下，这意味着:

CollectionAssert.IsSubsetOf(t2, t1);
小开

这是一个比这里提到的其他解决方案更有效率的解决方案，特别是最好的解决方案:

bool isSubset = t2.All(elem => t1.Contains(elem));

如果你能在 t2中找到一个不在 t1中的元素，那么你就知道 t2不是 t1的子集。这种方法的优点是，它完全就地完成，而不需要分配额外的空间，这与使用。除非。互联系统。此外，这个解决方案能够在发现违反子集条件的单个元素时立即中断，而其他元素继续搜索。下面是解决方案的最佳长格式，在我的测试中，它只比上面的速记解决方案稍微快一点。

bool isSubset = true;
foreach (var element in t2) {
if (!t1.Contains(element)) {
isSubset = false;
break;
}
}

我对所有解决方案做了一些基本的性能分析，结果非常惊人。这两个解决方案比。除了()和。Intersect ()解决方案，不使用额外的内存。

小开

在@Cameron 和@Neil 的回答的基础上，我编写了一个扩展方法，它使用了与枚举类相同的术语。

/// <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();
}
小开

在这里，我们检查子列表(即 t2)中是否存在父列表(即 t1)所不包含的元素。如果没有这样的存在，那么这个列表是另一个的子集

eg:

bool isSubset = !(t2.Any(x => !t1.Contains(x)));
小开

我花了一些时间用 BenchmarkDotNet 对这个问题的3个工作解决方案进行了基准测试。

  • !t2.Except(t1).Any()被称为除()。任何()
  • t2.IsSubsetOf(t1)叫做 HashSet
  • 称为 All (= > Contains0)的 t2.All(elem => t1.Contains(elem))

我有三种不同的方法:

  • 超集计数
  • 子集长度子集长度
  • 项目的可变性

所有超集均为随机长度，包含范围为 [0; Variability)的项目。子集具有固定的长度，并且包含范围为 [0; Variability)的项目。

获胜者是 All (= > Contains)方法——它有时比使用 HashSet 快30倍，比 Excel ()快50倍。任何()。

代码可以在 Github上找到

更新 正如@Gert Arnold 在评论中提到的，我的基准测试中有一个 bug，我在每次迭代中都调用 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 |
小开

假设我们有两个数组，array1和 array2，我们想检查所有的 array1值是否存在于 array2中:

array1.All(ar1 => array2.Any(ar2 => ar2.Equals(ar1)));

注意: 如果以其他方式描述相等，则可以替换 ar2.Equals(ar1)。


提交答案