help!: optimization of search problem (example code)

eric jones eric at
Thu Feb 14 17:16:09 EST 2002

> Hi,
> 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
import time

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:'
#print indices

Hope that helps,

More information about the Python-list mailing list