help!: optimization of search problem (example code)

[eric jones]

> 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.

C:\temp>python vq_ex.py
500 points ran in 0.037537 seconds

#vq_ex.py
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]

la=hstack((a,index))
lb=hstack((b,index))

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,
eric