vector - 与 BTreeSet 相比，为什么使用 Vec 可以更快地找到整数集的交集？

Question

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

我最初尝试迭代一个 Vec 并为每个元素检查它是否存在于另一个 Vec 中。然后我决定改用 BTreeSet，因为它在检查集合中是否存在整数时应该明显更快，但事实似乎并非如此。 Vec 实现需要大约 72 毫秒，而 BTreeSet 在稳定的 Rust 1.34 下以 Release模式调用数千个集合时需要大约 96 毫秒，每晚使用时性能相同。

这是 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 n) 访问时间不够用而导致执行速度变慢？如果是这样，我还能做些什么来加速这个功能吗？

Answer 1

由于您的集合不会随时间变化，我认为您最好的选择是使用排序向量。只需要在初始化时对向量进行一次排序。两个排序向量的交集可以在线性时间内通过同时迭代它们来计算，总是推进当前指向较低数字的迭代器。这是对实现的尝试:

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表示此版本的速度是使用向量的解决方案的三倍多。