[Numpy-discussion] finding close together points.

James Bergstra bergstrj@iro.umontreal...
Tue Nov 10 19:22:11 CST 2009


On Tue, Nov 10, 2009 at 8:17 PM, Christopher Barker
<Chris.Barker@noaa.gov> wrote:
> James Bergstra wrote:
>> In some cases a brute-force approach is also good.
>
> true.
>
>> If r is a matrix of shape Nx2:
>>
>> (r*r).sum(axis=1) -2 * numpy.dot(r, r.T) +
>> (r*r).sum(axis=1).reshape((r.shape[0], 1)) < thresh**2
>>
>> It's brute force, but it takes advantage of fast matrix multiplication.
>
> I'm more concerned about memory -- doesn't this use N^2 memory? Which
> could be an issue here.

Yes, this uses N^2 time and space.  It's not a good algorithm when N is large.

-- 
http://www-etud.iro.umontreal.ca/~bergstrj


More information about the NumPy-Discussion mailing list