检查 Vec 是否包含来自另一个 Vec 的所有元素

Question

There is a method contains that can be used to check if a particular element exists in a Vec. How to check if all elements from a Vec are contained in another Vec? Is there something more concise than iterating manually and checking all elements explicitly?

Answer 1

您有两个主要选择：

• 天真地检查一个向量中的每个元素，看看它是否在另一个向量中。这具有时间复杂度 O(n^2) 但它也非常简单并且开销很低：

  assert!(b.iter().all(|item| a.contains(item)));
  

• 创建一个向量的所有元素的集合，然后检查另一个向量的元素是否包含在其中。这具有 O(n) 时间复杂度，但包括额外的堆分配在内的开销更高：

  let a_set: HashSet<_> = a.iter().copied().collect();
  assert!(b.iter().all(|item| a_set.contains(item)));
  

哪个“更好”取决于您的要求。如果您只关心速度，更好的选择仍然取决于向量中的元素数量，因此您应该使用真实数据进行测试。您还可以使用 进行测试BTreeSet，它与 具有不同的性能特征HashSet。

以下是一些粗略的基准测试（来源），用于说明实现如何随输入的大小而变化。在所有测试中，b是 的一半大小a并包含a的元素的随机子集：

尺寸 a	Vec::contains	HashSet::contains	BtreeSet::contains
10	14	386	327
100	1,754	3,187	5,371
1000	112,306	31,233	88,340
10000	2,821,867	254,801	728,268
100000	29,207,999	2,645,703	6,611,666

以纳秒为单位的时间。

O(n^2)当元素数量很少时，朴素的解决方案最快。分配 a HashSetor的开销BTreeSet在大小超过 200 左右时被比较次数的影响所掩盖。BTreeSet大多比 慢很多HashSet，但在元素数量非常小时时略快。