3
\$\begingroup\$

I have sorted ascending number if you do abs(arr) in below code, I am trying to search for index where sign got changed from negative to positive. Wrote this below code, but for some reasons, I believe we can improve it or optimize more. Any tips and tricks ?

import numpy as np
arr = np.array([-1,-2,-3, 4, 5, 6])
_cut_index_1 = np.where(arr > 0)[0][0]
_cut_index_2 = np.where(arr < 0)[0][-1]
arr[_cut_index_1] # output:   4
arr[_cut_index_2] # output:  -3
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Your current solution does two passes over the input array (the two invocations of np.where) which as stated seems wasteful. One simple way to solve the problem is to use np.argmax which will take linear time:

import numpy as np
arr = np.array([-1, -2, -3, 4, 5, 6])
np.argmax(arr > 0) # Return (index) 3

At this point, if we can assume (as you seem to imply) that there is a single position of interest (and/or that we only care about the first one, read from left to right) we are done: just decrement one from the answer and you have the other cut-off point (but do check whether we are at a corner case so as not to return a non-valid index).

But in fact, if you can safely assume that the input is sorted, you can avoid doing a linear scan and not even read the whole input. For this, you can do a binary search via searchsorted. Theoretically, this is faster (i.e., logarithmic vs. linear in the worst case) but in practice this will depend on the size of the array. That is, for small enough arrays a linear scan will be faster due to cache locality (or, at least, that should be the case modulo your hardware details).

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.