A fast array shift implementation in C#?

I need to shift to the right and to the left an array by N place开发者_Python百科s.

The items that pop out on the side where i shift to must get back into on the other side.

Shift right by 13:

[0,1,2,3,4,5,6,7,8,9] -> [7,8,9,0,1,2,3,4,5,6]

Shift left by 15:

[0,1,2,3,4,5,6,7,8,9] -> [5,6,7,8,9,0,1,2,3,4]

This operation will happen millions of times and must be really fast.

My current implementation is the following. Please have a look and suggest if there is some optimization to do.

if (shift > 0)
{
    int offset = array.Length % shift;
    if (offset > 0)
    {
        byte[] temp = new byte[offset];
        if (!right)
        {
            Array.Copy(array, temp, offset);
            Array.Copy(array, offset, array, 0, array.Length - offset);
            Array.Copy(temp, 0, array, array.Length - offset, temp.Length);
        }
        else
        {
            Array.Copy(array, array.Length - offset, temp, 0, offset);
            Array.Copy(array, 0, array, offset, array.Length - offset);
            Array.Copy(temp, 0, array, 0, temp.Length);
        }
    }
}

As a tip on how much it will get shifted (but I doubt it can lead to optimization):

-  depends on the entropy of the array itself
-  for aray that are full of same values it will get shifted roughtly 0
-  more entropy means higher shift value
-  direction of shift will be used generally more to the left

PS. Cannot get the security permission to run unsafe code :/

PS2: The resulting array must be passed as an array onward to a different library for further processing, so I cannot just wrap and reindex.

PS3: I'd prefer to work on the same array since the method uses ref, and doing that on a new array and then copying back would be time consuming (i'm using the 'temp' array for the part that falls out because of shifting).

You should use Buffer.BlockCopy instead. It bypasses the array indexing and performs fast memory copies. Keep in mind, BlockCopy copies data in bytes, not in terms of the size of array element, so make sure to use sizeof() to account for that.

Just save the index of the first element of array. When you need to get value in shifted array, just add it to your iteration index.
When you need to do shift, add the shift value to the index of the first element.

If you truly have to create a new, shifted array use Buffer.BlockCopy() (I assumed an int array in the example, same works for any other type):

int [] sourceArray = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int [] targetArray = new int[sourceArray.Length];

int shift = 13;
int offset = shift % sourceArray.Length;

Buffer.BlockCopy(sourceArray, offset*sizeof(int), targetArray, 0 , (sourceArray.Length - offset)*sizeof(int));
Buffer.BlockCopy(sourceArray, 0, targetArray, (sourceArray.Length - offset) * sizeof(int), offset * sizeof(int));

Don't do the copy at all. Create lightweight objects that store the reference to the array and the shift value. Then use those objects instead when you need to retrieve the value.

If you need to "stack" a couple of shifts on the same array, optimise the situation my creating only one layer (add the shift from object passed in).

Based on Jerry Penner's answer:

internal static void ShiftCircular(int offset, object[] array)
{
    if (offset == 0 || array.Length <= 1)
        return;

    offset = offset % array.Length;

    if (offset == 0)
        return;

    if (offset < 0)
        offset = array.Length + offset;

    Array.Reverse(array, 0, array.Length);
    Array.Reverse(array, 0, offset);
    Array.Reverse(array, offset, array.Length - offset);
}

It supports circular left- and right-shifting and works only on the given array.

You could use something like this if you cant just circular index with a modulo

public byte[] ShiftBytes(byte[] arr, int shift, bool isRight) 
{
    byte[] newBytes = new byte[arr.Length];
    shift = (isRight) ? shift : -1 * shift;
    for (int i = 0; i < arr.Length; i++) 
        newBytes[i] = arr[(((i + shift) % arr.Length) 
            + arr.Length) % arr.Length];
    return newBytes;
}