Another fun one: partialSort with two ranges

[Timon Gehr via Digitalmars-d]

On 12/03/2015 08:12 PM, Andrei Alexandrescu wrote:
> On 12/03/2015 02:09 PM, Andrei Alexandrescu wrote:
>> Yah, please convert to pull request. Using two ranges is just beautiful.
>> Thanks! -- Andrei
>
> I should add that the use of chain is liable to be quite a bit less
> efficient - it's one of those "hamburger into cow" cases.
> ...

Well, one obvious improvement is this:

void partialSort(alias less="a<b",R,S)(R r,S s) /+if(...)+/
{ topN!less(chain(r,s),r.length); sort!less(r); }

Constraint left out as I have noticed that the template constraint of 
the current partial sort implementation is actually not restrictive 
enough, and the fixed constraint would be somewhat large.

Further improvements would probably be based on an implementation of 
topN accepting two ranges:

void partialSort(alias less="a<b",R,S)(R r,S s) /+if(...)+/
{ topN!less(r,s); sort!less(r); }

The two-ranges version for topN is quite natural:

void topN(alias less="a<b",R,S)(R r,S s) /+if(...)+/{
     while(r.length&&s.length){
         auto rs=chain(r.save,s.save);
         auto pivot=uniform(0,rs.length);
         swap(rs[pivot],s.back);
         auto right=partition!(a=>binaryFun!less(a,s.back))(rs);
         swap(right.front,s.back);
         pivot=r.length+s.length-right.length;
         if(pivot<r.length) r=r[pivot+1..$];
         else s=s[0..pivot-r.length];
     }
}

(NB: This relies on implementation details of partition, matching the 
current implementation in Phobos.)

If this is not fast enough, 'partition' should be specialized for 
chain's Result.

> The right way to go about this is redo partialSort with two ranges, then
> have the current signature with range and size_t forward to it:
> partialSort(r[0 .. n], r[n + 1 .. $]). -- Andrei

Ideally yes, but it might become slightly slower as the cow is more 
general than the hamburger.