[SciPy-User] get best few of many: argsort( few= ) using std::partial_sort ?
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