5

Scipy ( http://www.scipy.org/ ) 提供了两个 KD Tree 类；KDTree 和 cKDTree。

cKDTree 比 KDTree 快得多，但可定制性和可查询性较差（据我从文档中得知）。

这是我的问题： 我有一个包含 300 万个二维 (X,Y) 点的列表。我需要从每个点返回 X 个单位距离内的所有点。

使用 KDtree，有一个选项可以做到这一点：KDtree.query_ball_tree()它生成一个列表，其中包含 X 单位内的所有点与其他点的列表。但是：这个列表很大，很快就填满了我的虚拟内存（大约 7.44 亿条）。

潜在的解决方案#1：有没有办法在写入时将此列表解析为文本文件？

潜在解决方案#2：我尝试使用 for 循环（对于列表中的每个点），然后通过使用：KDtree.query_ball_point(). 但是：这需要很长时间，因为它需要运行数百万次查询。是否有与此 KDTree 工具等效的 cKDTree？

潜在的解决方案＃3：击败我，其他人有什么想法吗？

4

2 回答 2

4

从 scipy 0.12 开始，两个 KD Tree 类都具有特征奇偶性。引用其公告：

cKDTree 功能齐全

KDTree 的 Cython 版本，cKDTree，现在功能齐全。cKDTree 中的大多数操作（构造、查询、query_ball_point、query_pairs、count_neighbors 和 sparse_distance_matrix）比 KDTree 快 200 到 1000 倍。需要注意的是，cKDTree 与 KDTree 具有完全相同的界面，并且可以用作直接替代品。

于 2012-10-26T08:41:49.137 回答
1

尝试KDTree.query_ball_point改用。它需要一个点或点数组，并在输入点的给定距离内生成点。

您可以使用此功能执行批量查询。例如，一次给它 100000 个点，然后将结果写入文件。像这样的东西：

BATCH_SIZE = 100000
for i in xrange(0, len(pts), BATCH_SIZE):
    neighbours = tree.query_ball_point(pts[i:i+BATCH_SIZE], X)
    # write neighbours to a file...
于 2012-10-26T00:16:13.693 回答