Vectorized searchsorted numpy

by

We can add each row some offset as compared to the previous row. We would use the same offset for both arrays. The idea is to use np.searchsorted on flattened version of input arrays thereafter and thus each row from b would be restricted to find sorted positions in the corresponding row in a. Additionally, to make it work for negative numbers too, we just need to offset for the minimum numbers as well.

So, we would have a vectorized implementation like so –

def searchsorted2d(a,b):
    m,n = a.shape
    max_num = np.maximum(a.max() - a.min(), b.max() - b.min()) + 1
    r = max_num*np.arange(a.shape[0])[:,None]
    p = np.searchsorted( (a+r).ravel(), (b+r).ravel() ).reshape(m,-1)
    return p - n*(np.arange(m)[:,None])

Runtime test –

In [173]: def searchsorted2d_loopy(a,b):
     ...:     out = np.zeros(a.shape,dtype=int)
     ...:     for i in range(len(a)):
     ...:         out[i] = np.searchsorted(a[i],b[i])
     ...:     return out
     ...: 

In [174]: # Setup input arrays
     ...: a = np.random.randint(11,99,(10000,20))
     ...: b = np.random.randint(11,99,(10000,20))
     ...: a = np.sort(a,1)
     ...: b = np.sort(b,1)
     ...: 

In [175]: np.allclose(searchsorted2d(a,b),searchsorted2d_loopy(a,b))
Out[175]: True

In [176]: %timeit searchsorted2d_loopy(a,b)
10 loops, best of 3: 28.6 ms per loop

In [177]: %timeit searchsorted2d(a,b)
100 loops, best of 3: 13.7 ms per loop

More Related Contents:

  1. Bin elements per row – Vectorized 2D Bincount for NumPy
  2. Vectorizing Haversine distance calculation in Python
  3. Efficient evaluation of a function at every cell of a NumPy array
  4. Efficiently replace elements in array based on dictionary – NumPy / Python
  5. Most efficient way to map function over numpy array
  6. Performance of Pandas apply vs np.vectorize to create new column from existing columns
  7. numpy: most efficient frequency counts for unique values in an array
  8. What is vectorization? [closed]
  9. Why is numpy’s einsum faster than numpy’s built in functions?
  10. Roll rows of a matrix independently
  11. Numpy sum elements in array based on its value
  12. Is it possible to vectorize recursive calculation of a NumPy array where each element depends on the previous one?
  13. Efficiently return the index of the first value satisfying condition in array
  14. Most efficient way to forward-fill NaN values in numpy array
  15. Numpy: Fix array with rows of different lengths by filling the empty elements with zeros
  16. Using Numpy Vectorize on Functions that Return Vectors
  17. Why np.hypot and np.subtract.outer very fast compared to vanilla broadcast ? Using Numba for speedup numpy in parallel for distance matrix calculation
  18. Python vectorizing nested for loops
  19. Why is numpy.array so slow?
  20. Efficiently Calculating a Euclidean Distance Matrix Using Numpy
  21. Fastest save and load options for a numpy array
  22. Python Numpy Data Types Performance
  23. how to speed up a vector cross product calculation
  24. Getting days since last occurence in Pandas DataFrame?
  25. What is the most efficient way to check if a value exists in a NumPy array?
  26. numpy array TypeError: only integer scalar arrays can be converted to a scalar index
  27. Efficient dot products of large memory-mapped arrays
  28. Numpy Broadcast to perform euclidean distance vectorized
  29. Numpy: argmax over multiple axes without loop
  30. What is the most efficient way of doing square root of sum of square of two numbers?

Leave a Comment