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

Francesc Alted falted at pytables.org
Thu May 20 01:31:02 CDT 2004


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=numarray.arange(1000*1000)
>>> nu=Numeric.arange(1000*1000)
>>> t1=time();numarray.searchsorted(na,200*1000);time()-t1
200000
0.00055098533630371094
>>> t1=time();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=time();bisect.bisect_left(na,200*1000);time()-t1
200000
8.8930130004882812e-05
>>> t1=time();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.
From the python 2.3.3 sources:

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

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

Cheers,

-- 
Francesc Alted





More information about the Numpy-discussion mailing list