Могу ли я эффективно выбрать случайный образец из HashSet?

Question

У меня есть std::collections::HashSet, и я хочу сэмплировать и удалить равномерно случайный элемент.

В настоящее время я делаю случайную выборку индекса, используя rand.gen_range, затем перебирая HashSet к этому индексу, чтобы получить элемент.Затем я удаляю выбранный элемент.Это работает, но это не эффективно.Есть ли эффективный способ сделать случайную выборку элемента?

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

use std::collections::HashSet;

extern crate rand;
use rand::thread_rng;
use rand::Rng;

let mut hash_set = HashSet::new();

// ... Fill up hash_set ...

let index = thread_rng().gen_range(0, hash_set.len());
let element = hash_set.iter().nth(index).unwrap().clone();
hash_set.remove(&element);

// ... Use element ...

Answer 1

Думая об ответе Свена Марнаха, я хочу использовать вектор, но мне также нужно вставлять постоянное время без дублирования.Затем я понял, что могу поддерживать как вектор, так и набор, и гарантировать, что у них обоих всегда были одинаковые элементы.Это позволит вставлять как постоянное время с дедупликацией, так и случайное удаление с постоянным временем.

Вот реализация, с которой я закончил:

struct VecSet<T> {
    set: HashSet<T>,
    vec: Vec<T>,
}

impl<T> VecSet<T>
where
    T: Clone + Eq + std::hash::Hash,
{
    fn new() -> Self {
        Self {
            set: HashSet::new(),
            vec: Vec::new(),
        }
    }
    fn insert(&mut self, elem: T) {
        assert_eq!(self.set.len(), self.vec.len());
        let was_new = self.set.insert(elem.clone());
        if was_new {
            self.vec.push(elem);
        }
    }
    fn remove_random(&mut self) -> T {
        assert_eq!(self.set.len(), self.vec.len());
        let index = thread_rng().gen_range(0, self.vec.len());
        let elem = self.vec.swap_remove(index);
        let was_present = self.set.remove(&elem);
        assert!(was_present);
        elem
    }
    fn is_empty(&self) -> bool {
        assert_eq!(self.set.len(), self.vec.len());
        self.vec.is_empty()
    }
}

Answer 2

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

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

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

Вот пример реализации для удаления случайного элемента из Vec в постоянное время:

use rand::{thread_rng, Rng};

pub trait RemoveRandom {
    type Item;

    fn remove_random<R: Rng>(&mut self, rng: &mut R) -> Option<Self::Item>;
}

impl<T> RemoveRandom for Vec<T> {
    type Item = T;

    fn remove_random<R: Rng>(&mut self, rng: &mut R) -> Option<Self::Item> {
        if self.len() == 0 {
            None
        } else {
            let index = rng.gen_range(0, self.len());
            Some(self.swap_remove(index))
        }
    }
}

( Playground )