为什么与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的代码进行基准测试表明此版本的速度是使用矢量的解决方案的两倍多。

热门问答

Tencent Cloud API 3.0 SDK for PHP 没有文件夹 vendor?

推荐

为了防止和composer冲突,所以github上特意设置了不导出这个目录。如需要获取源码,请使用git clone的方式获取,不要用github上的下载源码方式。

lora接入腾讯物联网是只能在深圳地区吗?

DylanRichard

腾讯 · 产品经理 (已认证)

万物互联的时代,欢迎来到IoT的世界
推荐

深圳的南山及龙岗全区,可以租用腾讯运营的网络,支持CLAA协议,其它区域需要客户购买网关接入LPWA物联网络管理平台,支持LoRaWAN协议,我们也有网关、模组及传感器产品售卖。

ckafka是否支持kafka-connect-jdbc?

您好, 现在CKafka支持 kafka-connect-kafka(内侧功能),暂时还不能支持 jdbc的connector。如果这是您的需求,请提交工单,联系腾讯云工程师描述您的需求,我们会尽快规划并实现。

沙龙活动报名通知什么时候会收到通知呢?

Richel码农
推荐已采纳

沙龙报名之后会收到报名成功的短信,活动前一天会发送签到二维码短信和邮件,请留意.

请问有创建项目的sdk吗?

推荐

这是api2.0的接口,使用对应的sdk,代码托管在http://github.com/qcloudapi

云通信 uuid换取下载url 返回的文件地址无法访问?

推荐

您好,这个接口“v4/rich_media/query_file_url”目前新版本已经不支持了,想获取的话,建议升级SDK版本到最新版,最新版用的是cos。新版的拿到URL后直接在浏览器中打开。

所属标签

扫码关注云+社区

领取腾讯云代金券