पाइथन

Question

में किसी दिए गए बिंदु के निकटतम बिंदु को खोजने का सबसे तेज़ तरीका तो मान लें कि मेरे पास बी में 10,000 अंक और बी में 10,000 अंक हैं और प्रत्येक बी बिंदु के लिए ए में निकटतम बिंदु ढूंढना चाहते हैं।

वर्तमान में, मैं बस बी और ए में हर बिंदु के माध्यम से लूप करता हूं यह पता लगाने के लिए कि कौन सा दूरी निकटतम है। अर्थात।

B = [(.5, 1, 1), (1, .1, 1), (1, 1, .2)] 
A = [(1, 1, .3), (1, 0, 1), (.4, 1, 1)] 
C = {} 
for bp in B: 
    closestDist = -1 
    for ap in A: 
     dist = sum(((bp[0]-ap[0])**2, (bp[1]-ap[1])**2, (bp[2]-ap[2])**2)) 
     if(closestDist > dist or closestDist == -1): 
     C[bp] = ap 
     closestDist = dist 
print C 

हालांकि, मुझे यकीन है कि ऐसा करने का एक तेज़ तरीका है ... कोई विचार?

Answer 1

मैं आमतौर पर ऐसी स्थितियों में kd-tree का उपयोग करता हूं।

एक C++ implementation wrapped with SWIG and bundled with BioPython है जो उपयोग करना आसान है।

Answer 2

आप कुछ स्थानिक लुकअप संरचना का उपयोग कर सकते हैं। एक साधारण विकल्प octree है; fancier में BSP tree शामिल हैं।

Answer 3

आप numpy प्रसारण का उपयोग कर सकते हैं। उदाहरण के लिए,

from numpy import * 
import numpy as np 

a=array(A) 
b=array(B) 
#using looping 
for i in b: 
    print sum((a-i)**2,1).argmin() 

2,1,0 जो एक में पंक्तियों बी के 1,2,3 पंक्तियों के सबसे करीब हैं, क्रमशः प्रिंट होगा।

अन्यथा, आप प्रसारण का उपयोग कर सकते हैं:

z = sum((a[:,:, np.newaxis] - b)**2,1) 
z.argmin(1) # gives array([2, 1, 0]) 

मुझे आशा है कि मदद करता है।