[Numpy-discussion] תשובה: faster in1d() for monotonic case?
Michael Katz
michaeladamkatz at yahoo.com
Tue Jun 21 11:15:50 EDT 2011
I'm not quite sure how to use searchsorted to get the output I need (e.g., the
length of the output needs to be as long as large_array). But in any case it
says it uses binary search, so it would seem to be an O( n * log( n ) )
solution, whereas I'm hoping for an O( n ) solution.
________________________________
From: Nadav Horesh <nadavh at visionsense.com>
To: Discussion of Numerical Python <numpy-discussion at scipy.org>
Sent: Tue, June 21, 2011 2:33:24 AM
Subject: [Numpy-discussion] תשובה: faster in1d() for monotonic case?
Did you try searchsorted?
Nadav
________________________________
מאת:numpy-discussion-bounces at scipy.org
[mailto:numpy-discussion-bounces at 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.python.org/pipermail/numpy-discussion/attachments/20110621/34999415/attachment.html>
More information about the NumPy-Discussion
mailing list