How to make this speed up

[Carl Banks]

myang 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)

Two obvious things.  First, you say these are all 3D points, so
there's not much point being general here.  It is faster to get rid of
the loop and just calculate the distance directly.  Second, the **
operator seems to be a bit slower than multiplication, so when speed
matters, you should multiply instead of raise powers if you can.

So I would define distance as:

    def distance(a,b):
        x = a[0] - b[0]
        y = a[1] - b[1]
        z = a[2] - b[2]
        return sqrt(x*x + y*y + z*z)


> for i in range(len(plist)):
>    for j in range(i+1,len(plist)):
>        d = distance(plist[i],plist[j])

Function calls are rather expensive in Python.  It would be much
faster to calculate the distance right here, rather than call a
function to do it.  (Being that the distance formula is simple, it's
probably not necessary to abstract it in a function.)


> But this is damn slow. Do you have any suggestion to speed it up? 

Numeric and/or numarray.  These are some extension modules designed to
do the math stuff a lot faster (numarray will supercede Numeric).
Try Google.


> 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 :(

It could be a lot faster.  I would say the best tradeoff is to write
whole loop (not just the distance function) in C.


-- 
CARL BANKS                      http://www.aerojockey.com/software
"If you believe in yourself, drink your school, stay on drugs, and
don't do milk, you can get work." 
          -- Parody of Mr. T from a Robert Smigel Cartoon