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

[Robert Kern]

Francesc Alted wrote:
> 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

A better timing (IMHO), but with similar conclusions:

Python 2.3 (#1, Sep 13 2003, 00:49:11)
[GCC 3.3 20030304 (Apple Computer, Inc. build 1495)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
 >>> import timeit
 >>> t1 = timeit.Timer("Numeric.searchsorted(a,200000)",
"import Numeric;a=Numeric.arange(1000000)")
 >>> t2 = timeit.Timer("numarray.searchsorted(a,200000)",
"import numarray;a=numarray.arange(1000000)")
 >>> t3 = timeit.Timer("bisect.bisect_left(a,200000)",
"import Numeric;import bisect;a=Numeric.arange(1000000)")
 >>> t4 = timeit.Timer("bisect.bisect_left(a,200000)",
"import numarray;import bisect;a=numarray.arange(1000000)")
 >>> t1.repeat(3,10000)
[0.15758609771728516, 0.17469501495361328, 0.15456986427307129]
 >>> t2.repeat(3,10000)
[6.7581729888916016, 6.9644770622253418, 6.6776731014251709]
 >>> t3.repeat(3,10000)
[0.41335701942443848, 0.45698308944702148, 0.39665889739990234]
 >>> t4.repeat(3,10000)
[0.49930000305175781, 0.48063492774963379, 0.52067780494689941]

[Apologies for the linewraps.]

I also get similar results with double arrays. Weird.

Python 2.3 on Mac OS X 10.3.sumthin', latest CVS checkout of numarray, 
Numeric 23.1.

-- 
Robert Kern
rkern at ucsd.edu

"In the fields of hell where the grass grows high
  Are the graves of dreams allowed to die."
   -- Richard Harter