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: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2014-11-17 12:25:42

Steven Ross wrote:
> 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.

So my thought was, you wouldn't want to do that because all that
extra maths is being done so frequently and the performance would
be considerably worse than std::sort.  But:

> 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.

Ah, that may be true; I was overlooking the fact that not every bit of the
value is looked at if the values are sufficiently well separated.

Regards,  Phil.