C# quickest way to shift array

Question

How can i quickly shift all the items in an array one to the left, padding the end with null?

[0,1,2,3,4,5,6] would become [0,2,3,4,5,6,null]

Edit: I said quickly but I guess I meant efficiently. I need to do this without creating a List or some other data structure. This is something I need to do several hundred thousand times in as short amount of time as possible.

Answer 1

You might do it like this:

var items = new int?[] { 0, 1, 2, 3, 4, 5, 6 };  // Your array
var itemList = new List<int?>(items);  // Put the items in a List<>
itemList.RemoveAt(1); // Remove the item at index 1
itemList.Add(null); // Add a null to the end of the list
items = itemList.ToArray(); // Turn the list back into an array

Of course, it would be more efficient to get rid of the array entirely and just use a List<>. You could then forget the first line and last line and do it like this:

var itemList = new List<int?> { 0, 1, 2, 3, 4, 5, 6 };
itemList.RemoveAt(1); // Remove the item at index 1
itemList.Add(null); // Add a null to the end of the list

Answer 2

just do:

int?[] newAr = new int?[oldAr.Length];
for (int i = 1; i < oldAr.Length; i++)
   newAr[i - 1] = oldAr[i];

Answer 3

Incorrect and slightly amusing answer (thanks, i'll be here all night !)

int?[] test = new int?[] {0,1,2,3,4,5,6 };

        int?[] t = new int?[test.Length];
        t = test.Skip(1).ToArray();
        t[t.Length - 1] = null; 

In the spirit of still using Skip (dont ask me, i know worst usage of LINQ extension methods ever), the only way I thought of rewriting it would be

        int?[] test = new int?[] { 0, 1, 2, 3, 4, 5, 6 };

        int?[] t = new int?[test.Length];
        Array.Copy(test.Skip(1).ToArray(), t, t.Length - 1);

But it's in NO WAY faster than the other options.

Answer 4

Couldn't you use a System.Collections.Generic.Queue instead of an array ?

I feel like you need to perform actions on your value the discard it, thus using a queue seems to be more appropriate :

// dummy initialization
        System.Collections.Generic.Queue<int> queue = new Queue<int>();
        for (int i = 0; i < 7; ++i ) { queue.Enqueue(i); }// add each element at the end of the container

        // working thread
        if (queue.Count > 0)
            doSomething(queue.Dequeue());// removes the last element of the container and calls doSomething on it

Answer 5

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.

Answer 6

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...

Answer 7

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 :)

Answer 8

If it absolutely has to be in an array, then I would recommend the most obvious code possible.

for (int index = startIndex; index + 1 < values.Length; index++)
     values[index] = values[index + 1];
values[values.Length - 1] = null;

This gives the optimizer the most opportunities to find the best way on whatever target platform the program is installed on.

EDIT:

I just borrowed Jason Punyon's test code, and I'm afraid he's right. Array.Copy wins!

    var source = Enumerable.Range(1, 100).Cast<int?>().ToArray();
    int indexToRemove = 4;

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

Array.Copy takes between 103 and 150 ms on my machine.

for loop takes between 269 and 338 ms on my machine.

Answer 9

Array copying is an O(n) operation and creates a new array. While array copying can certainly be done quickly and efficiently, the problem you've stated can actually be solved in an entirely different way without (as you've requested) creating a new array/data structure and only creating one small wrapping object instance per array:

using System;
using System.Text;

public class ArrayReindexer
{
    private Array reindexed;
    private int location, offset;

    public ArrayReindexer( Array source )
    {
        reindexed = source;
    }

    public object this[int index]
    {
        get
        {
            if (offset > 0 && index >= location)
            {
                int adjustedIndex = index + offset;
                return adjustedIndex >= reindexed.Length ? "null" : reindexed.GetValue( adjustedIndex );
            }

            return reindexed.GetValue( index );
        }
    }

    public void Reindex( int position, int shiftAmount )
    {
        location = position;
        offset = shiftAmount;
    }

    public override string ToString()
    {
        StringBuilder output = new StringBuilder( "[ " );
        for (int i = 0; i < reindexed.Length; ++i)
        {
            output.Append( this[i] );
            if (i == reindexed.Length - 1)
            {
                output.Append( " ]" );
            }
            else
            {
                output.Append( ", " );
            }
        }

        return output.ToString();
    }
}

By wrapping and controlling access to the array in this manner, we can now demonstrate how the problem was solved with an O(1) method call...

ArrayReindexer original = new ArrayReindexer( SourceArray );
Console.WriteLine( "   Base array: {0}", original.ToString() );
ArrayReindexer reindexed = new ArrayReindexer( SourceArray );
reindexed.Reindex( 1, 1 );
Console.WriteLine( "Shifted array: {0}", reindexed.ToString() );

Will produce the output:

Base array: [ 0, 1, 2, 3, 4, 5, 6 ]
Shifted array: [ 0, 2, 3, 4, 5, 6, null ]

I'm willing to bet that there will be a reason that such a solution won't work for you, but I believe this does match your initial stated requirements. 8 )

It's often helpful to think about all the different kinds of solutions to a problem before implementing a specific one, and perhaps that might be the most important thing that this example can demonstrate.

Hope this helps!

Answer 10

You can use the same array as source and destination for fast in-place copy:

static void Main(string[] args)
        {
            int[] array = {0, 1, 2, 3, 4, 5, 6, 7};
            Array.ConstrainedCopy(array, 1, array, 0, array.Length - 1);
            array[array.Length - 1] = 0;
        }

Answer 11

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.

Answer 12

Can't you

• allocate the array with an extra 1000 elements

• have an integer variable int base = 0

• instead of accessing a[i] access a[base+i]

• to do your shift, just say base++

Then after you've done this 1000 times, copy it down and start over.
That way, you only do the copy once per 1000 shifts.

---

Old joke:
Q: How many IBM 360s does it take to shift a register by 1 bit?
A: 33. 32 to hold the bits in place, and 1 to move the register. (or some such...)