पाइथन केडी ट्री सर्च को अनुकूलित करना

Question

सिसि (http://www.scipy.org/) दो केडी ट्री क्लास प्रदान करता है; केडीटी और सीकेडीटी।

सीकेडीटी बहुत तेज है, लेकिन केडीटी (जहां तक ​​मैं दस्तावेज़ों से कह सकता हूं) से कम अनुकूलन और क्वेरी-सक्षम है।

यहां मेरी समस्या है: मेरे पास 3 मिलियन 2 आयामी (एक्स, वाई) अंक की एक सूची है। मुझे हर बिंदु से एक्स इकाइयों की दूरी के भीतर सभी बिंदुओं को वापस करने की जरूरत है।

केडीटी के साथ, ऐसा करने का एक विकल्प है: KDtree.query_ball_tree() यह हर दूसरे बिंदु से एक्स इकाइयों के भीतर सभी बिंदुओं की सूचियों की सूची उत्पन्न करता है। हालांकि: यह सूची बहुत बड़ी है और जल्दी से मेरी वर्चुअल मेमोरी भरती है (लगभग 744 मिलियन आइटम लंबे)।

संभावित समाधान # 1: क्या इस सूची को पाठ फ़ाइल में लिखने के तरीके को पार्स करने का कोई तरीका है?

संभावित समाधान # 2: मैं पाश के लिए और उसके बाद की खोज (सूची में हर बिंदु के लिए) एक्स इकाइयों के भीतर एक बिंदु के पड़ोसियों का उपयोग करके है कि एक का उपयोग कर की कोशिश की है: KDtree.query_ball_point()। हालांकि: यह हमेशा के लिए लेता है क्योंकि इसे लाखों बार क्वेरी चलाने की आवश्यकता होती है। क्या इस केडीटी उपकरण के बराबर सीकेडीटी है?

संभावित समाधान # 3: मुझे मारता है, किसी और के पास कोई विचार है?

Answer 1

एससीडी ट्री वर्गों में दोनों के समानता समानता है। इसके announcement का हवाला देते हुए:,

cKDTree सुविधा पूरा

Cython KDTree, cKDTree के संस्करण अब पूर्ण सुविधा-संपन्न है। अधिकांश संचालन (निर्माण, क्वेरी, query_ball_point, query_pairs, count_neighbors और sparse_distance_matrix) KDTree की तुलना में सीकेडीटी में 200 से 1000 गुना तेज हैं। बहुत मामूली चेतावनी के साथ, सीकेडी ट्री के पास केडीटी के समान इंटरफेस है, और इसे ड्रॉप-इन प्रतिस्थापन के रूप में उपयोग किया जा सकता है।

Answer 2

इसके बजाय 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...