3 个稳定版本
| 1.1.1 | 2024 年 6 月 22 日 |
|---|---|
| 1.0.1 | 2024 年 6 月 8 日 |
| 1.0.0 | 2024 年 5 月 25 日 |
703 在 数据结构 中
73KB
1K SLoC
稀疏集合容器
基于稀疏集合的容器。
如果您需要一个性能接近 Vec 的容器，同时又要安全地存储元素的索引（以便在删除时不会失效），则非常有用。
例如，您有一个用户可以添加和删除元素的 UI 元素列表，但您希望从其他地方引用该列表的元素。
使用方法
将以下内容添加到您的 Cargo.toml 中
[dependencies]
sparse_set_container = "1.1"
描述
一个类似于数组的基于稀疏集合实现的容器，它允许 O(1) 访问元素，无需哈希，并允许缓存友好的迭代。
| 操作 | SparseSet | Vec |
|---|---|---|
| push | O(1) | O(1) |
| lookup | O(1) | O(1) |
| size/len | O(1) | O(1) |
| remove | O(n) | O(n) |
| swap_remove | O(1) | O(1) |
为了遍历元素，SparseSet 提供了一个对内部 Vec 的迭代器，其效率与直接遍历 Vec 相当。
与 Vec 的区别
- 添加元素时，它返回一个轻量级键结构，可用于稍后访问元素，而不是使用索引
- 在从容器中删除元素时，键不会被失效
- 如果指向的元素已被删除，即使插入新元素，键也不会指向其他元素
- 与 Vec 相比，插入/查找/删除操作有轻微的性能开销
- 消耗更多内存
- 每个值在元素本身的大小之上额外消耗
4*sizeof(usize)字节- (例如，在 64 位系统上每个元素为 32 字节)
- 对于每次
2^(sizeof(usize)*8)删除，内存消耗也将增加2*sizeof(usize)- 例如（在64位系统上，删除18446744073709551616个元素需要16字节）
- 每个值在元素本身的大小之上额外消耗
- 许多Vec操作不支持（如果您想请求一个，请在GitHub上创建一个问题）
示例
extern crate sparse_set_container;
use sparse_set_container::SparseSet;
fn main() {
let mut elements = SparseSet::new();
elements.push("1");
let key2 = elements.push("2");
elements.push("3");
elements.remove(key2);
elements.push("4");
if !elements.contains(key2) {
println!("Value 2 is not in the container");
}
// Prints 1 3 4
for v in elements.values() {
print!("{} ", v);
}
// Prints 1 3 4
for k in elements.keys() {
print!("{} ", elements.get(k).unwrap());
}
}
基准测试
用于说明SparseSet容器实现、Vec和标准HashMap之间差异的值
| 基准测试 | SparseSet<字符串> |
Vec<字符串> |
HashMap<i32, 字符串> |
|---|---|---|---|
| 创建空 | 0 ns ±0 | 0 ns ±0 | 1 ns ±0 |
| 带有容量创建 | 17 ns ±0 | 16 ns ±0 | 32 ns ±1 |
| 推送100个元素 | 3,254 ns ±14 | 2,553 ns ±23 | 5,493 ns ±85 |
| 带有容量推送100 | 3,286 ns ±30 | 3,156 ns ±106 | 4,388 ns ±21 |
| 查找100个元素 | 88 ns ±2 | 39 ns ±14 | 464 ns ±3 |
| 遍历100个元素 | 30 ns ±0 | 30 ns ±0 | 41 ns ±1 |
| 带有100个元素的克隆 | 2,184 ns ±23 | 2,109 ns ±4 | 1,490 ns ±32 |
| 克隆100并删除10 | 3,055 ns ±107 | 2,364 ns ±97 | 1,692 ns ±145 |
| 克隆100并交换删除10 | 2,475 ns ±119 | 2,193 ns ±67 | 不适用 |
要在您的机器上运行基准测试，请执行以下命令：cargo run --example bench --release
或者，要构建此表格，您可以运行 python tools/collect_benchmark_table.py 然后在 bench_table.md 中查找结果
许可证
MIT许可证下授权： http://opensource.org/licenses/MIT