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

v6ylcynt  于 2023-04-06  发布在  其他
关注(0)|答案(3)|浏览(201)

有一个方法contains可以用来检查Vec中是否存在特定的元素。如何检查Vec中的所有元素是否都包含在另一个Vec中?有什么比手动迭代并显式检查所有元素更简洁的方法吗?

vcudknz3

vcudknz31#

您有两个主要选择:

  • 简单地检查一个向量中的每个元素,看看它是否在另一个向量中。这具有时间复杂度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有不同的性能特征。
下面是一些粗略的基准测试(source),测试了实现如何随输入大小而变化。在所有测试中,b的大小是a的一半,并且包含a元素的随机子集:
| 尺寸a|Vec::contains|HashSet::contains|BtreeSet::contains|
| --------------|--------------|--------------|--------------|
| 10个|十四岁|三八六|三二七|
| 一百|一千七百五十四人|三千一百八十七|五千三百七十一|
| 一千|十一万二千三百零六|三万一千二百三十三|八万八千三百四十|
| 一万|二百八十二万一千八百六十七|二十五万四千八百零一|七十二万八千二百六十八|
| 十万|29207999|二百六十四万五千七百零三|六百六十一万一千六百六十六|
时间单位为纳秒。
简单的O(n^2)解决方案在元素数量较少时是最快的。当大小超过200时,分配HashSetBTreeSet的开销被比较次数的影响所掩盖。BTreeSet通常比HashSet慢很多,但当元素数量 * 非常 * 小时稍微快一些。

dgiusagp

dgiusagp2#

如果你有排序的向量,你可以在线性时间内进行搜索:

let mut vec = vec![0, 2, 4, 3, 6, 3, 5, 1, 0];
    let mut v = vec![1, 4, 3, 3, 1];

    vec.sort_unstable();
    v.sort_unstable();

    // Remove duplicates elements in v
    v.dedup();

    let mut vec_iter = vec.iter();
    assert!(v.iter().all(|&x| vec_iter.any(|&item| item == x)));

参考:C++有std::includes,它就是这样做的。

rsl1atfo

rsl1atfo3#

你也可以对向量进行排序,然后测试它们是否相等:

fn main() {
    let mut v1 = vec![2, 3, 1];
    let mut v2 = vec![3, 1, 2];
    
    v1.sort();
    v2.sort();

    assert_eq!(v1, v2);
}

相关问题