## digitalmars.D.learn - Ranges help

- Xinok <xinok live.com> Oct 12 2011
- Dmitry Olshansky <dmitry.olsh gmail.com> Oct 12 2011
- Xinok <xinok live.com> Oct 12 2011
- travert phare.normalesup.org (Christophe) Oct 14 2011
- Xinok <xinok live.com> Oct 14 2011

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(); } 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(); } 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

Oct 12 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(); }

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

sort infinite range? hasSlicing is needed though. So my take on this would be: isRandomAccessRange && hasSlicing -- Dmitry Olshansky

Oct 12 2011

On 10/12/2011 4:04 PM, Dmitry Olshansky wrote:On 12.10.2011 22:23, Xinok wrote:I also need to figure out the template constraints. Would this be correct? Or would this be too much? isRandomAccessRange && !isFiniteRange && isBidirectionalRange && hasSlicing

sort infinite range? hasSlicing is needed though. So my take on this would be: isRandomAccessRange && hasSlicing

Sorry, typo. That should be !isInfiniteRange. But I can drop !isInfinteRange anyways, so: isRandomAccessRange && isBidirectionalRange && hasSlicing isRandomAccessRange can be a bidirectional range or an infinite forward range, so isBidirectionalRange is still required.

Oct 12 2011

Xinok , dans le message (digitalmars.D.learn:30054), a écrit :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(); } 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(); } 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

You should look at: std.algorithm.SetUnion std.algorithm.swapRanges -- Christophe

Oct 14 2011

Thanks. I'll run a benchmark with swapRanges, see how it compares to my own code. But it would be better if I coded the merge function myself, since I can do it in-place using very little memory.

Oct 14 2011