2个不稳定版本
使用旧Rust 2015
0.2.0 | 2017年1月2日 |
---|---|
0.1.0 | 2016年12月29日 |
#2118 在 算法 中
用于 kd-tree
34KB
711 行
kdtree-rust
rust的kdtree实现。
实现使用了树的滑动中点变化。更多信息请参考 这里 实现使用单个 Vec<Node>
来存储所有内容,允许快速访问,并且没有内存碎片。
###使用
pub trait KdtreePointTrait : Copy {
fn dims(&self) -> &[f64];
}
树只能与实现了特质的类型一起使用
通过这个特质,您可以使用任何维度。请注意,当前树仅支持3D及以下 #2。
pub struct Point3WithId {
dims: [f64; 3],
pub id: i32,
}
impl KdtreePointTrait for Point3WithId {
#[inline] // the inline on this method is important! as without it there is ~25% speed loss on the tree when cross-crate usage.
fn dims(&self) -> &[f64] {
return &self.dims;
}
}
示例实现如下
其中id只是我携带数据的一种方式。
let tree = kdtree::kdtree::Kdtree::new(&mut points.clone());
//test points pushed into the tree, id should be equal.
for i in 0 .. point_count {
let p = &points[i];
assert_eq!(p.id, tree.nearest_search(p).id );
}
有了这个特质的实现,您就可以使用这个树了。请注意,kdtree不是自平衡树,它确实支持使用'method insert_node'添加节点,并且确实有代码可以重建树,如果深度显著增长。基本用法可以在集成测试中找到,下面是部分代码
虽然不推荐,但您可以使用 insert_node
和 insert_nodes_and_rebuild
函数向树中添加节点。 insert_node
会进行愚蠢的检查,检查是否应该重建树。 insert_nodes_and_rebuild
会自动重建树。
目前不支持节点的删除。
running 3 tests
test bench_creating_1000_000_node_tree ... bench: 275,155,622 ns/iter (+/- 32,713,321)
test bench_adding_same_node_to_1000_tree ... bench: 42 ns/iter (+/- 11)
test bench_creating_1000_node_tree ... bench: 120,310 ns/iter (+/- 4,746)
test bench_single_lookup_times_for_1000_node_tree ... bench: 164 ns/iter (+/- 139)
test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured
##基准测试 cargo bench
使用travis :)
~275ms 创建一个包含1000_000个节点的树。 << 这个基准测试现在已经禁用。
~120us 创建一个包含1000个节点的树。
### 性能基准 - 与 CGAL 的比较。由于原始值并没有说明太多,我创建了一个基准来比较这个实现与 CGAL。基准测试的代码可在以下链接找到:https://github.com/fulara/kdtree-benchmarks
Benchmark Time CPU Iterations
-----------------------------------------------------------------
Cgal_tree_buildup/10 2226 ns 2221 ns 313336
Cgal_tree_buildup/100 18357 ns 18315 ns 37968
Cgal_tree_buildup/1000 288135 ns 287345 ns 2369
Cgal_tree_buildup/9.76562k 3296740 ns 3290815 ns 211
Cgal_tree_buildup/97.6562k 42909150 ns 42813307 ns 12
Cgal_tree_buildup/976.562k 734566227 ns 733267760 ns 1
Cgal_tree_lookup/10 72 ns 72 ns 9392612
Cgal_tree_lookup/100 95 ns 95 ns 7103628
Cgal_tree_lookup/1000 174 ns 174 ns 4010773
Cgal_tree_lookup/9.76562k 268 ns 267 ns 2759487
Cgal_tree_lookup/97.6562k 881 ns 876 ns 1262454
Cgal_tree_lookup/976.562k 993 ns 991 ns 713751
Rust_tree_buildup/10 726 ns 724 ns 856791
Rust_tree_buildup/100 7103 ns 7092 ns 96132
Rust_tree_buildup/1000 84879 ns 84720 ns 7927
Rust_tree_buildup/9.76562k 1012983 ns 1010856 ns 630
Rust_tree_buildup/97.6562k 12406293 ns 12382399 ns 51
Rust_tree_buildup/976.562k 197175067 ns 196763387 ns 3
Rust_tree_lookup/10 62 ns 62 ns 11541505
Rust_tree_lookup/100 139 ns 139 ns 4058837
Rust_tree_lookup/1000 220 ns 220 ns 2890813
Rust_tree_lookup/9.76562k 307 ns 307 ns 2508133
Rust_tree_lookup/97.6562k 362 ns 362 ns 2035671
Rust_tree_lookup/976.562k 442 ns 441 ns 1636130
Rust_tree_lookup 存在一些开销,因为库是从 C 代码调用 Rust 的,并且在中间也有轻微的开销,我的经验表明大约有 50 纳秒的开销。
## 许可证 The Unlicense