Есть ли встроенная функция для вычисления разницы двух наборов?

ProgramBox

Есть ли встроенная функция для вычисления разницы двух наборов?

Post author:admin
Запись опубликована:12 апреля, 2023
Post category:Вопросы по программированию

#rust #set

#Ржавчина #набор

Вопрос:

Новое в Rust. Довольно простой вопрос, я некоторое время искал и не мог найти ответа

В принципе, я хочу что-то вроде этого

 let mut v1 = vec![0, 1, 2, 3, 4];
let mut v2 = vec![3, 4];
assert_eq!(v1 - v2, amp;[0, 1, 2]);

let mut v1 = vec![0, 1, 2, 3, 4, 5, 6];
let mut v2 = vec![3, 4];
assert_eq!(v1 - v2, amp;[0, 1, 2, 5, 6]);

let mut v1 = vec![0, 1, 2, 3, 4, 5, 6];
let mut v2 = vec![7];
assert_eq!(v1 - v2, amp;[0, 1, 2, 3, 4, 5, 6]);

1. Не совсем понятно, как это должно работать. Что, если v2 это не суффикс v1 ?

2. Я добавляю больше примеров

3. Векторы не являются наборами, поэтому такая операция не была бы эффективной и не определена. Смотрите HashSet вместо этого.

4. Из примеров похоже, что вы хотите удалить элементы в обоих векторах из первого вектора. Наборы были бы хорошим способом сделать это для большого количества элементов. Для меньшего числа векторы были бы приемлемы и могли бы даже быть быстрее.

5. Каков ожидаемый результат для [1, 1, 2, 2] - [1, 2] ? Имеет ли значение порядок?

Ответ №1:

Основываясь на ваших примерах, кажется, что вы ищете векторы, элементы которых уникальны.

Векторы на самом деле не гарантируют это свойство (элементы не обязательно должны быть уникальными или упорядоченными, более того, им даже не обязательно поддерживать сравнение), но наборы (HashSet или BTreeSet). И HashSet действительно поддерживает - оператор:

(ссылка на игровую площадку)

 use std::collections::HashSet;

fn main() {
    let s1: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    let s2: HashSet<i32> = [3, 4].iter().cloned().collect();
    let expected: HashSet<i32> = [0, 1, 2].iter().cloned().collect();
    assert_eq!(amp;s1 - amp;s2, expected);
}

Если вы хотите выполнить эту операцию над векторами, вы могли бы преобразовать в HashSet или BTreeSet, а затем создать вектор из этого:

 fn vect_difference(v1: amp;Vec<i32>, v2: amp;Vec<i32>) -> Vec<i32> {
    let s1: HashSet<i32> = v1.iter().cloned().collect();
    let s2: HashSet<i32> = v2.iter().cloned().collect();
    (amp;s1 - amp;s2).iter().cloned().collect()
}

Или вы могли бы выполнить разницу непосредственно для векторов (имея в виду, что это алгоритм O (N * M) и будет работать плохо, если оба вектора будут длинными):

 fn vect_difference(v1: amp;Vec<i32>, v2: amp;Vec<i32>) -> Vec<i32> {
    v1.iter().filter(|amp;x| !v2.contains(x)).cloned().collect()
}

1. Для аргументов функции неплохо использовать срез amp;[T] вместо вектора amp;Vec<T> . Общая ссылка на vec добавляет ненужную косвенность при доступе к данным и не дает никаких преимуществ по сравнению с amp;[T] . Срез, с другой стороны, может быть получен из любых последовательно сохраненных данных, а не только из вектора.

2. Полностью согласен с разделами re и Vec. Я хотел сфокусироваться на примере Vec, поскольку это то, с чем работает OP. Я думаю, что всегда возникает вопрос о том, сколько лучших практик следует перенести в сообщение — возможно, здесь было бы лучше использовать amp;[T] , но иногда вы в конечном итоге объясняете слишком много ключевых моментов таким образом…

3. @Paul в зависимости от длины версии v2, возможно, стоит преобразовать только это в предварительный набор, чтобы избежать оплаты поиска членства O (n) для каждого элемента v1.

4. Достаточно справедливо. Я думаю, я бы просто заставил post принять amp;[i32] без специального объяснения, поскольку фрагменты достаточно просты, чтобы их охватил любой учебник по Rust. Но, поскольку вы знаете о наилучшей практике, это просто вопрос вкуса.

Ответ №2:

Для удаления элементов из одного вектора, которые находятся в другом:

 fn subtract(a: amp;Vec<i32>, b: amp;Vec<i32>) -> Vec<i32> {
    let mut c = a.clone();
    c.retain(|x| !b.contains(x));
    c
}

или, если вы согласны с изменением первого вектора:

 fn subtract(a: amp;mut Vec<i32>, b: amp;Vec<i32>) {
    a.retain(|x| !b.contains(x));
}

Обратите внимание, что это алгоритм O (N * M), где N, M — длины векторов.

Это быстро для небольшого количества элементов. Для большего числа вы могли бы использовать HashSet . difference Метод предоставляет применимый пример, изначально создавая наборы из векторов.

Вот моя версия, которая создает только один HashSet и, следовательно, быстрее, если вы начинаете с двух векторов и хотите закончить вектором. Это похоже на то, что difference() выполняется под капотом.

 use std::collections::HashSet;
let b: HashSet<_> = v2.into_iter().collect();
v1.retain(|x| !b.contains(x));

Это будет O (M N): M для построения хэш-набора из второго вектора и N для проверки каждого элемента в первом векторе.