为什么与BTreeSet相比,与Vec更快地找到整数集的交集?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (8)

我需要快速找出两个给定集合中存在多少个整数。这些集只被写入一次,但是这个操作将使用不同的对集合执行多次。集合包含5-30个整数,其中最大的整数为840000。

我最初尝试迭代一个,Vec并为每个元素检查它是否存在于另一个元素中Vec。然后我决定使用BTreeSet它,因为它应该明显更快地检查集合中是否存在整数,但似乎并非如此。Vec当在夜间使用时,在稳定的Rust 1.34下以相同的性能在释放模式下调用数千集时,实现需要~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

该程序的完整代码可在此处获得

BTreeSet实现是否较慢,因为集合中的整数太少,不允许其O(log n)访问时间闪耀?如果是这样,我还能做些什么来加速这个功能吗?

提问于
用户回答回答于

由于您的集合不随时间而变化,我认为您最好的选择是使用排序向量。在初始化时,仅需要对向量进行一次排序。通过同时迭代它们,可以在线性时间内计算两个排序矢量的交集。以下是对实施的尝试:

use std::cmp::Ordering;

fn intersection_count_sorted_vec(a: &[u32], b: &[u32]) -> usize {
    let mut count = 0;
    macro_rules! next {
        ($iter:ident, $var:ident) => {
            if let Some(tmp) = $iter.next() {
                $var = tmp;
            } else {
                return count;
            }
        }
    }
    let mut a_iter = a.iter();
    let mut b_iter = b.iter();
    let mut current_a;
    let mut current_b;
    next!(a_iter, current_a);
    next!(b_iter, current_b);
    loop {
        match current_a.cmp(&current_b) {
            Ordering::Less => next!(a_iter, current_a),
            Ordering::Greater => next!(b_iter, current_b),
            Ordering::Equal => {
                count += 1;
                next!(a_iter, current_a);
                next!(b_iter, current_b);
            }
        }
    }
}

这可能没有特别好的优化; 无论如何,使用基于Criterion的代码进行基准测试表明此版本的速度是使用矢量的解决方案的两倍多。

所属标签

可能回答问题的人

  • 西风

    renzha.net · 站长 (已认证)

    7 粉丝1 提问11 回答
  • 四无君

    0 粉丝0 提问3 回答
  • 旺仔小小鹿

    社区 · 运营 (已认证)

    46 粉丝0 提问2 回答
  • 拉布拉多拉不多

    1 粉丝0 提问2 回答

扫码关注云+社区

领取腾讯云代金券