random - 我可以有效地从 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

唯一允许在恒定时间内进行均匀采样的数据结构是具有恒定时间索引访问的数据结构。 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 )