Почему поиск пересечения целочисленных множеств быстрее с Vec по сравнению с BTreeSet? - PullRequest
Новая
       27

Почему поиск пересечения целочисленных множеств быстрее с Vec по сравнению с BTreeSet?

4 голосов
/ 22 мая 2019

Мне нужно выяснить, сколько целых чисел присутствует в обоих заданных наборах, быстро.Наборы записываются только один раз, но эта операция будет выполняться много раз с разными парами наборов.Наборы содержат 5-30 целых чисел, и наибольшее из этих целых чисел составляет 840000.

Сначала я попытался выполнить итерацию для одного Vec и для каждого элемента проверить, присутствует ли он в другом Vec.Затем я решил использовать BTreeSet вместо этого, поскольку он должен быть значительно быстрее при проверке наличия целого числа в наборе, но, похоже, это не так.Реализация Vec занимает ~ 72 мс, а BTreeSet ~ 96 мс при вызове на нескольких тысячах наборов в режиме выпуска в стабильном Rust 1.34 с той же производительностью при использовании ночью.

Это реализация 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) ксияние?Если да, могу ли я еще что-нибудь сделать, чтобы ускорить эту функцию?

1 Ответ

2 голосов
/ 23 мая 2019

Поскольку ваши наборы не меняются со временем, я думаю, что ваш лучший вариант - использовать отсортированные векторы. Сортировка векторов потребуется только один раз, во время инициализации. Пересечение двух отсортированных векторов может быть вычислено в линейное время путем итерации по ним одновременно, всегда опережая итератор, который в данный момент указывает на меньшее число. Вот попытка реализации: 

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
}

Это, вероятно, не особенно хорошо оптимизировано; независимо от того, сравнительный анализ с кодом на основе критерия указывает, что эта версия более чем в три раза быстрее, чем ваше решение с использованием векторов.

...