[SciPy-User] get best few of many: argsort( few= ) using std::partial_sort ?

denis denis-bz-gg@t-online...
Fri Jul 9 11:13:02 CDT 2010



On Jul 9, 5:46 pm, Charles R Harris <charlesr.har...@gmail.com> wrote:
> On Fri, Jul 9, 2010 at 8:33 AM, denis <denis-bz...@t-online.de> wrote:
> > Folks,
> >  you've probably seenhttp://www.sgi.com/tech/stl/partial_sort.html
> > --
> >    sort uses the introsort algorithm and partial_sort uses heapsort
> >    introsort is usually faster by a factor of 2 to 5
>
> Sounds like partial_sort just sets up the heap and then pulls off the needed
> elements. That would make it about twice as fast as the normal heapsort for
> a small number of values, or about the same as a full quicksort.

Yes, at least in STLport  _algo.c -- not so hot.
What with factors of 2 from various *sort, arch, cache, inline
operator< vs lessf()
the possible gain of partial_sort is melting away ...

> > Heapsort fans: the normal pivot selector (without medians) is blind;
> > trying for a pivot near a small k/n percentile is fun.
>
> You mean quicksort?
yes, my mistake


More information about the SciPy-User mailing list