[Numpy-discussion] distance matrix speed (original) (raw)

Tim Hochberg tim.hochberg at cox.net
Fri Jun 16 09:17:53 EDT 2006

Sebastian Beca wrote:

Hi, I'm working with NumPy/SciPy on some algorithms and i've run into some important speed differences wrt Matlab 7. I've narrowed the main speed problem down to the operation of finding the euclidean distance between two matrices that share one dimension rank (dist in Matlab):

Python: def dtest(): A = random( [4,2]) B = random( [1000,2]) d = zeros([4, 1000], dtype='f') for i in range(4): for j in range(1000): d[i, j] = sqrt( sum( (A[i] - B[j])**2 ) ) return d Matlab: A = rand( [4,2]) B = rand( [1000,2]) d = dist(A, B') Running both of these 100 times, I've found the python version to run between 10-20 times slower. My question is if there is a faster way to do this? Perhaps I'm not using the correct functions/structures? Or this is as good as it gets? Here's one faster way.

    from numpy import *
    import timeit
   
    A = random.random( [4,2])
    B = random.random( [1000,2])
   
    def d1():
        d = zeros([4, 1000], dtype=float)
        for i in range(4):
            for j in range(1000):
                d[i, j] = sqrt( sum( (A[i] - B[j])**2 ) )
        return d

    def d2():
        d = zeros([4, 1000], dtype=float)
        for i in range(4):
            xy = A[i] - B
            d[i] = hypot(xy[:,0], xy[:,1])
        return d

    if __name__ == "__main__":
        t1 = timeit.Timer('d1()', 'from scratch import d1').timeit(100)
        t2 =timeit.Timer('d2()', 'from scratch import d2').timeit(100)
        print t1, t2, t1 / t2

In this case, d2 is 50x faster than d1 on my box. Making some extremely dubious assumptions about transitivity of measurements, that would implt that d2 is twice as fast as matlab.

Oh, and I didn't actually test that the output is correct....

-tim

Thanks on beforehand,

Sebastian Beca Department of Computer Science Engineering University of Chile PD: I'm using NumPy 0.9.8, SciPy 0.4.8. I also understand I have ATLAS, BLAS and LAPACK all installed, but I havn't confirmed that.

Numpy-discussion mailing list Numpy-discussion at lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/numpy-discussion

More information about the NumPy-Discussion mailing list