[Numpy-discussion] max argmax combo

Francesc Altet faltet at carabos.com
Wed Sep 20 05:00:20 CDT 2006

```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
"-"

```