我需要找出在两个给定的集合中都有多少个整数。这些集合仅写入一次,但此操作将对不同的集合对执行多次。这些集合包含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 )访问时间更快吗?如果是这样的话,我还能做些什么来加速这个函数呢?
发布于 2019-05-23 05:07:28
由于您的集合不会随着时间的推移而改变,我认为您最好的选择是使用排序向量。只需要在初始化时对向量进行一次排序。两个排序向量的交集可以通过同时迭代它们来在线性时间内计算,始终将当前指向较低数字的迭代器向前推进。下面是一个实现的尝试:
fn intersection_count_sorted_vec(a: &[u32], b: &[u32]) -> usize {
let mut count = 0;
let mut b_iter = b.iter();
if let Some(mut current_b) = b_iter.next() {
for current_a in a {
while current_b < current_a {
current_b = match b_iter.next() {
Some(current_b) => current_b,
None => return count,
};
}
if current_a == current_b {
count += 1;
}
}
}
count
}
这可能没有得到特别好的优化;无论如何,benchmarking with Criterion-based code指出这个版本的速度是使用向量的解决方案的三倍多。
https://stackoverflow.com/questions/56261476
复制相似问题