我需要找出在两个给定的集合中都有多少个整数。这些集合仅写入一次,但此操作将对不同的集合对执行多次。这些集合包含5-30个整数,其中最大的整数是840000。
我最初尝试遍历一个Vec
,并针对每个元素检查它是否存在于另一个Vec
中。然后我决定改用BTreeSet
,因为它在检查集合中是否存在整数时应该要快得多,但情况似乎并非如此。在稳定的Rust 1.34下以释放模式调用数千组时,Vec
实现耗时约72ms,BTreeSet约为96ms,夜间使用时性能相同。
这是Vec
的实现:
use std::cmp;
fn main() {
let mut sets = Vec::with_capacity(1000);
for i in 1..1000 {
let mut set = Vec::new();
for j in 1..i % 30 {
set.push(i * j % 50000);
}
sets.push(set);
}
for left_set in sets.iter() {
for right_set in sets.iter() {
calculate_waste(left_set, right_set);
}
}
}
fn calculate_waste(left_nums: &Vec<usize>, right_nums: &Vec<usize>) -> usize {
let common_nums = left_nums.iter().fold(0, |intersection_count, num| {
intersection_count + right_nums.contains(num) as usize
});
let left_side = left_nums.len() - common_nums;
let right_side = right_nums.len() - common_nums;
let score = cmp::min(common_nums, cmp::min(left_side, right_side));
left_side - score + right_side - score + common_nums - score
}
这是BTreeSet
的实现:
use std::cmp;
use std::collections::BTreeSet;
fn main() {
let mut sets = Vec::with_capacity(1000);
for i in 1..1000 {
let mut set = BTreeSet::new();
for j in 1..i % 30 {
set.insert(i * j % 50000);
}
sets.push(set);
}
for left_set in sets.iter() {
for right_set in sets.iter() {
calculate_waste(left_set, right_set);
}
}
}
fn calculate_waste(left_nums: &BTreeSet<usize>, right_nums: &BTreeSet<usize>) -> usize {
let common_nums = left_nums.intersection(&right_nums).count();
let left_side = left_nums.len() - common_nums;
let right_side = right_nums.len() - common_nums;
let score = cmp::min(common_nums, cmp::min(left_side, right_side));
left_side - score + right_side - score + common_nums - score
}
它是使用以下命令运行的(-w 50
使其忽略前50次运行):
hyperfine "cargo run --release" -w 50 -m 100
该程序的完整代码可用here。
BTreeSet
实现变慢是因为集合中的整数太少,无法让O(log )访问时间更快吗?如果是这样的话,我还能做些什么来加速这个函数呢?
https://stackoverflow.com/questions/56261476
复制相似问题