作者:mobiledu2502859367 | 来源:互联网 | 2022-11-16 12:18
我的算法需要通过删除元素来迭代地收缩集合,并在每次迭代中删除元素并使用收缩集做一些事情.和:
我需要一个快速查找的真实集合,而不仅仅是包含唯一元素的向量.
元素的选择是任意的:算法的结果不依赖于访问的顺序.性能可能与该选择有很大不同,但是假设我想要最简单的代码并将其留给集合本身以选择它可以有效移除的元素.
顺便说一下,我的算法是Bron-Kerbosch算法的基本形式.该算法的更智能版本工作得更快(大部分),因为他们不会选择任意元素,我想知道这种努力能带来多少回报.
Python集合的pop
成员几乎就是这样做的.在Scala和Go中,选择和删除哈希集的"第一个"元素似乎工作正常(其中"first"对应于迭代器).在Rust中,这类似于:
// split off an arbitrary element from a (non-empty) set
pub fn pop(set: &mut HashSet) -> T
where
T: Eq + Clone + std::hash::Hash,
{
let elt = set.iter().next().cloned().unwrap();
set.remove(&elt);
elt
}
与其他语言相比,这似乎是一个性能瓶颈.我在操场上对一些类似pop的函数的一些实现进行了基准测试,但没有一个表现良好.显然删除一个元素并不昂贵,但选择一个元素是:iter().next()
花费一大笔钱.可以retain
理解地避免这种情况并没有帮助:它总是迭代整个集合.还有其他选择吗?