# #最近邻搜索 #节点树 #维度 #搜索 #邻居 #最近

fux_kdtree

使用Rust实现的高效NN查询的K维树

2个不稳定版本

使用旧Rust 2015

0.2.0 2017年1月2日
0.1.0 2016年12月29日

#2118算法


用于 kd-tree

Unlicense协议

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_nodeinsert_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

无运行时依赖