[Numpy-discussion] argsort speed

[Charles R Harris]

On Sun, Feb 16, 2014 at 4:18 PM, <josef.pktd at gmail.com> wrote:

> On Sun, Feb 16, 2014 at 6:15 PM,  <josef.pktd at gmail.com> wrote:
> > On Sun, Feb 16, 2014 at 5:50 PM, Eelco Hoogendoorn
> > <hoogendoorn.eelco at gmail.com> wrote:
> >>
> >> My guess;
> >>
> >> First of all, you are actually manipulating twice as much data as
> opposed to
> >> an inplace sort.
> >>
> >> Moreover, an inplace sort gains locality as it is being sorted, whereas
> the
> >> argsort is continuously making completely random memory accesses.
> >>
> >>
> >> -----Original Message-----
> >> From: josef.pktd at gmail.com
> >> Sent: Sunday, February 16, 2014 11:43 PM
> >> To: Discussion of Numerical Python
> >> Subject: [Numpy-discussion] argsort speed
> >>
> >> currently using numpy 1.6.1
> >>
> >> What's the fastest argsort for a 1d array with around 28 Million
> >> elements, roughly uniformly distributed, random order?
> >>
> >> Is there a reason that np.argsort is almost 3 times slower than np.sort?
> >>
> >> I'm doing semi-systematic timing for a stats(models) algorithm.
> >
> > I was using np.sort, inplace sort is only a little bit faster
> >
> > It looks like sorting first, and then argsorting is faster than argsort
> alon
> >
> > pvals.sort()
> > sortind = np.argsort(pvals)
>
> Ok, that was useless, that won't be anything I want.
>
>
I think locality is the most important thing. The argsort routines used to
move both the indexes and the array to argsort, the new ones only move the
indexes. It is a tradeoff, twice as many moves vs locality. It's probably
possible to invent an algorithm that mixes the two.

<snip>

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20140216/5cb0ba4e/attachment.html>