C# quickest way to shift array

Solution 1:

Here's my test harness...

var source = Enumerable.Range(1, 100).Cast<int?>().ToArray();
var destination = new int?[source.Length];

var s = new Stopwatch();
s.Start();
for (int i = 0; i < 1000000;i++)
{
    Array.Copy(source, 1, destination, 0, source.Length - 1);
}
s.Stop();
Console.WriteLine(s.Elapsed);

Here are the performance results for 1 million iterations of each solution (8 Core Intel Xeon E5450 @ 3.00GHz)

                       100 elements  10000 elements
For Loop                     0.390s         31.839s 
Array.Copy()                 0.177s         12.496s
Aaron 1                      3.789s         84.082s
Array.ConstrainedCopy()      0.197s         17.658s

Make the choice for yourself :)

Solution 2:

The quickest way to do this is to use Array.Copy, which in the final implementation uses a bulk memory transfer operation (similar to memcpy):

var oldArray = new int?[] { 1, 2, 3, 4, 5, 6 };
var newArray = new int?[oldArray.Length];
Array.Copy(oldArray, 1, newArray, 0, oldArray.Length - 1);
// newArray is now { 2, 3, 4, 5, 6, null }

Edited: according to the documentation:

If sourceArray and destinationArray overlap, this method behaves as if the original values of sourceArray were preserved in a temporary location before destinationArray is overwritten.

So if you don't want to allocate a new array, you can pass in the original array for both source and destination--although I imagine the tradeoff will be a somewhat slower performance since the values go through a temporary holding position.

I suppose, as in any investigation of this kind, you should do some quick benchmarking.

Solution 3:

Here is my solution, similar to Task's in that it is a simple Array wrapper and that it takes O(1) time to shift the array to the left.

public class ShiftyArray<T>
{
    private readonly T[] array;
    private int front;

    public ShiftyArray(T[] array)
    {
        this.array = array;
        front = 0;
    }

    public void ShiftLeft()
    {
        array[front++] = default(T);
        if(front > array.Length - 1)
        {
            front = 0;
        }
    }

    public void ShiftLeft(int count)
    {
        for(int i = 0; i < count; i++)
        {
            ShiftLeft();
        }
    }

    public T this[int index]
    {
        get
        {
            if(index > array.Length - 1)
            {
                throw new IndexOutOfRangeException();
            }

            return array[(front + index) % array.Length];
        }
    }

    public int Length { get { return array.Length; } }
}

Running it through Jason Punyon's test code...

int?[] intData = Enumerable.Range(1, 100).Cast<int?>().ToArray();
ShiftyArray<int?> array = new ShiftyArray<int?>(intData);

Stopwatch watch = new Stopwatch();
watch.Start();

for(int i = 0; i < 1000000; i++)
{
    array.ShiftLeft();
}

watch.Stop();

Console.WriteLine(watch.ElapsedMilliseconds);

Takes ~29ms, regardless of the array size.

Solution 4:

Use the Array.Copy() method as in

int?[] myArray = new int?[]{0,1,2,3,4};
Array.Copy(myArray, 1, myArray, 0, myArray.Length - 1);
myArray[myArray.Length - 1] = null

The Array.Copy is probably the way, Microsoft wanted us to copy array elements...