Sven的答案建议将HashSet转换为Vec,以便在O(1)时间内从Vec中随机采样。此转换需要O(n)时间,如果只偶尔需要进行转换,例如从一个不变的哈希集合中取一系列随机样本,则适用。如果需要经常进行转换,例如在取随机样本之间,想要插入一些通过值进行O(1)删除的操作,则较不适用,因为这将涉及在HashSet和Vec之间来回转换,每次转换需要O(n)时间。
isaacg的解决方案是同时保留HashSet和Vec,并对它们进行操作。这允许通过索引进行O(1)查找,O(1)随机删除和O(1)插入,但不能进行O(1)值查找或O(1)值删除(因为Vec无法完成这些操作)。
下面是一种数据结构,它允许按索引或值O(1)查找,O(1)插入和O(1)删除:
它是一个`HashMap`和一个`Vec`的组合,其中`Vec`将索引(即`usizes`)映射到 `T`,而`HashMap`将`T`映射到`usize`。可以将`HashMap`和`Vec`视为彼此的
反函数,以便您可以从索引转到其值,并从值返回到其索引。插入和删除操作的定义使得索引恰好是从0到size()-1的整数,不允许存在空缺。我称这种数据结构为
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();
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> {
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();
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()
}
}