15个版本
使用旧的Rust 2015
| 0.6.6 | 2017年2月24日 |
|---|---|
| 0.6.5 | 2017年2月20日 |
| 0.5.0 | 2017年1月6日 |
| 0.4.8 | 2016年12月12日 |
#917 在 数据结构 中
180KB
3.5K SLoC
teardown_tree
一个用Rust编写的BST（二叉搜索树），支持高效的查询和拆解场景，即典型使用模式是首先构建一个树的副本，然后
- 将主副本克隆到一个新树中
- 通过一系列删除范围操作来拆解树（并对检索到的项进行处理），中间穿插范围查询
- 重复以上步骤
目前实现了两种数据结构： TeardownTree 和 IntervalTeardownTree（一个增强的区间树），它们都具有传统的Map和Set接口。
该树不使用任何类型的自平衡，也不支持插入操作。
详细信息
该树是隐式的，这意味着节点不存储指向其子节点的显式指针。节点中存储的唯一东西是你的数据。这与二叉堆的工作方式类似：树中的所有节点都位于一个数组中，根始终在索引0处，给定索引为i的节点，其左右子节点位于索引2*i+1和2*i+2。因此不需要动态内存分配或释放。这使得实现快速 clone 操作成为可能：我们不需要遍历树，为每个节点分配和复制，我们能够通过单个调用分配整个数组并高效地复制全部内容。该树还支持一个 refill 操作（目前仅针对T: Copy），它将主树的内容复制到self中而不进行任何分配。
至于 delete-range 操作，我们使用一个自定义算法，其运行时间为O(k + log n)，其中k是要删除（并返回）的项目数量，n是树的初始大小。 详细描述。
针对 delete-range 的彻底自动化测试已经编写并位于lib.rs。我已经测试了所有大小为n=10的树。所有其他支持的操作都针对树的每个变体进行了广泛的测试（我们对IntervalTree和过滤变体使用略微不同的算法）。总的来说，我感觉质量已经相当不错。如果您发现任何错误，请提交问题。
根据性能分析，该库已经针对速度进行了优化，并使用了大量不安全的代码。每个不安全代码的出现都经过仔细审查，大多数都添加了注释来详细说明安全性。
使用方法
作为一个库
运行基准测试
- 安装Rust和Cargo（任何近期版本均可，稳定版或nightly版）。
- git clone https://github.com/kirillkh/rs_teardown_tree.git
- cd rs_teardown_tree/benchmarks
- cargo run --release
性能
复杂度
所有查询和删除操作都在时间复杂度为 O(k + log n) 内完成，其中 k 是查询、删除或返回的项目数量，而n是树的初始大小。注意，如果您已经删除了m项，下一个 delete_range 操作仍然需要 O(n) 的时间，而不是像许多其他数据结构那样的 O(n-m) 时间。然而，这种区别仅在实践中当 delete 操作与 insert 操作交替出现时才有意义，而 TeardownTree 不支持 insert 操作。
使用 n 项，每项大小为 s 的 TeardownTree 消耗的内存量是s字节，其中 z 是一个小常数。（第一个术语是仅存储您数据的数组的大小；第二个是未设置已删除项的标志数组的大小；第三个是用于内部删除范围算法的两个辅助数组的大小）。n*s + n + 2*log_2(n) + zbytes, where z is a small constant. (The first term is the size of an array holding just your data; the second -- of an array of flags that are unset for removed items; the third -- of two auxiliary arrays used internally by the delete_range algorithm).
基准测试
第一组基准测试比较了TeardownTree::delete_range()与
I对Treap和SplayTree进行了简单修改以添加对 delete_range 的支持，然而BTreeSet缺少一个等效操作（它有一个O(log n) split,但没有merge,请参见 Rust #34666），因此BTreeSet::remove()被使用。
如图所示，在我的机器上，对包含1,000,000个u64项的树的整个填充/拆卸序列（我们使用主副本中的元素填充树，然后每次删除1000个元素，直到树为空），使用TeardownTreeSet<usize>::delete_range()比使用BTreeSet<usize>::remove()快约20倍。它还消耗45%的更少内存。
另一组基准测试揭示了数据结构和其算法的几个变体的开销。
有关详细信息，请参阅 基准测试页面。
缺点
- 无插入操作（尚未？..）
- 存储只有在结构被丢弃时才会解除分配。
- 关于复杂度的注意事项delete_range的工作在O(k + log n)，其中n是树的初始大小，而不是其当前大小（如果您已经删除了m项，下一个delete_range操作在最坏情况下仍然需要 O(log n) 的时间，而不一定是 O(log(n-m))）。同样适用于其他对数操作。
- 性能对您的数据大小敏感。从某个大小开始，使用 TeardownSet<Box<(Key,Value)>> 或将键值对分别存储并使用外部句柄作为键（例如 TeardownSet<INDEX_INTO_EXTERNAL_VEC> 或 TeardownSet<&MyKey>）可能更快。运行一些基准测试以确定您的最佳选择可能是一个好主意。
依赖项
~2.5MB
~48K SLoC