Scipy ( http://www.scipy.org/ ) 提供两个 KD 树类; KDTree 和 cKDTree。
cKDTree 速度要快得多,但与 KDTree 相比,可定制性和可查询性较差(据我从文档中得知)。
这是我的问题:
我有一个包含 300 万个二维 (X,Y) 点的列表。我需要从每个点返回 X 单位距离内的所有点。
使用 KDtree,有一个选项可以做到这一点:KDtree.query_ball_tree()
它从每隔一个点生成 X 单位内所有点的列表。然而:这个列表非常庞大,很快就会填满我的虚拟内存(大约 7.44 亿项)。
潜在解决方案#1:有没有办法在写入时将此列表解析为文本文件?
潜在解决方案#2:我尝试使用 for 循环(对于列表中的每个点),然后通过使用以下方法在 X 单位内找到该单点的邻居:KDtree.query_ball_point()
.然而:这需要永远,因为它需要运行查询数百万次。是否有与此 KDTree 工具等效的 cKDTree?
潜在解决方案#3:打败我,其他人有什么想法吗?
最佳答案
从 scipy 0.12 开始,两个 KD 树类都具有特征奇偶校验。引用其 announcement :
cKDTree feature-complete
Cython version of KDTree, cKDTree, is now feature-complete. Most operations (construction, query, query_ball_point, query_pairs, count_neighbors and sparse_distance_matrix) are between 200 and 1000 times faster in cKDTree than in KDTree. With very minor caveats, cKDTree has exactly the same interface as KDTree, and can be used as a drop-in replacement.
关于numpy - 优化 Python KD 树搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13079010/