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

[Francesc A. <fa...@py...>]

Hi,

I'm willing to use a lot the searchsorted function in numarray, but I'm a
bit surprised about the poor performance of it. Look at that:

>>> from time import time
>>> import numarray
>>> import Numeric
>>> na=3Dnumarray.arange(1000*1000)
>>> nu=3DNumeric.arange(1000*1000)
>>> t1=3Dtime();numarray.searchsorted(na,200*1000);time()-t1
200000
0.00055098533630371094
>>> t1=3Dtime();Numeric.searchsorted(nu,200*1000);time()-t1
200000
7.7962875366210938e-05

It may seem that Numeric is better optimised, but the standard python module
bisect is even faster than numarray.searchsorted:

>>> import bisect
>>> t1=3Dtime();bisect.bisect_left(na,200*1000);time()-t1
200000
8.8930130004882812e-05
>>> t1=3Dtime();bisect.bisect_left(nu,200*1000);time()-t1
200000
8.6069107055664062e-05

So, bisect performance is similar to that of Numeric searchsorted and both
are almost an order of magnitude better than numarray searchsorted. This a
little bit surprising as the bisect_left module is written in plain python.
=46rom the python 2.3.3 sources:

def bisect_left(a, x, lo=3D0, hi=3DNone):
    if hi is None:
        hi =3D len(a)
    while lo < hi:
        mid =3D (lo+hi)//2
        if a[mid] < x: lo =3D mid+1
        else: hi =3D mid
    return lo

I'm using python2.3.3, numarray 0.9.1 (latest CVS) and Debian Linux (sid).

Cheers,

=2D-=20
=46rancesc Alted