From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-06-28 14:09:14
Steven Ross wrote:
> Would there be interest in an integer_sort call that is faster than std::sort?
> Spreadsort is an in-place hybrid radix-based and comparison-based algorithm with
> better worst-case and average-case (roughly 20-50%) performance than introsort
> on random integer data.
> The worst-case advantage is algorithmic, with Spreadsort taking the better of
> O(n(square_root(bit_sizeof(data) - log(n)))) and O(nlog(n)) time.
> For 32-bit integers, that's O(n(square_root(32 - log(n)))),
> so for a log(n) of 16 (65536 items), it's 4n (plus a small constant times n),
> vs 16n for introsort.
> For larger n, the advantage vs. pure comparison-based algorithms increases.
> In effect, Spreadsort smoothly transitions from pure MSB Radix sort to std::sort
> with its data cut up by a couple iterations of MSB Radix sort
> (reducing the size of the log(n) factor),
> depending upon the distribution and size of the data.
>
> I could write a templated version of Spreadsort for the Boost library if there
> is interest. It would work for anything that supports the << and - operators.
Yes, this would interest me. I have a fixed-point class that it could
probably be used with. I have a feeling that you need a little bit
more than just << and - though, don't you? Hmm, what would a (pure)
radix sort need? Presumably, since yours is a hybrid method, you need
everything that a comparison sort needs and everything that a radix
sort needs. Maybe we should start by implementing a (sketch of a)
radix sort template.
Johan mentioned sorting a vector of [pointers to] structs by some
member of that struct; I also have some wrappers around std::sort (e.g.
below) that do this and would be interested to see how you would
implement it.
template <typename obj_t, typename data_member_ptr_t>
struct compare_data_member {
data_member_ptr_t data_member_ptr;
compare_data_member(data_member_ptr_t data_member_ptr_):
data_member_ptr(data_member_ptr_)
{}
bool operator()(const obj_t& a, const obj_t& b)
{
return a.*data_member_ptr < b.*data_member_ptr;
}
};
template <typename iter_t, typename data_member_ptr_t>
void sort_by(iter_t begin, iter_t end, data_member_ptr_t
data_member_ptr) {
std::sort(begin,end,
compare_data_member<typename iter_t::value_type,
data_member_ptr_t> (data_member_ptr));
}
> It could also handle standard floats sorted as integers.
what exactly do you mean by this? As I understand it, if you treat an
IEEE float as an integer for sorting it will almost work but the
negative range will be backwards; you need to do some sign-mag vs.
2s-comp fixup to allow for it. But I bet std::c++ doesn't guarantee
anything along those lines.
> Functors supporting << and - could make it more general.
> Multi-dimensional sorting is also sped up by Spreadsort.
> I could also write a similar string_sort, that should also be significantly
> faster than std::sort. This would look much like postal sort, just using
> introsort after a certain number of iterations.
> Is this of interest?
Yes, that too. I'm particularly interested in
algorithmically-efficient sorting of strings that frequently have
common prefixes, e.g. filenames, URLs etc; I think would be a good case
for this algorithm, wouldn't it?
> http://sourceforge.net/projects/spreadsort
I've recenty been re-coding something where a std::map<> was using more
memory than I wanted. I decided to instead put the data in a
std::vector, sort it, and then search using the std::lower/upper_bound
algorithms. This works well, but I did notice std::sort using a lot of
time in the profile. So an improved sort would be appreciated.
This is off-topic but people might be interested: there are a couple of
remaining problems with this sorted vector implementation. Firstly,
the access pattern when you search is horrible; it starts by reading
one element in the middle, then one at the 1/4 or 3/4 point, and so on;
probably each of those is a page or cache-line that will never be
accessed otherwise. This can be fixed by bit-reversed addressing
(well, at least in the case where the vector size is a power of two, I
think) and I'm considering a container-adaptor that bit-reverses the
index. It makes normal iteration slower of course. The other problem
is that if my data is a key-value pair, I waste a lot of cache space
for the value parts of the elements that I only access the keys of
(i.e. the nodes near the root of the tree). I could fix this by
replacing the vector<pair<key,value>> with a
pair<vector<key>,vector<value>>, but can I somehow get the memory
layout of the latter with the syntax of the former?
Regards, Phil