我可以有效地从 HashSet 中随机采样吗？

问题描述 投票：0回答：4

我有一个

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 ...
random rust hashset
4个回答
6
投票

唯一允许在恒定时间内进行均匀采样的数据结构是具有恒定时间索引访问的数据结构。 

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))
        }
    }
}

(游乐场)

5
投票

考虑 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()
    }
}
2
投票

Sven 的答案建议将 

HashSet
转换为 
Vec
，以便在 O(1) 时间内从 
Vec
中随机采样。此转换需要 O(n) 时间，如果只需少量转换，则适合；例如，用于从其他不变的哈希集中获取一系列随机样本。如果需要经常进行转换，例如，如果在随机采样之间，想要从 
HashSet
中散布一些 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<T, usize>
和 
Vec<T>
，这样 
Vec
将索引（即 
usizes
）映射到 
T
，而 
HashMap
将 
T
映射到 
usizes
。 
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();
                // 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.
}
2
投票

根据HashSet::iter的

文档
，它返回“以任意顺序访问所有元素的迭代器。”

任意可能并不完全是均匀的随机性，但如果它足够接近您的用例，则这是 O(1) 并且每次都会返回不同的值：

// 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，似乎每次都会产生相同的结果。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.