近似比較大型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數組中值的最快方法？

回答

相關問題