I added the keyword side to the searchsorted method and functions. Documentation:
"""a.searchsorted(values=v, side='left') -> array of indices.
Required Arguments:
v -- keys to be searched for in a.
Keyword arguments
side -- {'left', 'right'}, default('left').
If a is a 1-D array in ascending order, then
a.searchsorted(v, side='left')
returns an array of indices i such that for each element of values the
following holds:
a[j] < key <= a[i] for all j < i,
If such an index does not exist, a.size() is used. The result is such that
if the key were to be inserted in the slot before the index i, then the
order of a would be preserved and i would be the smallest index with that
property.
If a is a 1-D array in ascending order, then
a.searchsorted(v, side='right')
returns an array of indices i such that for each element of values the
following holds:
a[j] <= key < a[i] for all j < i,
If such an index does not exist, a.size() is used. The result is that if the
key were to be inserted in the slot before the index i, then the order of a
would be preserved and i would be the largest index with that property.
"""
I also replaced the old search routine as it was linear time worst case:
In [27]: t1 = t.Timer('N.searchsorted(a,1,side="left")','import numpy as N; a = N.ones(1000000)')
In [28]: t2 = t.Timer('N.searchsorted(a,1,side="right")','import numpy as N; a = N.ones(1000000)')
In [29]: t1.repeat(3,100)
Out[29]: [0.5301368236541748, 0.4924161434173584 , 0.46317386627197266]
In [30]: t2.repeat(3,100)
Out[30]: [0.0011379718780517578, 0.00081586837768554688, 0.00083994865417480469]
where left was the original routine. It is now noticeably faster in some situations:
In [2]: t1 = t.Timer('N.searchsorted(a,1,side="left")','import numpy as N; a = N.ones(1000000)')
In [3]: t1.repeat(3,100)
Out[3]: [0.00082802772521972656, 0.00077795982360839844 , 0.00076913833618164062]
I am open to suggestions as to better names for the keyword kind. It also might be worth it to make type-specific routines if anyone commonly uses large lists of keys and large sorted arrays.
Chuck
------------------------------------------------------------------------- Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________ Numpy-discussion mailing list Numpy-discussion@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/numpy-discussion
