Re: [boost] [review] Formal review period for Sort library continuing through November 19

Subject: Re: [boost] [review] Formal review period for Sort library continuing through November 19
From: Steven Ross (spreadsort_at_[hidden])
Date: 2014-11-17 08:01:35

Phil,

On Mon, Nov 17, 2014 at 7:21 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:
> Steven Ross wrote:
>
>> If std::sort can sort it, so can string_sort if you use the
>> available functors properly.
>
>
> How about:
>
> bool compare_distance_from_origin(point& a, point& b)
> {
>   return sqr(a.x)+sqr(a.y) < sqr(b.x)+sqr(b.y);
> }
>
> std::sort(points.begin(),points.end(),&compare_distance_from_origin);

Your radix key is: sqr(x) + sqr(y).  If you make all your functors work
relative to that generated key, it'll work fine.

> To me, it's clear that there are many kinds of sort where a radix
> sort can't be used.  An interesting borderline case would be
> case-insensitive sorting; have you tried doing that?

Your Get_char functor just needs to convert one case to the other before
returning:
struct bracket {
  inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {
    return tolower(x.a[offset]);
  }
};
See
https://github.com/spreadsort/sort/blob/master/example/stringfunctorsample.cpp
for an example of using string_sort with functors.  I'll convert that
example to do case-insensitive comparison, as that is an interesting case.

If you can represent your sort as a sequence of comparisons of sequences of
bytes, you can convert each of those comparisons into a sequence of bytes
that make up a synthetic radix.  I am willing to concede that this might be
complicated, and in some cases less efficient when sorting reasonable
quantities of data, but it is doable.

I think many people are confused about the limitations of radix sorts,
because LSD radix sorting over more complex variable-length keys is
inefficient, but MSD radix sort does well with variable-length keys.