檢查座標的接近程度在一個組與另一個

{(x1,y1),..(xn,yn)}
{(w1,z1),..(wn,zn)}

，我想在第2組的每對匹配於所述一對在它最接近的組1中。我的團隊很大，因此搜索需要高效。任何建議設置這將不勝感激。此外，如果我有兩組第一組= {(x1,y1,z1),..(xn,yn,zn)}和第二組= {(u1,v1, w1),..(un,vn,wn)}，我的答案會有什麼不同？此外，考慮到我的團隊太大而無法存儲在計算機上，因此，有關克服此問題的任何建議將不勝感激。

來源

2017-09-01 user2468702

我不認爲你可以做得比計算每個組合的距離和檢查最小的組合的距離好得多。這就要求你計算'n'個物體的距離'n'次，所以需要'n^2'計算來計算距離。如果你的數據集真的像你說的那麼大，那麼你基本上可以忘記在接下來的幾千年內完成的這些計算。 – Zinki

你知道關於點的範圍和分佈嗎？ – Prune

@Prune嗨 - 沒有什麼特別瞭解座標的範圍和分佈。高效搜索算法應該適用於任何用戶指定的n值。以及如何處理極大的數據集。希望對此有任何工作示例。謝謝。 – user2468702

您可以使用一個KDTree：該算法允許有效地找到最近的鄰居，大大減少了比較次數。「KD」代表「k維」，意思是它可以處理任意維度的數據（回答你最後一個問題）。

您可以使用其中一個列表構建樹，然後爲另一個列表的每個元素查詢最近的元素。 Scipy提供了一個implementation for ktrees。

來源

2017-09-01 19:05:24 Batsu

謝謝你的回覆。你能給出一個小的最小工作示例，可以推廣到任何大小爲n的座標嗎？還有關於我的後續問題的任何建議？ – user2468702

看起來您希望我們爲您編寫一些代碼。儘管許多用戶願意爲遇險的編碼人員編寫代碼，但他們通常只在海報已嘗試自行解決問題時才提供幫助。展示這一努力的一個好方法是包含一個[最小，完整，可驗證的示例]（http://stackoverflow.com/help/mcve）。查看[intro tour]（https://stackoverflow.com/tour），尤其是[如何提問]（http://stackoverflow.com/help/how-to-ask）。 – Prune

檢查座標的接近程度在一個組與另一個

回答

相關問題