13

I need to shift to the right and to the left an array by N places.

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

Improve this question
6
  • 3
    Do you actually need to shift the array? Can't you just make a wrapper that acts as if the array was shifted? Commented Jul 6, 2011 at 20:32
  • 7
    Wouldn't it possibly be more efficient to not move the items at all -- just keep track of an index, and circularly access the elements without copying them anywhere? Commented Jul 6, 2011 at 20:33
  • 1
    I would try and get rid of the extra array allocation. Commented Jul 6, 2011 at 20:33
  • 1
    Sorry for not addign this in the first version fo the question. I updated my question with a PS2. Commented Jul 6, 2011 at 20:38
  • The allocation of "temp" on every call will generate lot of garbage collection. I would keep temp as a class member that is allocated once instead (make it large enough for largest shift, or reallocate to larger when necessary). This could also benefit cache performance. Commented Jul 7, 2011 at 14:30

6 Answers 6

Reset to default
13

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

this actually seems good! i need exactly bytes since the array is byte[]
4

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.

Improve this answer

3 Comments

The resulting array will be passed onward to code i cannot control. I will add this to my question. At some point the resulting array won't be adressed by me but a library.
Marino Šimić : does that code need an Array or an IEnumerable?
So, you have no choice. You should to iterate over the whole array to shift it or use Array.Copy()
4

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));
Improve this answer

6 Comments

can I use BlockCopy to do the operations from and to the same array?
well no - since you would override part of the array that you haven't copied yet.
An alternative to BlockCopy() is Array.Copy(), I don't have reflector handy right now though, so I don't know if it is efficient. If you can I would avoid creating an new array and just have a thin layer on top that handle the shifting as some of the other answers are pointing to.
so basically I should stick to my method with the temp array (for the part that fall out) but instead of using Array.Copy use Buffer.BlockCopy?
@Marrino: Turns out Array.Copy uses same copy mechanism internally, you only save some of the bounds checking which should make BlockCopy very slightly faster. The main improvement would be using just two BlockCopy operations and not three as in the sample you provided.
|
3

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

Improve this answer

Comments

2

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.

Improve this answer

Comments

0

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;
}
Improve this answer

2 Comments

this seems to contain more memcpy operations than my solution, so I relly think that it would be slower... I'm not knowledgeable on how the Array.Copy works exactly but generally less memory operations means more speed. I don't have a problem with additionaly buffers, just speed.
Checking this one... that last one was for a swap based on distance, my b.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.