www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Another fun one: partialSort with two ranges

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
This should be pretty cool:

https://issues.dlang.org/show_bug.cgi?id=15401

Andrei
Dec 03 2015
parent reply Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
On Thursday, 3 December 2015 at 15:18:16 UTC, Andrei Alexandrescu 
wrote:
 This should be pretty cool:

 https://issues.dlang.org/show_bug.cgi?id=15401

 Andrei
Does chain not provide random access, thus allowing sorting a chain of two ranges?
Dec 03 2015
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 12/03/2015 05:09 PM, Vladimir Panteleev wrote:
 On Thursday, 3 December 2015 at 15:18:16 UTC, Andrei Alexandrescu wrote:
 This should be pretty cool:

 https://issues.dlang.org/show_bug.cgi?id=15401

 Andrei
Does chain not provide random access, thus allowing sorting a chain of two ranges?
void partialSort(R,S)(R r,S s) if(isRandomAccessRange!R && hasLength!R && hasSlicing!R && isRandomAccessRange!S && hasLength!S && hasSlicing!S) { partialSort(chain(r,s),r.length); } unittest{ auto a=[1,2,3,4]; auto b=[1,2,3,4,5,6]; partialSort(a,b); assert(equal(a,[1,1,2,2])); }
Dec 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 12:59 PM, Timon Gehr wrote:
 On 12/03/2015 05:09 PM, Vladimir Panteleev wrote:
 On Thursday, 3 December 2015 at 15:18:16 UTC, Andrei Alexandrescu wrote:
 This should be pretty cool:

 https://issues.dlang.org/show_bug.cgi?id=15401

 Andrei
Does chain not provide random access, thus allowing sorting a chain of two ranges?
void partialSort(R,S)(R r,S s) if(isRandomAccessRange!R && hasLength!R && hasSlicing!R && isRandomAccessRange!S && hasLength!S && hasSlicing!S) { partialSort(chain(r,s),r.length); } unittest{ auto a=[1,2,3,4]; auto b=[1,2,3,4,5,6]; partialSort(a,b); assert(equal(a,[1,1,2,2])); }
Yah, please convert to pull request. Using two ranges is just beautiful. Thanks! -- Andrei
Dec 03 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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. 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
Dec 03 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Dec 03 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 06:19 PM, Timon Gehr wrote:
 void partialSort(alias less="a<b",R,S)(R r,S s) /+if(...)+/
 { topN!less(chain(r,s),r.length); sort!less(r); }
Again this is suboptimal - should use two ranges, not chain. -- Andrei
Dec 03 2015
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 06:19 PM, Timon Gehr wrote:
 void partialSort(alias less="a<b",R,S)(R r,S s) /+if(...)+/
 { topN!less(r,s); sort!less(r); }
Sorry, I was hasty. Yes, that's the good stuff. -- Andrei
Dec 03 2015
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2015 11:09 AM, Vladimir Panteleev wrote:
 On Thursday, 3 December 2015 at 15:18:16 UTC, Andrei Alexandrescu wrote:
 This should be pretty cool:

 https://issues.dlang.org/show_bug.cgi?id=15401

 Andrei
Does chain not provide random access, thus allowing sorting a chain of two ranges?
Here the ranges must be distinct. It would be awkward to pass partialSort(chain(r1, r2), r1.length). -- Andrei
Dec 03 2015