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

Question

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

我最初尝试迭代一个Vec元素，并为每个元素检查它是否存在于另一个Vec. 然后我决定BTreeSet改用它，因为它在检查集合中是否存在整数时应该明显更快，但情况似乎并非如此。Vec在稳定的 Rust 1.34 下，在稳定的 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) 访问时间无法发挥作用？如果是这样，我还能做些什么来加速这个功能？

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
}

这可能不是特别优化；无论如何，使用基于 Criterion 的代码进行基准测试表明此版本的速度是使用向量的解决方案的三倍多。