Ranges help
Dmitry Olshansky
dmitry.olsh at gmail.com
Wed Oct 12 13:04:51 PDT 2011
On 12.10.2011 22:23, Xinok wrote:
> This is in relation to my sorting algorithm. This is what I need to
> accomplish with ranges in the most efficient way possible:
>
> 1. Merge sort - This involves copying elements to a temporary buffer,
> which can simply be an array, then merging the two lists together. The
> important thing is that it may merge left to right, or right to left,
> which requires a bidirectional range.
>
> c[] = a[0..$/2];
> foreach(a; arr) if(!b.empty && !c.empty) if(b.front <= c.front){
> a = b.front; b.popFront();
> } else{
> a = c.front; c.popFront();
> }
How about:
if(b.empty)
copy(c, a);
else if(c.empty)
copy(b, a);
foreach(a; arr)
if(b.front <= c.front){
a = b.front;
b.popFront();
if(b.empty){
copy(c, a);
break;
}
}
else{
a = c.front; c.popFront();
if(c.empty){
copy(b, a);
break;
}
}
no need to check c if it hasn't changed from the last time, same about b.
>
> 2. Range swap - First, I need to do a binary search, which requires a
> random access range. Then I need to swap two ranges of elements.
>
> while(!a.empty && !b.empty){
> swap(a.front, b.front);
> a.popFront(); b.popFront();
> }
>
If your ranges have equal lengths (or you assume it)
you can skip one of !a.empty or !b.empty in while clause.
Otherwise :
for(;;){
swap(a.front, b.front);
a.popFront();
if(a.empty)
break;
b.popFront();
if(b.empty)
break;
}
might save you a couple of ops in case a is shorter then b, and with
sorting every bit counts isn't it?
>
> That's the best I can come up with. I'm wondering if there's a more
> efficient way to accomplish what I have above.
>
> I also need to figure out the template constraints. Would this be
> correct? Or would this be too much?
>
> isRandomAccessRange && !isFiniteRange && isBidirectionalRange && hasSlicing
isRandomAccessRange should be enough. Also why !isFinite how would one
sort infinite range? hasSlicing is needed though. So my take on this
would be:
isRandomAccessRange && hasSlicing
--
Dmitry Olshansky
More information about the Digitalmars-d-learn
mailing list