[Numpy-discussion] Performance issues with numarray.searchsorted()

Francesc Alted falted at pytables.org
Thu May 20 10:42:05 CDT 2004


A Dijous 20 Maig 2004 19:13, vareu escriure:
> The first case agrees with your results of ~10x difference in favor of
> Numeric at 10**6 elements.  The last case shows a ~3x numarray advantage
> given large numbers of values.
> 
> My analysis is this:  since searchsorted runs in O(log2(N)) time,  even
> with 10**6 elements there are only 20 iterations or so.  This is just
> not enough to overcome numarray's Python ufunc overhead.  I'll see what
> I can do,  but I think we're up against the standard numarray
> performance wall for small arrays.	

I see. What about creating a special case for when the item to be searched
is an scalar (and not an array)? In such a case, it would be theoretically
possible to get at least the bisect.bisect() performance.

Besides, if this special case would be implemented, users would be able to
call repeatedly this scalar version of searchsorted() in order to deal with
very small "values" arrays (len()<5) and still having a gain.

Just a thought,

-- 
Francesc Alted





More information about the Numpy-discussion mailing list