nearest neighbor in 2D

[Peter Otten]

Alex Martelli wrote:

> Andrew Dalke wrote:
> 
>> Ron Adam
>>> for point in p:
>>>     distance = math.sqrt((new_point[0]-point[0])**2 \
>>>                          +(new_point[1]-point[1])**2)
>> 
>>> I really don't know how you can make this faster.  There might be a
> 
> Hmmm, that's what math.hypot is for, isn't it...?
> 
> [alex at lancelot Lib]$ timeit.py -c -s'import math; p=1.6,2.5; np=2.4,1.3'
> 'math.sqrt((np[0]-p[0])**2 + (np[1]-p[1])**2)'
> 100000 loops, best of 3: 3 usec per loop
> 
> [alex at lancelot Lib]$ timeit.py -c -s'import math; p=1.6,2.5; np=2.4,1.3'
> 'math.hypot(np[0]-p[0], np[1]-p[1])'
> 100000 loops, best of 3: 1.9 usec per loop
> 
> 
>>> library that has a distance between two points function that could
>>> speed it up.
>> 
>> An easy way is to move the math.sqrt call outside the loop, since
>>  sqrt(d1) < sqrt(d2) iff d1 < d2 (when d1,d2>=0)
> 
> Yes, omitting the math.sqrt gives the same speed as calling math.hypot,
> and it's the classic solution to speed up minimum-distance problems.
> 
> I vaguely suspect you could shave some further fraction of a microsecond
> by saving those differences as dx and dy and then computing dx*dx+dy*dy --
> since another classic tip is that a**2 is slower than a*2.  Let's see...:
> 
> [alex at lancelot Lib]$ timeit.py -c -s'import math; p=1.6,2.5; np=2.4,1.3'
> 'dx=np[0]-p[0]; dy=np[1]-p[1]; disq=dx*dx+dy*dy'
> 1000000 loops, best of 3: 1.39 usec per loop
> 
> ...yep, another small enhancement.  Ain't measuring _FUN_?-)

Finally found an application for complex numbers:

...> timeit.py -s"p= 1.6+2.5j; np=2.4+1.3j" "d=abs(p-np)"
1000000 loops, best of 3: 0.436 usec per loop

...> timeit.py -s"p= 1.6,2.5; np=2.4,1.3" "dx=np[0]-p[0];
dy=np[1]-p[1];d=dx*dx+dy*dy"
1000000 loops, best of 3: 1.15 usec per loop

This is of course all premature optimization as the most promising approach
is to try hard to reduce the number of candidate points, as David Eppstein
seems to have done. But then, he could use complex numbers, too.

Peter