C# quickest way to shift array

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

For example, [0,1,2,3,4,5,6] would become [1,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.

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

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.

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.

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

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

For any pour soul finding this thread and about to implement one of the highly rated answers. All of them are trash, I'm not sure why that is. Maybe Dested asked for a new array implementation at first or something that has now been removed from the question. Well if you simply want to shift the array and don't need a new one, see an answer like tdaines's answer. And read up on things like the Circular Buffer / Ring Buffer : http://en.wikipedia.org/wiki/Circular_buffer. No moving of the actual data is necessary. The performance of shifting an array should not be tied to the size of the array.

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.

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

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

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

Try this! using Linq. No need of second Array.

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

        i_array = i_array.Select((v, k) => new { v = v, k = k }).
            Where(i => i.k > 0).Select(i => i.v).ToArray();

        Array.Resize(ref i_array, i_array.Length + 1);

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

If you own the memory you could consider using Unsafe Code and good old fashioned pointers.

Make yourself a memory stream and lock it down or use Marshal.AllocHGlobal Construct all your arrays in it with a little bit of padding at the beginning and end. increment or decrement all of the array pointers at once. You'll still need to loop back and set your nulls.

If you need to selectively increment or decrement the arrays you would have to add padding between them.

Arrays are incredibly low level data structures, if you treat them in a low level way you can get huge performance out of them.

A baytrail doing this could outperform Jason's with all its copying 8 Core Intel Xeon E5450 @ 3.00GHz

Not tested this code, but it should shifts all the values to right by one. Note that the last three lines of code is all you require to efficiently shift the array.

public class Shift : MonoBehaviour {
     //Initialize Array
     public int[] queue;

     void Start () {
          //Create Array Rows
          queue = new int[5];

          //Set Values to 1,2,3,4,5
          for (int i=0; i<5;i++)
          {
               queue[i] = i + 1;
          }

          //Get the integer at the first index
          int prev = queue[0];

          //Copy the array to the new array.
          System.Array.Copy(queue, 1, queue, 0, queue.Length - 1);

          //Set the last shifted value to the previously first value.
          queue[queue.Length - 1] = prev;

The best and most efficient method I believe is using Buffer.BlockCopy function. You will set both source and destination to your array, the offset of the source is 1. Depending on your array type (I assume it is int), 1 int = 4 bytes, so you must pass in 4 as the second parameter of this function. Note that the offset is byte offset.

So it looks like this:

int bytes2copy = yourArray.length - 4;
Buffer.BlockCopy(yourArray, 4, yourArray, 0, bytes2copy);
yourArray[yourArray.length-1] = null;

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.

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!

I know this is an old question but coming from Google there was no simple example so thanks to this is the easiest way to reorder a list, and you don't have to supply the type it will work it out at runtime,

   private static List<T> reorderList<T>(List<T> list){
       List<T> newList = new List<T>();

       list.ForEach(delegate(T item)
       {
           newList.Add(item);
       });

       return newList;
   }

See C# code below to remove space from string. That shift character in array. Performance is O(n). No other array is used. So no extra memory either.

    static void Main(string[] args)
    {
        string strIn = System.Console.ReadLine();

        char[] chraryIn = strIn.ToCharArray();

        int iShift = 0;
        char chrTemp;
        for (int i = 0; i < chraryIn.Length; ++i)
        {
            if (i > 0)
            {
                chrTemp = chraryIn[i];
                chraryIn[i - iShift] = chrTemp;
                chraryIn[i] = chraryIn[i - iShift];
            }
            if (chraryIn[i] == ' ') iShift++;
            if (i >= chraryIn.Length - 1 - iShift) chraryIn[i] = ' ';
        }
       System.Console.WriteLine(new string(chraryIn));
       System.Console.Read();
    }

using System;
using System.Threading;

namespace ShiftMatrix
{
    class Program
    {
        static void Main(string[] args)
        {

            MatrixOperation objMatrixOperation = new MatrixOperation();

            //Create a matrix
            int[,] mat = new int[,]
        {
        {1, 2},
        {3,4 },
        {5, 6},
        {7,8},
        {8,9},
        };

            int type = 2;
            int counter = 0;
            if (type == 1)
            {
                counter = mat.GetLength(0);
            }
            else
            {
                counter = mat.GetLength(1);
            }
            while (true)
            {
                for (int i = 0; i < counter; i++)
                {
                    ShowMatrix(objMatrixOperation.ShiftMatrix(mat, i, type));
                    Thread.Sleep(TimeSpan.FromSeconds(2));
                }
            }
        }
        public static void ShowMatrix(int[,] matrix)
        {
            int rows = matrix.GetLength(0);
            int columns = matrix.GetLength(1);
            for (int k = 0; k < rows; k++)
            {
                for (int l = 0; l < columns; l++)
                {
                    Console.Write(matrix[k, l] + " ");
                }
                Console.WriteLine();
            }
        }
    }
    class MatrixOperation
    {
        public int[,] ShiftMatrix(int[,] origanalMatrix, int shift, int type)
        {
            int rows = origanalMatrix.GetLength(0);
            int cols = origanalMatrix.GetLength(1);

            int[,] _tmpMatrix = new int[rows, cols];
            if (type == 2)
            {
                for (int x1 = 0; x1 < rows; x1++)
                {
                    int y2 = 0;
                    for (int y1 = shift; y2 < cols - shift; y1++, y2++)
                    {
                        _tmpMatrix[x1, y2] = origanalMatrix[x1, y1];
                    }
                    y2--;
                    for (int y1 = 0; y1 < shift; y1++, y2++)
                    {
                        _tmpMatrix[x1, y2] = origanalMatrix[x1, y1];
                    }
                }
            }
            else
            {
                int x2 = 0;
                for (int x1 = shift; x2 < rows - shift; x1++, x2++)
                {
                    for (int y1 = 0; y1 < cols; y1++)
                    {
                        _tmpMatrix[x2, y1] = origanalMatrix[x1, y1];
                    }
                }
                x2--;
                for (int x1 = 0; x1 < shift; x1++, x2++)
                {
                    for (int y1 = 0; y1 < cols; y1++)
                    {
                        _tmpMatrix[x2, y1] = origanalMatrix[x1, y1];
                    }
                }

            }
            return _tmpMatrix;
        }
    }

}

a is array of ints & d is number of times array has to shift left.

static int[] rotLeft(int[] a, int d) 
{
     var innerLoop = a.Length - 1;
     for(var loop=0; loop < d; loop++)
     {
         var res = a[innerLoop];
         for (var i= innerLoop; i>=0; i--)
         {
            var tempI = i-1;
            if (tempI < 0)
            {
                tempI = innerLoop;
            }        
            var yolo = a[tempI];
            a[tempI] = res;
            res = yolo;
         }
     }
     return a;
}

Simple way to do it when you need to resize the same array.

            var nLength = args.Length - 1;
            Array.Copy(args, 1, args, 0, nLength);
            Array.Resize(ref args, nLength);