If I have an array of items:
1, 2, 3, 4, 5, 6, 7, 8
I want to select a range of items and move them to another position in the array. For example:
1, 2, 5, 6, 7, 3, 4, 8
Here the 5, 6, 7 segment has been moved to index 2.
What's the most efficient way of doing this, specifically to limit the number of extra array copies. I have a version working, but it's inefficient and forms a central role in my algorithm which I'm trying to optimise.
Thanks.
Try using a linked list. Since you're moving subsections of a list, it'll be much more memory efficient to move the references on either end of the sublist than to copy each individual item in that same sublist. Overall time-complexity is the same (Θ(n) to traverse a linked list, Θ(n) to copy an array segment), but you'll have better memory-complexity (constant n as opposed to Θ(n)) and fewer issues with continual memory allocation / deallocation.
One approach would be to slice out the items which should move, then shift the existing members:
// T[] source
// int dest
// int start, end
T[] slice = new T[end - start];
Array.Copy(source, start, slice, 0, slice.Length);
if (dest < start)
{
// push towards end
Array.Copy(source, dest, source, dest + slice.Length, start - dest);
}
else
{
// push towards start
// who moves where? Assumes dest..dest+count goes left
Array.Copy(source, end, source, dest, dest - start);
}
Array.Copy(slice, 0, source, dest, slice.Length);
Buffer.BlockCopy instead of Array.Copy.
I know you have chosen an answer; but this question really got under my skin; to see if it's possible to write it another way.
So I came up with this code:
static int[] MoveSlice(int[] arr, int startIndex, int length, int newIndex)
{
var delta = (int)Math.Abs(newIndex - startIndex);
if (delta >= length)
{
for (var i = 0; i < length; i++)
{
var swap = arr[startIndex + i];
arr[startIndex + i] = arr[newIndex + i];
arr[newIndex + i] = swap;
}
}
else
{
var newStart = newIndex + length;
for (var i = 0; i < delta; i++)
{
var swap = arr[newStart + i];
arr[newStart + i] = arr[newIndex + i];
arr[newIndex + i] = swap;
}
var l = (int)Math.Abs(length - delta);
arr = MoveSlice(arr, newIndex + delta, l, newIndex);
}
return arr;
}
I did not test the performance yet. But I enjoyed solving it!
Perhaps you need to employ more code to check for possible errors on boundaries and the like.
If you want to avoid making array copies for efficiency's sake, you can avoid them altogether. You can use a minimum of variables for single values to move the items to their new destinations. Such an algorithm is very efficient on memory, and can be efficient also overall, though it obviously can't take advantage of native, efficient array copying.
