Best match searching

[anton muhin]

Daniel Pryde wrote:

> Hi everyone.
> I was wondering if anyone might be able to help me out here. I'm 
> currently looking to find the quickest way to find a best fit match in a 
> large array.
> My problem is that I have an array of, say, 600*400, which contains a 
> value at each point, and I need to find the value in that array which is 
> closest to the input value. It's basically some euclidean distances that 
> I've calculated, and I need to be able to find the best matches over a 
> large number of input values, so I was looking for a speedy solution to 
> this.
> The array is implemented simply using a list of lists. The only solution 
> I could think of is to use some for statements, but that seems to take a 
> while, even for just one search.
> Any hints or tips would be really helpful. :-)
> 
> Daniel
> 
> _________________________________________________________________
> Express yourself with cool new emoticons 
> http://www.msn.co.uk/specials/myemo
> 
> 
  I'm not an expert, but I'd use numarray module. The most simple 
example can look like:

a = numarray.array(....) # An array to look in
value = x # Value to look for
c = a.copy() # Create a copy
print numarray.abs(a.copy() - value).argmin() # Finds minimal absolute 
difference

If performance of numarray is still too slow, I'd resort to simple 
hasing scheme: you can split your inputs in reasonable ranges and look 
for closest match only in this ranges.

hth,
anton.