Re: [boost] Anyone downloaded the sorting library from vault?

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-17 15:54:22

On March 17, Lewis Hyatt wrote
 > > Are you sure about the quicksort speed difference? That seems like a
huge
> > difference. Did you have inlining enabled? Also, the current versions
are
> > not the final forms. I am implementing random-access iterators and
> > user-provided functions.
>
> Yes, this was on cygwin compiled with g++ -O3. One thing to keep in mind
is that
> your routines are competing with the standard library, which can be highly
> optimized for whatever target platform the compiler was written for.
Unless you
> have a dramatically improved algorithm, it is unlikely that your sorting
> routines will beat std::sort in general, even if they do on some
platforms.
>
> As an example, suppose your goal was to write an equivalent of std::bitset
which
> beat the standard implementation. It is unlikely that you could exceed the
> performance of std::bitset::count(), for instance, because most
implementations
> use native assembly instructions to do this whenever possible. ( e.g., gcc
uses
> its built-in popcount function on platforms where it is available.) On the
other
> hand, if you hand-coded a version with the best algorithm you could find,
it
> might beat a few poor implementations, but in general it would be
inferior. The
> only way to make it better in general would be to implement all these
> optimizations yourself for each target platform, but at that point, it's
just
> not worth the time.
>
> I don't think it's true that std::sort, std::stable_sort, and
std::partial_sort
> are the end of the story, but I think any work in a sorting library should
focus
> on needs which are not already met. So far, only radix sort appears to
fall in
> that category, but you would also need to demonstrate a case in which
radix sort
> is preferable to std::sort.
>
>
> -lewis
Well, one place where radix sort is preferable to std::sort is where you
need to "sort within a sort", where you sort by one criteria, then by
another. You do this by arranging the criteria so that the most influencial
is at the top of a byte sequence, and the least influential is at the bottom
of a byte sequence. Then you sort using radixsort and it comes out sorted by
criteria #1 and the by criteria #2. You can do the same with radix quicksort
but in that case all of the criteria is in a string. That, and radixsort is
stable, and faster than std::stable_sort. Finally, radixsort runs in linear
time, regardless of the input, so you can sort any data without worrying
about whether it is sorted or not, yet nearly as fast or as fast as
std::sort.