kNN 算法的 kd 树实现（ C 源码）
begeekmyfriend · begeekmyfriend · 2017-02-22 19:14:56 +08:00 · 2137 次点击这是一个创建于 2825 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://github.com/begeekmyfriend/kdtree
特点：绝对平衡，搜索极快，代价是动态性差，每次增删后需要重建。
实现是对增删进行缓存，直到重建才映射到实际数据结构中去。重建会对每个维度分量进行快速排序，以确保每个树节点都是取中值，实现了绝对平衡，也即最小高度，最大限度降低搜索比较次数，杜绝最差情况发生。
注意，排序只是对数据样本的索引进行移动，数据本身插入时只拷贝一次，数据样本集中缓存有利于 cache 命中。
有兴趣欢迎探讨。
特点：绝对平衡，搜索极快，代价是动态性差，每次增删后需要重建。
实现是对增删进行缓存，直到重建才映射到实际数据结构中去。重建会对每个维度分量进行快速排序，以确保每个树节点都是取中值，实现了绝对平衡，也即最小高度，最大限度降低搜索比较次数，杜绝最差情况发生。
注意，排序只是对数据样本的索引进行移动，数据本身插入时只拷贝一次，数据样本集中缓存有利于 cache 命中。
有兴趣欢迎探讨。
 |
1
y8y 2017-02-22 19:17:20 +08:00
我是第一个赞的，楼主的 C 代码看起来很舒服。
|
 |
2
zgqq 2017-02-22 19:30:21 +08:00 via Android
大佬
|
 |
3
franklinyu 2017-02-23 01:47:55 +08:00
除了「 for(; ;)」和「 8 個空格縮進」屬於口味不同以外，樓主的代碼簡直是一股清流……
|
 |
4
congeec 2017-02-23 06:47:21 +08:00 via iPhone
正规军
|
 |
5
wujunze 2017-04-20 18:10:58 +08:00
👍
|
Select Language