我有一个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 ...
考虑 Sven Marnach 的答案，我想使用向量，但也需要在不重复的情况下进行常数时间插入。然后我意识到我可以同时维护一个向量和一个集合，并确保它们始终具有相同的元素。这将允许常数时间插入和去重以及常数时间的随机删除。
这是我最终实现的代码：
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()
}
}
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))
}
}
}
// Build a set of integers 0 - 99
let mut set = HashSet::new();
for i in 0..100 {
set.insert(i);
}
// Sample
for _ in 0..10 {
let n = set.iter().next().unwrap().clone();
println!("{}", n);
set.remove(&n);
}
和作者一样，我想从HashSet中删除采样后的值。通过这种方式多次采样，而不改变HashSet，似乎每次都会得到相同的结果。
BijectiveFiniteSequence。（请注意`take_random_val`方法；它在O(1)时间内运行。）use std::collections::HashMap;
use rand::{thread_rng, Rng};
#[derive(Clone, Debug)]
struct BijectiveFiniteSequence<T: Eq + Copy + Hash> {
idx_to_val: Vec<T>,
val_to_idx: HashMap<T, usize>,
}
impl<T: Eq + Copy + Hash> BijectiveFiniteSequence<T> {
fn new () -> BijectiveFiniteSequence<T> {
BijectiveFiniteSequence {
idx_to_val: Vec::new(),
val_to_idx: HashMap::new()
}
}
fn insert(&mut self, val: T) {
self.idx_to_val.push(val);
self.val_to_idx.insert(val, self.len()-1);
}
fn take_random_val(&mut self) -> Option<T> {
let mut rng = thread_rng();
let rand_idx: usize = rng.gen_range(0..self.len());
self.remove_by_idx(rand_idx)
}
fn remove_by_idx(&mut self, idx: usize) -> Option<T> {
match idx < self.len() {
true => {
let val = self.idx_to_val[idx];
let last_idx = self.len() - 1;
self.idx_to_val.swap(idx, last_idx);
self.idx_to_val.pop();
// update hashmap entry after the swap above
self.val_to_idx.insert(self.idx_to_val[idx], idx);
self.val_to_idx.remove(&val);
Some(val)
},
false => None
}
}
fn remove_val(&mut self, val: T) -> Option<T> {
//nearly identical to the implementation of remove_by_idx,above
match self.contains(&val) {
true => {
let idx: usize = *self.val_to_idx.get(&val).unwrap();
let last_idx = self.len() - 1;
self.idx_to_val.swap(idx, last_idx);
self.idx_to_val.pop();
// update hashmap entry after the swap above
self.val_to_idx.insert(self.idx_to_val[idx], idx);
self.val_to_idx.remove(&val);
Some(val)
}
false => None
}
}
fn get_idx_of(&mut self, val: &T) -> Option<&usize> {
self.val_to_idx.get(val)
}
fn get_val_at(&mut self, idx: usize) -> Option<T> {
match idx < self.len() {
true => Some(self.idx_to_val[idx]),
false => None
}
}
fn contains(&self, val: &T) -> bool {
self.val_to_idx.contains_key(val)
}
fn len(&self) -> usize {
self.idx_to_val.len()
}
// etc. etc. etc.
}
swap_remove，与您的swap(last)和pop相同。可能会稍微好一点（2次复制而不是3次）。 - undefineduse hashbrown::HashSet;
use rand::prelude::*;
use std::hash::Hash;
fn remove_random<T, R>(set: &mut HashSet<T>, rng: &mut R) -> Option<T>
where
R: Rng,
T: Eq + PartialEq + Hash,
{
if set.is_empty() {
return None;
}
// If load factor is under 25%, shrink to fit.
// We need a high load factor to ensure that the sampling succeeds in a reasonable time,
// and the table doesn't rebalance on removals.
// Insertions can only cause the load factor to reach as low as 50%,
// so it's safe to shrink at 25%.
if set.capacity() >= 8 && set.len() < set.capacity() / 4 {
set.shrink_to_fit();
}
let raw_table = set.raw_table_mut();
let num_buckets = raw_table.buckets();
// Perform rejection sampling: Pick a random bucket, check if it's full,
// repeat until a full bucket is found.
loop {
let bucket_index = rng.gen_range(0..num_buckets);
// Safety: bucket_index is less than the number of buckets.
// Note that we return the first time we modify the table,
// so raw_table.buckets() never changes.
// Also, the table has been allocated, because set is a HashSet.
unsafe {
if raw_table.is_bucket_full(bucket_index) {
let bucket = raw_table.bucket(bucket_index);
let ((element, ()), _insert_slot) = raw_table.remove(bucket);
return Some(element);
}
}
}
}
Cargo.toml 文件：[dependencies]
hashbrown = { version = "^0.14.2", features = ["raw"] }
rand = "^0.8.5"