[Numpy-discussion] תשובה: faster in1d() for monotonic case?

Nadav Horesh nadavh@visionsense....
Tue Jun 21 04:33:24 CDT 2011

Did you try searchsorted?


מאת: numpy-discussion-bounces@scipy.org [mailto:numpy-discussion-bounces@scipy.org] בשם Michael Katz
נשלח: Tuesday, June 21, 2011 10:06
אל: Discussion of Numerical Python
נושא: [Numpy-discussion] faster in1d() for monotonic case?

The following call is a bottleneck for me:

    np.in1d( large_array.field_of_interest, values_of_interest )

I'm not sure how in1d() is implemented, but this call seems to be slower than O(n) and faster than O( n**2 ), so perhaps it sorts the values_of_interest and does a binary search for each element of large_array?

In any case, in my situation I actually know that field_of_interest increases monotonically across the large_array. So if I were writing this in C, I could do a simple O(n) loop by sorting values_of_interest and then just checking each value of large_array against values_of_interest[ i ] and values_of_interest[ i + 1 ], and any time it matched values_of_interest[ i + 1 ] increment i.

Is there some way to achieve that same efficiency in numpy, taking advantage of the monotonic nature of field_of_interest?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/numpy-discussion/attachments/20110621/a4cc550e/attachment.html 

More information about the NumPy-Discussion mailing list