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

Question

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

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

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
}

与其他语言相比，这似乎是一个性能瓶颈。我benchmarked some implementations of a pop-like function on the playground但没有表现良好。显然删除一个元素并不昂贵，但选择一个是：iter().next()花了一大笔钱（*）。使用retain可以理解地避免这种情况并没有帮助：它总是迭代整个集合。还有其他选择吗？

PS仔细检查，iter().next()相当便宜，到目前为止microbenchmarking可以信任。 Separate microbenchmarks说从设定成本中选择一个任意元素（在我的系统上以纳秒为单位）：

| Type of set      | Number of elements in set instance
|                  | 100 | 10,000 | 1,000,000
| Rust HashSet     |   2 |      2 |         2
| Rust BTreeSet    |  11 |     12 |        13
| Go map[]struct{} |  27 |     31 |        94
| Python set       | 125 |    125 |       125

Answer 1

我正在使用的集合有整数

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

对于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

我想同样的建议适用于Can I randomly sample from a HashSet efficiently?：将集合复制为向量，只是迭代它，如"sequenced" solution in the benchmark所示：

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

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

Answer 3

您的代码可以简化一下：

let elt = set.iter().next().cloned().unwrap();
set.take(&elt).unwrap()

如果你想从HashSet中删除所有元素，那么你应该使用drain迭代器 - 它非常有效。

来自Rust标准库的HashSet并不那么快。尝试用hashbrown箱子中的一个替换它。