more efficient way to calculate distance in numpy?

by

Whenever you have multiplications and sums, try to use one of the dot product functions or np.einsum. Since you are preallocating your arrays, rather than having different arrays for horizontal and vertical coordinates, stack them both together:

precomputed_flat = np.column_stack((svf.flatten(), shf.flatten()))
measured_flat = np.column_stack((VVmeasured.flatten(), HHmeasured.flatten()))
deltas = precomputed_flat - measured_flat[:, None, :]

From here, the simplest would be:

dist = np.einsum('ijk,ijk->ij', deltas, deltas)

You could also try something like:

from numpy.core.umath_tests import inner1d
dist = inner1d(deltas, deltas)

There is of course also SciPy’s spatial module cdist:

from scipy.spatial.distance import cdist
dist = cdist(precomputed_flat, measured_flat, 'euclidean')

EDIT
I cannot run tests on such a large dataset, but these timings are rather enlightening:

len_a, len_b = 10000, 1000

a = np.random.rand(2, len_a)
b =  np.random.rand(2, len_b)
c = np.random.rand(len_a, 2)
d = np.random.rand(len_b, 2)

In [3]: %timeit a[:, None, :] - b[..., None]
10 loops, best of 3: 76.7 ms per loop

In [4]: %timeit c[:, None, :] - d
1 loops, best of 3: 221 ms per loop

For the above smaller dataset, I can get a slight speed up over your method with scipy.spatial.distance.cdist and match it with inner1d, by arranging data differently in memory:

precomputed_flat = np.vstack((svf.flatten(), shf.flatten()))
measured_flat = np.vstack((VVmeasured.flatten(), HHmeasured.flatten()))
deltas = precomputed_flat[:, None, :] - measured_flat

import scipy.spatial.distance as spdist
from numpy.core.umath_tests import inner1d

In [13]: %timeit r0 = a[0, None, :] - b[0, :, None]; r1 = a[1, None, :] - b[1, :, None]; r0 *= r0; r1 *= r1; r0 += r1
10 loops, best of 3: 146 ms per loop

In [14]: %timeit deltas = (a[:, None, :] - b[..., None]).T; inner1d(deltas, deltas)
10 loops, best of 3: 145 ms per loop

In [15]: %timeit spdist.cdist(a.T, b.T)
10 loops, best of 3: 124 ms per loop

In [16]: %timeit deltas = a[:, None, :] - b[..., None]; np.einsum('ijk,ijk->jk', deltas, deltas)
10 loops, best of 3: 163 ms per loop

More Related Contents:

  1. What is the difference between contiguous and non-contiguous arrays?
  2. Python 32-bit memory limits on 64bit windows
  3. Python out of memory on large CSV file (numpy)
  4. How to increase Jupyter notebook Memory limit?
  5. Is freeing handled differently for small/large numpy arrays?
  6. Python/Numpy MemoryError
  7. How can I explicitly free memory in Python?
  8. String concatenation of two pandas columns
  9. Intuition and idea behind reshaping 4D array to 2D array in NumPy
  10. Find column name in pandas that matches an array
  11. Reshape an array in NumPy
  12. binning data in python with scipy/numpy
  13. How do I count the occurrence of a certain item in an ndarray?
  14. Transform a set of numbers in numpy so that each number gets converted into a number of other numbers which are less than it
  15. Calculating Pearson correlation and significance in Python
  16. ValueError: could not broadcast input array from shape (224,224,3) into shape (224,224)
  17. How to split a numpy array in fixed size chunks with and without overlap?
  18. how to read certain columns from Excel using Pandas – Python
  19. Why does numpy.linalg.solve() offer more precise matrix inversions than numpy.linalg.inv()?
  20. load csv into 2D matrix with numpy for plotting
  21. Pandas in AWS lambda gives numpy error
  22. Create numpy matrix filled with NaNs
  23. How to fix ‘Object arrays cannot be loaded when allow_pickle=False’ for imdb.load_data() function?
  24. Shuffling NumPy array along a given axis
  25. How to display progress of scipy.optimize function?
  26. Fitting a Weibull distribution using Scipy
  27. Large Performance difference when summing ints vs floats in Cython vs NumPy
  28. Shift rows of a numpy array independently
  29. Formatting floats in a numpy array [duplicate]
  30. Add density curve on the histogram

Leave a Comment