[Numpy-discussion] A question about argmax and argsort

Tom Denniston tom.denniston at alum.dartmouth.org
Wed Dec 20 17:02:41 CST 2006


If you want the n largest item i would recommend quicksort but at each
partition you only recurse into the side of the pivot that has the
values you care about.   This is easy to determine because you know
how many items are on either side of the pivot and you know that you
want the nth item.  This makes it take N+1/2N +1/4N... time, which
telscopes to 2N or O(N) rather than n log(n) of sorting algorithms.
I've found empirically this beats the pants of quicksorting and taking
the nth value.

I don't know of a way to do this in numpy.  I think it would require
adding a cfunction to numpy.  Perhaps an "argnth" function?

Does anyone else know of an existing mechanism?

On 12/12/06, asaf david <asafdav2 at gmail.com> wrote:
> Hello
> Let's say i have an N sized array, and i want to get the positions of the K
> largest items. for K = 1 this is simply argmax. is there any way to
> generalize it for k !=1? currently I use argsort and take only K items from
> it, but I'm paying an additional ~lg(N)...
>
> Thanks in advance, asaf
>
>
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at scipy.org
> http://projects.scipy.org/mailman/listinfo/numpy-discussion
>
>
>


More information about the Numpy-discussion mailing list