首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >为什么使用Vec比使用BTreeSet更快地找到整数集的交集?

为什么使用Vec比使用BTreeSet更快地找到整数集的交集?
EN

Stack Overflow用户
提问于 2019-05-23 00:39:25
回答 1查看 2.5K关注 0票数 5

我需要找出在两个给定的集合中都有多少个整数。这些集合仅写入一次,但此操作将对不同的集合对执行多次。这些集合包含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 )访问时间更快吗?如果是这样的话,我还能做些什么来加速这个函数呢?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 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指出这个版本的速度是使用向量的解决方案的三倍多。

票数 5
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56261476

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档