How to make this speed up

[David M. Cooke]

At some point, "myang" <myang at clarku.edu> wrote:

> Hi,
>
> I have thousands of points in 3D space, and I want to calcuate the distance
> between each other of them. I do the calculation with the following code.
>
> def distance(a,b):
>     sum = 0
>     for i in range(len(a)):
>         sum += (a[i]-b[i])**2
>     return sqrt(sum)
>
> for i in range(len(plist)):
>     for j in range(i+1,len(plist)):
>         d = distance(plist[i],plist[j])
>
> But this is damn slow. Do you have any suggestion to speed it up? If I write
> the distance function in C extension, how faster will it be? (For the time
> being, I don't know how to write C extension yet :(

Use numarray or Numeric, and use arrays for your points. Also, do you
need the distance, or will the square of the distance do? (that'll
save you a sqrt).

import numarray as NA

def distance_between_points(plist):
    # if plist was a list of N points in d dimensions, p is an array of size (N,d)
    p = NA.asarray(plist)
    N, d = p.shape
    # dist2 is a (N,N) array of squared distance
    dist2 = NA.zeros((N, N), type=p.type())
    for i in range(d):
        dist2 += NA.subtract.outer(p[:,i],p[:,i])**2
    return NA.sqrt(dist2)

This should be almost as fast as writing your own C extension (and
much easier...)

-- 
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke
|cookedm(at)physics(dot)mcmaster(dot)ca