優化Python KD樹搜索

Scipy（http://www.scipy.org/）提供了兩個KD樹類; KDTree和cKDTree。優化Python KD樹搜索

cKDTree快得多，但比KDTree更少定製和查詢能力（據我所知，文檔）。

這是我的問題： 我有一個3百萬2維（X，Y）點的列表。我需要返回距離每個點X個單位距離內的所有點。

使用KDtree，有一個選項可以做到這一點：KDtree.query_ball_tree()它生成一個從所有其他點的X單位內的所有點列表的列表。然而：這個清單是巨大的，並迅速填補我的虛擬內存（約744萬條項目長）。

潛在的解決方案＃1：有沒有一種方法來解析這個列表到一個文本文件，因爲它是在寫什麼？

潛在的解決方案＃2：我有一個for循環（列表中的每一個點），然後發現的X單元內單點的鄰國採用嘗試使用：KDtree.query_ball_point()。然而：這需要永久，因爲它需要數百萬次運行查詢。這個KDTree工具有相當於cKDTree的嗎？

潛在解決方案＃3：打我，任何人有任何想法？

來源

2012-10-25 Dlinet

從scipy 0.12開始，兩個KD樹類都具有功能奇偶性。引用其announcement：KDTree，cKDTree的

cKDTree功能完善

用Cython版本，現在是功能齊全。大多數操作（構造，查詢，query_ball_point，query_pairs， count_neighbors和sparse_distance_matrix）在cKDTree中比在KDTree中快200到1000 倍。對於非常小的警告， cKDTree與KDTree具有完全相同的界面，並且可以用作直接替換。

來源

2012-10-26 08:41:49 jorgeca

啊，那會很好。我沒有任何技術/經驗來自源代碼編譯，所以我可能會考慮這一點。否則，除非發佈另一個解決方案，否則我會等待scipy的新版本發佈。 – Dlinet

@Dlinet版本0.12上個月發佈。 – jorgeca

請嘗試使用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-26 00:16:13 nneonneo

除非我理解你錯了，我認爲這正是我列爲潛在解決方案＃2否？據我所知，這種方法的問題是需要永久。 – Dlinet

你的建議是循環每一個點。在這裏，我建議在「批處理」模式下使用它，這樣可以減少迭代次數。 – nneonneo

有趣的是，我會研究這個。我從未使用過「批次」。你是否建議瞭解更多關於批次的特定資源？ – Dlinet

優化Python KD樹搜索

回答

cKDTree功能完善

相關問題