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

Question

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

有关如何检查该列表是否是另一个列表的任何想法？

具体来说,我有

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

Run Code Online (Sandbox Code Playgroud)

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

Answer 1

Cam*_*and 245

bool isSubset = !t2.Except(t1).Any();

Run Code Online (Sandbox Code Playgroud)

但这对于具有重复值的列表不起作用 (4认同)
如果将其归结为一个名为 ContainsAll 的 linq 方法，那就太好了 (3认同)
如果列表的长度为 n 和 m，那么该算法的时间复杂度是多少？ (2认同)

Answer 2

tva*_*son 56

如果使用集合,请使用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);

Run Code Online (Sandbox Code Playgroud)

对不起,它不使用LINQ.:-(

如果你需要使用列表,那么@Jared的解决方案可以解决你需要删除任何存在的重复元素的问题.

@JaredPar:那又怎样？向某人展示正确的方式比他们想要的方式更好吗？ (6认同)
究竟.您想要一个集合操作,使用为它们设计的类.Cameron的解决方案很有创意,但不像HashSet那样清晰/富有表现力. (3认同)
嗯,我不同意,因为这个问题具体说"使用LINQ". (2认同)

Answer 3

Géz*_*éza 11

如果您是单元测试,您还可以使用CollectionAssert.IsSubsetOf方法:

CollectionAssert.IsSubsetOf(subset, superset);

Run Code Online (Sandbox Code Playgroud)

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

CollectionAssert.IsSubsetOf(t2, t1);

Run Code Online (Sandbox Code Playgroud)

Answer 4

zet*_*oot 9

我花了一些时间使用 BenchmarkDotNet 对这个答案中的 3 个可行解决方案进行基准测试。

\n

!t2.Except(t1).Any()称为 except().Any()
t2.IsSubsetOf(t1)称为哈希集
t2.All(elem => t1.Contains(elem))称为全部（=>包含）

\n

我改变了 3 个参数：

\n

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

\n

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

\n

获胜者是 All(=>Contains) 方法 - 它有时比使用 HashSet 快 30 倍，比 except().Any() 快 50 倍。

\n

代码可以在github上找到

\n

更新\n正如 @Gert Arnold 的评论中提到的，我的基准测试中有一个错误。我ToHashSet()在每次迭代中调用。\n因此，我还构建了一个预构建哈希集的集合，并添加了一个名为的纯哈希集测试prebuilt HashSet。\n这不是绝对的赢家，有时它会失去All(=>Contains)算法。在我看来，重点在于超集中的可变性（和重复性）。当值的可变性较低时，哈希集会获胜，因为它将它从数据中删除。

\n

决赛桌如下：

\n

|             Method | SupersetsInIteration | SubsetLength | Variability |          Mean |        Error |       StdDev |        Median |\n|------------------- |--------------------- |------------- |------------ |--------------:|-------------:|-------------:|--------------:|\n|     Except().Any() |                 1000 |           10 |         100 |   1,485.89 \xce\xbcs |     7.363 \xce\xbcs |     6.887 \xce\xbcs |   1,488.36 \xce\xbcs |\n|        ToHashSet() |                 1000 |           10 |         100 |   1,015.59 \xce\xbcs |     5.099 \xce\xbcs |     4.770 \xce\xbcs |   1,015.43 \xce\xbcs |\n| prebuilt HashSet   |                 1000 |           10 |         100 |      38.76 \xce\xbcs |     0.065 \xce\xbcs |     0.054 \xce\xbcs |      38.78 \xce\xbcs |\n|    All(=>Contains) |                 1000 |           10 |         100 |     105.46 \xce\xbcs |     0.320 \xce\xbcs |     0.267 \xce\xbcs |     105.38 \xce\xbcs |\n|     Except().Any() |                 1000 |           10 |       10000 |   1,912.17 \xce\xbcs |    38.180 \xce\xbcs |    87.725 \xce\xbcs |   1,890.72 \xce\xbcs |\n|        ToHashSet() |                 1000 |           10 |       10000 |   1,038.70 \xce\xbcs |    20.028 \xce\xbcs |    40.459 \xce\xbcs |   1,019.35 \xce\xbcs |\n| prebuilt HashSet   |                 1000 |           10 |       10000 |      28.22 \xce\xbcs |     0.165 \xce\xbcs |     0.155 \xce\xbcs |      28.24 \xce\xbcs |\n|    All(=>Contains) |                 1000 |           10 |       10000 |      81.47 \xce\xbcs |     0.117 \xce\xbcs |     0.109 \xce\xbcs |      81.45 \xce\xbcs |\n|     Except().Any() |                 1000 |           50 |         100 |   4,888.22 \xce\xbcs |    81.268 \xce\xbcs |    76.019 \xce\xbcs |   4,854.42 \xce\xbcs |\n|        ToHashSet() |                 1000 |           50 |         100 |   4,323.23 \xce\xbcs |    21.424 \xce\xbcs |    18.992 \xce\xbcs |   4,315.16 \xce\xbcs |\n| prebuilt HashSet   |                 1000 |           50 |         100 |     186.53 \xce\xbcs |     1.257 \xce\xbcs |     1.176 \xce\xbcs |     186.35 \xce\xbcs |\n|    All(=>Contains) |                 1000 |           50 |         100 |   1,173.37 \xce\xbcs |     2.667 \xce\xbcs |     2.227 \xce\xbcs |   1,173.08 \xce\xbcs |\n|     Except().Any() |                 1000 |           50 |       10000 |   7,148.22 \xce\xbcs |    20.545 \xce\xbcs |    19.218 \xce\xbcs |   7,138.22 \xce\xbcs |\n|        ToHashSet() |                 1000 |           50 |       10000 |   4,576.69 \xce\xbcs |    20.955 \xce\xbcs |    17.499 \xce\xbcs |   4,574.34 \xce\xbcs |\n| prebuilt HashSet   |                 1000 |           50 |       10000 |      33.87 \xce\xbcs |     0.160 \xce\xbcs |     0.142 \xce\xbcs |      33.85 \xce\xbcs |\n|    All(=>Contains) |                 1000 |           50 |       10000 |     131.34 \xce\xbcs |     0.569 \xce\xbcs |     0.475 \xce\xbcs |     131.24 \xce\xbcs |\n|     Except().Any() |                10000 |           10 |         100 |  14,798.42 \xce\xbcs |   120.423 \xce\xbcs |   112.643 \xce\xbcs |  14,775.43 \xce\xbcs |\n|        ToHashSet() |                10000 |           10 |         100 |  10,263.52 \xce\xbcs |    64.082 \xce\xbcs |    59.942 \xce\xbcs |  10,265.58 \xce\xbcs |\n| prebuilt HashSet   |                10000 |           10 |         100 |   1,241.19 \xce\xbcs |     4.248 \xce\xbcs |     3.973 \xce\xbcs |   1,241.75 \xce\xbcs |\n|    All(=>Contains) |                10000 |           10 |         100 |   1,058.41 \xce\xbcs |     6.766 \xce\xbcs |     6.329 \xce\xbcs |   1,059.22 \xce\xbcs |\n|     Except().Any() |                10000 |           10 |       10000 |  16,318.65 \xce\xbcs |    97.878 \xce\xbcs |    91.555 \xce\xbcs |  16,310.02 \xce\xbcs |\n|        ToHashSet() |                10000 |           10 |       10000 |  10,393.23 \xce\xbcs |    68.236 \xce\xbcs |    63.828 \xce\xbcs |  10,386.27 \xce\xbcs |\n| prebuilt HashSet   |                10000 |           10 |       10000 |   1,087.21 \xce\xbcs |     2.812 \xce\xbcs |     2.631 \xce\xbcs |   1,085.89 \xce\xbcs |\n|    All(=>Contains) |                10000 |           10 |       10000 |     847.88 \xce\xbcs |     1.536 \xce\xbcs |     1.436 \xce\xbcs |     847.34 \xce\xbcs |\n|     Except().Any() |                10000 |           50 |         100 |  48,257.76 \xce\xbcs |   232.573 \xce\xbcs |   181.578 \xce\xbcs |  48,236.31 \xce\xbcs |\n|        ToHashSet() |                10000 |           50 |         100 |  43,938.46 \xce\xbcs |   994.200 \xce\xbcs | 2,687.877 \xce\xbcs |  42,877.97 \xce\xbcs |\n| prebuilt HashSet   |                10000 |           50 |         100 |   4,634.98 \xce\xbcs |    16.757 \xce\xbcs |    15.675 \xce\xbcs |   4,643.17 \xce\xbcs |\n|    All(=>Contains) |                10000 |           50 |         100 |  10,256.62 \xce\xbcs |    26.440 \xce\xbcs |    24.732 \xce\xbcs |  10,243.34 \xce\xbcs |\n|     Except().Any() |                10000 |           50 |       10000 |  73,192.15 \xce\xbcs |   479.584 \xce\xbcs |   425.139 \xce\xbcs |  73,077.26 \xce\xbcs |\n|        ToHashSet() |                10000 |           50 |       10000 |  45,880.72 \xce\xbcs |   141.497 \xce\xbcs |   125.433 \xce\xbcs |  45,860.50 \xce\xbcs |\n| prebuilt HashSet   |                10000 |           50 |       10000 |   1,620.61 \xce\xbcs |     3.507 \xce\xbcs |     3.280 \xce\xbcs |   1,620.52 \xce\xbcs |\n|    All(=>Contains) |                10000 |           50 |       10000 |   1,460.01 \xce\xbcs |     1.819 \xce\xbcs |     1.702 \xce\xbcs |   1,459.49 \xce\xbcs |\n|     Except().Any() |               100000 |           10 |         100 | 149,047.91 \xce\xbcs | 1,696.388 \xce\xbcs | 1,586.803 \xce\xbcs | 149,063.20 \xce\xbcs |\n|        ToHashSet() |               100000 |           10 |         100 | 100,657.74 \xce\xbcs |   150.890 \xce\xbcs |   117.805 \xce\xbcs | 100,654.39 \xce\xbcs |\n| prebuilt HashSet   |               100000 |           10 |         100 |  12,753.33 \xce\xbcs |    17.257 \xce\xbcs |    15.298 \xce\xbcs |  12,749.85 \xce\xbcs |\n|    All(=>Contains) |               100000 |           10 |         100 |  11,238.79 \xce\xbcs |    54.228 \xce\xbcs |    50.725 \xce\xbcs |  11,247.03 \xce\xbcs |\n|     Except().Any() |               100000 |           10 |       10000 | 163,277.55 \xce\xbcs | 1,096.107 \xce\xbcs | 1,025.299 \xce\xbcs | 163,556.98 \xce\xbcs |\n|        ToHashSet() |               100000 |           10 |       10000 |  99,927.78 \xce\xbcs |   403.811 \xce\xbcs |   337.201 \xce\xbcs |  99,812.12 \xce\xbcs |\n| prebuilt HashSet   |               100000 |           10 |       10000 |  11,671.99 \xce\xbcs |     6.753 \xce\xbcs |     5.986 \xce\xbcs |  11,672.28 \xce\xbcs |\n|    All(=>Contains) |               100000 |           10 |       10000 |   8,217.51 \xce\xbcs |    67.959 \xce\xbcs |    56.749 \xce\xbcs |   8,225.85 \xce\xbcs |\n|     Except().Any() |               100000 |           50 |         100 | 493,925.76 \xce\xbcs | 2,169.048 \xce\xbcs | 1,922.805 \xce\xbcs | 493,386.70 \xce\xbcs |\n|        ToHashSet() |               100000 |           50 |         100 | 432,214.15 \xce\xbcs | 1,261.673 \xce\xbcs | 1,180.169 \xce\xbcs | 431,624.50 \xce\xbcs |\n| prebuilt HashSet   |               100000 |           50 |         100 |  49,593.29 \xce\xbcs |    75.300 \xce\xbcs |    66.751 \xce\xbcs |  49,598.45 \xce\xbcs |\n|    All(=>Contains) |               100000 |           50 |         100 |  98,662.71 \xce\xbcs |   119.057 \xce\xbcs |   111.366 \xce\xbcs |  98,656.00 \xce\xbcs |\n|     Except().Any() |               100000 |           50 |       10000 | 733,526.81 \xce\xbcs | 8,728.516 \xce\xbcs | 8,164.659 \xce\xbcs | 733,455.20 \xce\xbcs |\n|        ToHashSet() |               100000 |           50 |       10000 | 460,166.27 \xce\xbcs | 7,227.011 \xce\xbcs | 6,760.150 \xce\xbcs | 457,359.70 \xce\xbcs |\n| prebuilt HashSet   |               100000 |           50 |       10000 |  17,443.96 \xce\xbcs |    10.839 \xce\xbcs |     9.608 \xce\xbcs |  17,443.40 \xce\xbcs |\n|    All(=>Contains) |               100000 |           50 |       10000 |  14,222.31 \xce\xbcs |    47.090 \xce\xbcs |    44.048 \xce\xbcs |  14,217.94 \xce\xbcs |\n\n

Run Code Online (Sandbox Code Playgroud)\n

Answer 5

Nei*_*eil 6

@ Cameron的解决方案作为扩展方法:

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

Run Code Online (Sandbox Code Playgroud)

用法:

bool isSubset = t2.IsSubsetOf(t1);

Run Code Online (Sandbox Code Playgroud)

(这与@ Michael博客上发布的内容类似,但不完全相同)

Answer 6

use*_*458 6

这是一个比这里发布的其他解决方案更有效的解决方案,尤其是顶级解决方案:

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

Run Code Online (Sandbox Code Playgroud)

如果你能在t2中找到一个不在t1中的单个元素,那么你知道t2不是t1的子集.与使用.Except或.Intersect的解决方案不同,这种方法的优点是它可以在所有就地完成,而无需分配额外的空间.此外,该解决方案能够在找到违反子集条件的单个元素时立即中断,而其他元素继续搜索.下面是解决方案的最佳长形式,在我的测试中仅比上述速记解决方案略快.

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

Run Code Online (Sandbox Code Playgroud)

我对所有解决方案进行了一些基本的性能分析,结果非常激烈.这两个解决方案比.Except()和.Intersect()解决方案快约100倍,并且不使用额外的内存.

这不是 Linq 的工作方式。`t2.Except (t1)` 返回的是一个 `IEnumerable` 而不是 `Collection`。如果您完全迭代它，它只会发出所有可能的项目，例如通过 `ToArray ()` 或 `ToList ()` 或使用 `foreach` 而不会破坏内部。搜索 *linq deferred execution* 以了解有关该概念的更多信息。 (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 中的元素。 (3认同)
这正是 `!t2.Except(t1).Any()` 正在做的事情。Linq 正在来回工作。`Any()` 正在询问 `IEnumerable` 是否至少有一个元素。在这种情况下，“t2.Except(t1)”仅发出“t2”中不在“t1”中的第一个元素。如果“t2”的第一个元素不在“t1”中，则它完成得最快，如果“t2”的所有元素都在“t1”中，则运行时间最长。 (2认同)

归档时间：	16 年，9 月前
查看次数：	41302 次
最近记录：	6 年，11 月前