Best match searching

[Terry Reedy]

"Daniel Pryde" <ababo_2002 at hotmail.com> wrote in message
news:mailman.3.1072700087.8134.python-list at python.org...
> 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. :-)

If the values in the array have any structure or constraints, try to
exploit that.  If they are ordered in both directions, use binary search on
one axis and then trace the zigzag frontier between lower and height
values.  If there are just a 'few' values (as in 0-255), then a dict might
work, though changing values would complicate this.

Terry J. Reedy