digitalmars.D - Another fun one: partialSort with two ranges
- Andrei Alexandrescu (3/3) Dec 03 2015 This should be pretty cool:
- Vladimir Panteleev (4/7) Dec 03 2015 Does chain not provide random access, thus allowing sorting a
- Timon Gehr (11/19) Dec 03 2015 void partialSort(R,S)(R r,S s)
- Andrei Alexandrescu (3/23) Dec 03 2015 Yah, please convert to pull request. Using two ranges is just beautiful....
- Andrei Alexandrescu (6/8) Dec 03 2015 I should add that the use of chain is liable to be quite a bit less
- Timon Gehr (30/39) Dec 03 2015 Well, one obvious improvement is this:
- Andrei Alexandrescu (2/4) Dec 03 2015 Again this is suboptimal - should use two ranges, not chain. -- Andrei
- Andrei Alexandrescu (2/4) Dec 03 2015 Sorry, I was hasty. Yes, that's the good stuff. -- Andrei
- Andrei Alexandrescu (3/11) Dec 03 2015 Here the ranges must be distinct. It would be awkward to pass
This should be pretty cool: https://issues.dlang.org/show_bug.cgi?id=15401 Andrei
Dec 03 2015
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 AndreiDoes chain not provide random access, thus allowing sorting a chain of two ranges?
Dec 03 2015
On 12/03/2015 05:09 PM, Vladimir Panteleev wrote:On Thursday, 3 December 2015 at 15:18:16 UTC, Andrei Alexandrescu wrote: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])); }This should be pretty cool: https://issues.dlang.org/show_bug.cgi?id=15401 AndreiDoes chain not provide random access, thus allowing sorting a chain of two ranges?
Dec 03 2015
On 12/03/2015 12:59 PM, Timon Gehr wrote:On 12/03/2015 05:09 PM, Vladimir Panteleev wrote:Yah, please convert to pull request. Using two ranges is just beautiful. Thanks! -- AndreiOn Thursday, 3 December 2015 at 15:18:16 UTC, Andrei Alexandrescu wrote: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])); }This should be pretty cool: https://issues.dlang.org/show_bug.cgi?id=15401 AndreiDoes chain not provide random access, thus allowing sorting a chain of two ranges?
Dec 03 2015
On 12/03/2015 02:09 PM, Andrei Alexandrescu wrote:Yah, please convert to pull request. Using two ranges is just beautiful. Thanks! -- AndreiI 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
On 12/03/2015 08:12 PM, Andrei Alexandrescu wrote:On 12/03/2015 02:09 PM, Andrei Alexandrescu wrote: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.Yah, please convert to pull request. Using two ranges is just beautiful. Thanks! -- AndreiI 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 .. $]). -- AndreiIdeally yes, but it might become slightly slower as the cow is more general than the hamburger.
Dec 03 2015
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
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
On 12/03/2015 11:09 AM, Vladimir Panteleev wrote:On Thursday, 3 December 2015 at 15:18:16 UTC, Andrei Alexandrescu wrote:Here the ranges must be distinct. It would be awkward to pass partialSort(chain(r1, r2), r1.length). -- AndreiThis should be pretty cool: https://issues.dlang.org/show_bug.cgi?id=15401 AndreiDoes chain not provide random access, thus allowing sorting a chain of two ranges?
Dec 03 2015