Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 646
Dested Avatar asked Mar 04 '10 17:03

Dested


2 Answers

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

like image 163
Jason Punyon Avatar answered Nov 03 '22 09:11

Jason Punyon


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.

like image 65
Ben M Avatar answered Nov 03 '22 09:11

Ben M