1 个不稳定版本
| 新功能 0.1.2 | 2024 年 8 月 22 日 |
|---|---|
| 0.1.1 |
|
| 0.1.0 |
|
#587 在 数据结构 中
99KB
2.5K SLoC
interval_map
interval_map 是基于区间树的数据结构。它完全实现了红黑树插入和删除功能，确保每次修改操作最多需要 $O(logN)$ 时间复杂度。
interval_map 中区间树的实现参考了 "算法导论"（第 3 版，第 14.3 节：区间树，第 348-354 页）。
为了在 Rust 中安全高效地处理插入和删除操作，interval_map 创新性地 使用数组来模拟指针，用于管理红黑树中的父子引用。这种方法也确保了 interval_map 具有代码Send 和 Unpin 特性，允许它在线程之间安全传输，并在异步操作期间保持固定的内存位置。
interval_map 实现了一个 IntervalMap 结构体
- 它接受
Interval<T>作为键，其中T可以是任何实现Ord特性的类型。因此，允许区间如 $[1, 2)$ 和 $["aaa", "bbb")$ - 值可以是任何类型
interval_map 支持 insert、delete 和 iter 函数。遍历按 Interval<T> 的顺序进行。例如，对于类型 Interval<u32>
- $[1,4)<[2,5)$，因为 $1<2$
- $[1,4)<[1,5)$，因为 $4<5$
所以 IntervalMap 中区间的顺序是 $[1,4)<[1,5)<[2,5)$。
目前，interval_map 只支持半开区间，即 $[...,...)$。
基准测试
基准测试在一个具有 AMD R7 7840H + DDR5 5600MHz 的平台上进行。结果如下
- 只有插入
插入 100 1000 10, 000 100, 000 总时间 5.4168 µs 80.518 µs 2.2823 ms 36.528 ms - 插入 N 和删除 N
insert_and_remove 100 1000 10, 000 100, 000 总时间 10.333 µs 223.43 µs 4.9358 ms 81.634 ms
待办事项
-
支持$(...,...)$, $[...,...]$和$(...,...]$区间类型。目前无法支持这些区间类型而不影响性能。 -
为区间添加Point类型要支持Point类型，还应支持$[...,...]$，因此目前也无法支持。但您可以参考以下示例代码：examples/new_point。 - 添加更多测试，例如etcd。
- 优化iter模块。
依赖项
~165KB