help!: optimization of search problem (example code)
eric at enthought.com
Thu Feb 14 23:16:09 CET 2002
> after some days of playing around I am not getting
> any further and have to ask for some more help.
> Here is my problem. I have two large lists ("la" and "lb") of tuples.
> Each tuple represents a point in space and has four entries:
> x, y, z, pointID
> Now I have to find out for each point of list "la" which point of
> "lb" is closest. The result should be for all points of "la":
> Point 123 of "lb" is the closest one to Point 5932 of "la"
> where 123 and 5932 is the pointID.
SciPy has a vector quantization module that does what your looking for and
it is pretty fast.
500 points ran in 0.037537 seconds
from scipy import *
from scipy.cluster.vq import vq
from RandomArray import random
N = 500
a = random((N,3))*100
b = random((N,3))*100
index = arange(N)[:,NewAxis]
t1 = time.clock()
indices,distortion = vq(la[:,:3],lb[:,:3])
t2 = time.clock()
print '%d points ran in %f seconds' % (N,t2 - t1)
#print 'points in a are closet to the following points in b:'
Hope that helps,
More information about the Python-list