Как хранить список элементов, из которых я буду удалять, но не добавлять? - PullRequest
Новая
       29

Как хранить список элементов, из которых я буду удалять, но не добавлять?

2 голосов
/ 25 июня 2019

Я реализую функцию, в которой я буду неоднократно исключать значения из большого списка и передавать копию этого списка как вектор в другую функцию на каждой итерации: 

let mut v = vec![5, 4, 4, 2, 6, 5, 1, 8, 2, 1, 6, 5, 4, 2, 0, 1];
for i in 0..10 {
    println!("{}", Vector::from(v).iter().sum());
    v.retain(|x| x > i);
}

Если v очень большой, это будет медленноЕсть ли способ лучше?Я попытался: 

let mut v = vec![5, 4, 4, 2, 6, 5, 1, 8, 2, 1, 6, 5, 4, 2, 0, 1];
let mut v = v.into_iter().map(|x| Some(x)).collect();

(а затем заменить «удаленные» значения на None), но это просто казалось громоздким, чтобы преобразовать в и из обычного Vec.

Как следуетЯ буду хранить этот список значений?

Ответы [ 3 ]

1 голос
/ 27 июня 2019

Поскольку речь идет о производительности, вам нужно будет сравнить все, чтобы проверить свои предположения. Это, как говорится, и если в вызываемой функции нет чего-то умного (возможно, только лениво копировать элементы, которые вы хотите изменить), то я думаю, что ваш retain + clone подход близок к быстрейшему, что вы можете сделать. Использование Option s почти наверняка плохая идея: он добавляет проверки повсюду и убивает локальность кэша.

Единственное, что может повысить производительность, - это выполнить копирование и фильтрацию за один проход: 

let mut v = vec![5, 4, 4, 2, 6, 5, 1, 8, 2, 1, 6, 5, 4, 2, 0, 1];
let mut work = v.clone();
for i in 0..10 {
    println!("{}", work.iter().sum::<i32>());
    work.clear();
    v.retain(|&x| if (x > i) { work.push (x); true } else { false });
}

детская площадка

Обратите внимание, что это, вероятно, не будет иметь никакого значения, если ваши данные помещаются в кэш. В любом случае, эталон, , эталон , , эталон ! Многие предположения оказываются неверными в условиях оптимизации компилятора и современной архитектуры ЦП.

0 голосов
/ 26 июня 2019

Если вы удаляете элементы по порядку, вы должны рассмотреть очередь .Использование remove() занимает O (1) время для удаления элемента, потому что это, по сути, dequeue или pop.

0 голосов
/ 25 июня 2019

Вы можете реструктурировать создание скопированного списка, чтобы выполнить удаление до копии: 

for i in 0..10 {
    let dup = your_list.iter().filter(|n| n > i).collect::<Vec<_>>();
    use_it(dup);
}

Если для вашего варианта использования важно, чтобы у вас осталась отфильтрованнаяVec, и не может изменить тип коллекции, то это, вероятно, самый полезный способ.Если фильтры являются кумулятивными, вы можете перезаписать исходную Vec с отфильтрованной Vec каждой итерацией, чтобы уменьшить рабочую нагрузку для каждой будущей итерации. 

let mut list = your_list;
for i in 0..10 {
    list = list.iter().filter(|n| n > i).collect();
    use_it(list.clone());
}

Заданный вами вопрос прямо ответил, изменив способ фильтрации и дублирования вектора, но если вы можете изменить свои типы, то ответы ниже могут быть более полезными.

Если ваша use_it функция не требуется a Vec или срез, тогда вам может быть лучше обслужить перестройку потребителя, чтобы он взял итератор чисел, и передав your_list.iter().filter(...).Это не приведет к копированию или переупорядочению в памяти, а функция потребителя просто пропустит недопустимые значения.

Если вам нужно больше подсчитывать, сколько раз числа появляются в коллекции, и вам не требуется конкретно последовательноеСписок в памяти, вы можете изменить свой список в HashMap: 

use std::collections::HashMap;
let mut dict: HashMap<i32, usize> = HashMap::new();
for num in your_list {
    *dict.entry(num).or_insert(0) += 1;
}

, а затем вы можете отфильтровать числа из карты с постоянным доступом, а не с линейным временем по размеру коллекции.

...