Boost logo

Boost :

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-06-30 16:45:47


Hi Steven,

I've had time to have a quick look at your code:

Steven Ross wrote:
> You are correct, I do require a comparison operator too (<). I assumed that,
> but it's good to make clear.

> I could sort fixed-point data, given a >> operator, which you should be able
> to implement. Here is what is needed for a hybrid MSB radix sort and
> introsort combo:
>
> bool operator <(const T &) : for comparison
> size_t operator -(const T & lhs, const T & rhs) : a - b > 0 -> b > a
> Note: - will always be used such that lhs >= rhs inside the algorithm.
> T operator >>(const T &) : to divide the values in a quick and efficient
> manner that will preserve ordering (a >> n) < (b >> n) -> a < b.

No, T T::operator>>(const T&) isn't what you're using; you need int
T::operator>>(int). The shift amount is obviously an integer, not T,
but furthermore you're using the result of the shift as a bin number.
So if my fixed-point class lets you say e.g. assert(3.1415 >> 2 ==
0.7854), i.e. it returns a T, then you can't use that to select a bin.

My fixed class provides a base() method to access the underlying
integer type, and somehow your algorithm needs to be supplied with a
functor that uses that base() method to extract the next few bits. I'm
not sure how best to do that: it's easy to solve for specific cases but
it's hard to be general without becoming so generic that the code is incomprehensible.

You can draw parallels with generating CRCs or hash functions for
arbitrary types [i.e. what tr1:: hash functions don't do]: you need a
simple concept that most types can satisfy for accessing their bit
patterns. In your case you also need that you get the bit patterns
with some sort of most-to-least significant ordering.

Anyway, I suggest that you get it looking good for integers first and
then we can all think about how to make it more generic. You might
also like to prepare some benchmarks so that we can see how fast it
really is and argue about the distribution of the values being sorted.
I have a nice big file of GPS coordinates you can try it on...

Oh, since no-one else has mentioned it, there was someone else who
proposed some sorting algorithms here a while ago. You might like to
have a look at the list archive (search for "sorting library") and see
what you can learn.

Phil.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk