有一个方法contains可以用来检查Vec中是否存在特定的元素。如何检查Vec中的所有元素是否都包含在另一个Vec中?有什么比手动迭代并显式检查所有元素更简洁的方法吗?
Vec
vcudknz31#
您有两个主要选择:
assert!(b.iter().all(|item| a.contains(item)));
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时,分配HashSet或BTreeSet的开销被比较次数的影响所掩盖。BTreeSet通常比HashSet慢很多,但当元素数量 * 非常 * 小时稍微快一些。
BTreeSet
HashSet
b
a
Vec::contains
HashSet::contains
BtreeSet::contains
O(n^2)
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,它就是这样做的。
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); }
3条答案
按热度按时间vcudknz31#
您有两个主要选择:
哪一个“更好”取决于你的需求。如果你只关心速度,更好的选择仍然取决于向量中元素的数量,所以你应该用真实的数据来测试。你也可以用
BTreeSet
来测试,它与HashSet
有不同的性能特征。下面是一些粗略的基准测试(source),测试了实现如何随输入大小而变化。在所有测试中,
b
的大小是a
的一半,并且包含a
元素的随机子集:| 尺寸
a
|Vec::contains
|HashSet::contains
|BtreeSet::contains
|| --------------|--------------|--------------|--------------|
| 10个|十四岁|三八六|三二七|
| 一百|一千七百五十四人|三千一百八十七|五千三百七十一|
| 一千|十一万二千三百零六|三万一千二百三十三|八万八千三百四十|
| 一万|二百八十二万一千八百六十七|二十五万四千八百零一|七十二万八千二百六十八|
| 十万|29207999|二百六十四万五千七百零三|六百六十一万一千六百六十六|
时间单位为纳秒。
简单的
O(n^2)
解决方案在元素数量较少时是最快的。当大小超过200时,分配HashSet
或BTreeSet
的开销被比较次数的影响所掩盖。BTreeSet
通常比HashSet
慢很多,但当元素数量 * 非常 * 小时稍微快一些。dgiusagp2#
如果你有排序的向量,你可以在线性时间内进行搜索:
参考:C++有std::includes,它就是这样做的。
rsl1atfo3#
你也可以对向量进行排序,然后测试它们是否相等: