[Numpy-discussion] Find the N maximum values and corresponding indexes in an array

Charles R Harris charlesr.harris@gmail....
Wed Dec 2 19:44:16 CST 2009


On Wed, Dec 2, 2009 at 6:32 PM, Anne Archibald <peridot.faceted@gmail.com>wrote:

> 2009/12/2 David Warde-Farley <dwf@cs.toronto.edu>:
> > On 2-Dec-09, at 8:09 PM, Neal Becker wrote:
> >
> >> Not bad, although I wonder whether a partial sort could be faster.
> >
> > Probably (if the array is large) but depending on n, not if it's in
> > Python. Ideal problem for Cython, though.
>
> How is Cython support for generic types these days? One wouldn't want
> to have to write separate versions for each dtype...
>
>
It could be made part of the _sortmodule without much trouble, but if you
are looking at the lower 30% I doubt it would do much more that buy you a
factor of 2x. Would that matter? folks mostly think of using partial sorts
for finding medians and such where it is essentially linear time. I've
thought of implementing it for the next release.

Re heapsort, heapsort is already the slowest sort by about a factor of 2,
and that is about the best case savings you could get using it for finding
some small percentage of the smallest values. Half the time is spent
building the heap.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/numpy-discussion/attachments/20091202/15d928fd/attachment-0001.html 


More information about the NumPy-Discussion mailing list