[Numpy-discussion] max argmax combo

[Francesc Altet]

A Dimarts 19 Setembre 2006 21:41, Bill Baxter va escriure:
> I think he meant do an argsort first, then use fancy indexing to get
> the sorted array.
> For a 1-d array that's just
>
>   ind = A.argsort()
>   Asorted = A[ind]
>
> That should be O(N lg N + N), aka O(N lg N)

I see. Thanks.  OTOH, maybe your estimations are right, but the effect of the 
constants in these O(whatever) estimations can be surprisingly high:

In [3]: from timeit import Timer

In [4]: Timer("b=numpy.argsort(a);c=a[b]", "import numpy; 
a=numpy.arange(100000,-1,-1)").repeat(3,100)
Out[4]: [1.6653108596801758, 1.670341968536377, 1.6632120609283447]

In [5]: Timer("b=numpy.argsort(a);c=numpy.sort(a)", "import numpy; 
a=numpy.arange(100000,-1,-1)").repeat(3,100)
Out[5]: [1.6533238887786865, 1.6272940635681152, 1.6253311634063721]

In [6]: Timer("b=numpy.argsort(a);a.sort();c=a", "import numpy; 
a=numpy.arange(100000,-1,-1)").repeat(3,100)
Out[6]: [0.95492100715637207, 0.90312504768371582, 0.90426898002624512]

so, it seems that argsorting first and fancy indexing later on is the most 
expensive procedure for relatively large arrays (100000).

Interestingly, figures above seems to indicate that in-place sort is 
stunningly fast:

In [7]: Timer("a.sort()","import numpy; 
a=numpy.arange(100000,-1,-1)").repeat(3,100)
Out[7]: [0.32840394973754883, 0.2746579647064209, 0.2770991325378418]

and much faster indeed than fancy indexing

In [8]: Timer("b[a]","import numpy; 
a=numpy.arange(100000,-1,-1);b=a.copy()").repeat(3,100)
Out[8]: [0.79876089096069336, 0.74172186851501465, 0.74209499359130859]

i.e. in-place sort seems 2.7x faster than fancy indexing (at least for these 
datasets).

Mmmm, with this, I really ponder if a combo that makes the argsort() and 
sort() in one shot really makes any sense, at least from the point of view of 
speed:

In [10]: Timer("b=numpy.argsort(a);a.sort();c=a","import numpy; 
a=numpy.arange(100000,-1,-1)").repeat(3,100)
Out[10]: [0.98506593704223633, 0.89880609512329102, 0.89982390403747559]

In [11]: Timer("b=numpy.argsort(a)","import numpy; 
a=numpy.arange(100000,-1,-1)").repeat(3,100)
Out[11]: [0.92959284782409668, 0.85385990142822266, 0.87773990631103516]

So, it seems that doing an in-place sort() immediately after an argsort() 
operation is very efficient (cache effects here?), and would avoid the need 
of the combo function (from the point of view of efficiency, I repeat).

Cheers,

-- 
>0,0<   Francesc Altet     http://www.carabos.com/
V   V   Cárabos Coop. V.   Enjoy Data
 "-"