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

我有两个阵列，阵列A〜1M行，阵列B〜400K行。除了别的以外，每一个都包含一个点的坐标。对于数组A中的每个点，我需要查找数组B中有多少点在它的某个距离内。我如何避免天真地比较一切事物？根据它的启动速度，天真地运行需要10天以上。这需要嵌套循环，但阵列太大，无法构造一个distance matrix（400G条目！）近似比较大型numpy数组中值的最快方法？

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

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

来源

2012-08-01 Tristan Klassen

您可以将每个记录排序到网格区域，只检查相关网格和周围的网格 - 这取决于您是否有最大距离？如果没有，你将不得不将它们全部进行比较。 – Basic 2012-08-01 18:40:17

是的，有一个最大距离（但请参阅编辑问题）。 – 2012-08-01 19:40:36

我解决了它分裂成纬度箱和检查每个垃圾箱本身和相邻垃圾箱。我认为这会很复杂，因为我认为首先（或仅仅）按经度排序，但仅按纬度排序可以提供足够的性能改进。 – 2012-08-09 21:50:42

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

来源

2012-08-01 18:43:48

以下是使用k-d树的球体上的点列表之间交叉匹配的一种可能的实现。 http://code.google.com/p/astrolibpy/source/browse/my_utils/match_lists.py

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

来源

2013-05-12 17:14:54

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

回答

相关问题