A fast array shift implementation in C#?

Question

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

Do you actually need to shift the array? Can't you just make a wrapper that acts as if the array was shifted? — svick, Jul 06 '11 at 20:32
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? — aardvarkk, Jul 06 '11 at 20:33
Sorry for not addign this in the first version fo the question. I updated my question with a PS2. — Marino Šimić, Jul 06 '11 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. — Ville Krumlinde, Jul 07 '11 at 14:30
possible duplicate of [Fastest algorithm for circle shift N sized array for M position](http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position) — Isaac Turner, Sep 24 '15 at 17:33

score 13 · Accepted Answer · answered Jul 06 '11 at 20:36

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.

answered Jul 06 '11 at 20:36

LBushkin

129,300
32
216
265

this actually seems good! i need exactly bytes since the array is byte[] – Marino Šimić Jul 06 '11 at 20:42

score 4 · Answer 2 · answered Jul 06 '11 at 20:33

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.

answered Jul 06 '11 at 20:33

Sergey Metlov

25,747
28
93
153

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ć Jul 06 '11 at 20:36
Marino Šimić : does that code need an Array or an IEnumerable? – Andrei Jul 06 '11 at 20:39
So, you have no choice. You should to iterate over the whole array to shift it or use Array.Copy() – Sergey Metlov Jul 06 '11 at 20:43

score 4 · Answer 3 · answered Jul 06 '11 at 20:42

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

answered Jul 06 '11 at 20:42

BrokenGlass

158,293
28
286
335

can I use BlockCopy to do the operations from and to the same array? – Marino Šimić Jul 06 '11 at 20:48
well no - since you would override part of the array that you haven't copied yet. – BrokenGlass Jul 06 '11 at 20:55
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. – BrokenGlass Jul 06 '11 at 20:57
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? – Marino Šimić Jul 06 '11 at 20:58
@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. – BrokenGlass Jul 06 '11 at 21:15
the slight problem would be when having array with low entropy, in that case the method with two Copy would use roughly double memory space (new array) instead of +half. But thanks for the support. i'll give you +1, but musta ccept the other answer with BlockCopy since it came first. – Marino Šimić Jul 07 '11 at 10:22

score 3 · Answer 4 · answered Jul 06 '11 at 20:38

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

score 2 · Answer 5 · edited May 23 '17 at 10:28

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.

FlyingStreudel · Answer 6 · 2011-07-06T21:03:27.150

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

edited Jul 06 '11 at 21:03

answered Jul 06 '11 at 20:37

FlyingStreudel

4,434
4
33
55

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. – Marino Šimić Jul 06 '11 at 20:45
Checking this one... that last one was for a swap based on distance, my b. – FlyingStreudel Jul 06 '11 at 20:52

A fast array shift implementation in C#?

6 Answers6