python - 近似比较大型numpy数组中的值的最快方法？

Question

我有两个数组，数组 A 有 ~1M 行，数组 B 有 ~400K 行。除其他外，每个都包含一个点的坐标。对于数组 A 中的每个点，我需要找出数组 B 中有多少点在它的一定距离内。我如何避免天真地比较一切？根据它一开始的速度，在我的机器上天真地运行需要 10 多天。这需要嵌套循环，但数组太大而无法构建距离矩阵（400G 条目！）

我认为方法是仅针对每个 A 坐标检查一组有限的 B 坐标。但是，我还没有确定一个简单的方法来做到这一点。也就是说，进行不需要检查 B 中所有值的选择的最简单/最快的方法是什么（这与我试图避免的任务完全相同）？

编辑：我应该提到这些不是二维（或nD）笛卡尔，而是球面（纬度/经度），距离是大圆距离。

Answer 1

我现在无法给出完整的答案，但有一些提示可以帮助您入门。B在 kd-tree 中组织点会更有效率。您可以使用该类scipy.spatial.KDTree轻松完成此操作，并且您可以使用query()该类上的方法来请求给定距离内的点。

Answer 2

这是使用 kd 树在球体上的点列表之间进行交叉匹配的一种可能实现。 http://code.google.com/p/astrolibpy/source/browse/my_utils/match_lists.py

另一种方法是使用 healpy 模块及其 get_neighbors 方法。