用法

将以下内容添加到您的Cargo.toml中

[dependencies]
thinset = "0.1"

描述

基于Briggs和Torczon于1993年发表的论文《稀疏集合的有效表示》实现的集合和映射，使用一对稀疏和密集数组作为后端存储。

当需要高效地跟踪来自大型宇宙的整数集合成员资格，但值相对分散时，此类集合很有用。

与标准库中的HashSet相比，清除集合是O(1)而不是O(n)。与基于位图的集合相比，集合的迭代与集合的基数（您拥有的元素数量）成比例，而不是与集合的最大大小成比例。

主要缺点是集合比其他集合实现使用更多的内存。

映射的行为与集合相同，除了它跟踪存储在集合中的值之外。在底层，SparseSet是键到值的SparseMap。

下表比较了稀疏集合与位图集合的几个集合操作的渐近复杂度。n是集合中的元素数量，而u是集合宇宙的大小。

基准测试

以下基准测试是在2020年MacBook Pro上运行的，该电脑配备2 GHz英特尔酷睿i5处理器。

基准测试比较了SparseSet与标准库中的HashSet以及bit-set crate的BitSet。

当从[0, 2^16)宇宙中插入1000个随机元素到集合中，然后迭代集合时，稀疏集合比HashSet快4.1倍，比BitSet快1.7倍。

• SparseSet: 160,329 ns/iter (+/- 55,664)
• BitSet: 278,428 ns/iter (+/- 42,477)
• HashSet：每迭代662,964纳秒（±56,851）

基准测试文件位于 examples/bench.rs，可以使用以下命令运行：

cargo run --example bench

示例

use thinset::SparseSet;

let mut s: SparseSet<usize> = SparseSet::new();
s.insert(0);
s.insert(3);
s.insert(7);

s.remove(7);

if !s.contains(7) {
    println!("There is no 7");
}

// Print 0, 1, 3 in some order
for x in s.iter() {
    println!("{}", x);
}

use thinset::{Pair, SparseMap};

let mut m: SparseMap<u32, u32> = SparseMap::new();

m.insert(13, 2);
m.insert(8, 16);

assert_eq!(m.get(13), Some(&2));
assert_eq!(m.get(6), None);

for Pair {key, value} in m.iter() {
    println!("{key}:{value}");
}

许可证

双许可，以兼容 Rust 项目。

许可协议为 Apache 许可证第 2 版：[https://apache.ac.cn/licenses/LICENSE-2.0](https://apache.ac.cn/licenses/LICENSE-2.0)，或者 MIT 许可证：[http://opensource.org/licenses/MIT](http://opensource.org/licenses/MIT)，任选其一。