我可以有效地从HashSet弹出吗？

Question

我的算法需要通过删除元素来迭代地收缩集合,并在每次迭代中删除元素并使用收缩集做一些事情.和:

• 我需要一个快速查找的真实集合,而不仅仅是包含唯一元素的向量.
• 元素的选择是任意的:算法的结果不依赖于访问的顺序.性能可能与该选择有很大不同,但是假设我想要最简单的代码并将其留给集合本身以选择它可以有效移除的元素.
• 顺便说一下,我的算法是Bron-Kerbosch算法的基本形式.该算法的更智能版本工作得更快(大部分),因为他们不会选择任意元素,我想知道这种努力能带来多少回报.

Python集合的pop成员几乎就是这样做的.在Scala和Go中,选择和删除哈希集的"第一个"元素似乎工作正常(其中"first"对应于迭代器).在Rust中,这类似于:

// split off an arbitrary element from a (non-empty) set
pub fn pop<T>(set: &mut HashSet<T>) -> T
where
    T: Eq + Clone + std::hash::Hash,
{
    let elt = set.iter().next().cloned().unwrap();
    set.remove(&elt);
    elt
}

与其他语言相比,这似乎是一个性能瓶颈.我在操场上对一些类似pop的函数的一些实现进行了基准测试,但没有一个表现良好.显然删除一个元素并不昂贵,但选择一个元素是:iter().next()花费一大笔钱.可以retain理解地避免这种情况并没有帮助:它总是迭代整个集合.还有其他选择吗？

Answer 1

我使用的集合有整数

不要使用HashSet; ABTreeSet具有更好和更一致的性能。

对于N= 100000...

BTreeSet

sequenced : 3065.098µs
pop_1     : 2941.876µs
pop_2     : 2927.429µs

HashSet

sequenced : 3091.454µs
pop_1     : 172547.080µs
pop_2     : 807182.085µs

Answer 2

我想同样的建议也适用于我可以有效地从 HashSet 中随机采样吗？：将集合复制为向量只是为了对其进行迭代，如基准测试中的“序列”解决方案所示：

let seq: Vec<u32> = set.iter().cloned().collect();
for elt in seq {
    set.remove(&elt);

这意味着如果您只需要缩小集合（选择任意元素）一次或几次，或者集合内容无法廉价克隆，则此答案不适用。