Быстрая реализация сдвига массива в C #?

Question

Мне нужно сместить вправо и влево массив на N мест.

Элементы, которые появляются на той стороне, на которую я смещаюсь, должны вернуться на другую сторону.

Сдвиг вправо на 13:

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

Сдвиг влево на 15:

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

Эта операция будет происходить миллионы рази должен быть очень быстрым.

Моя текущая реализация следующая.Пожалуйста, посмотрите и предложите, если есть какая-то оптимизация.

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

В качестве подсказки о том, насколько она будет сдвинута (но я сомневаюсь, что это может привести к оптимизации):

-  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.Невозможно получить разрешение безопасности для запуска небезопасного кода: /

PS2: Полученный массив должен быть передан в виде массива в другую библиотеку для дальнейшей обработки, поэтому я не могу просто перенести и переиндексировать.

PS3: Я бы предпочел работать с тем же массивом, так как метод использует ref, и выполнение этого с новым массивом с последующим копированием обратно заняло бы много времени (я использую массив 'temp' для части, котораявыпадает из-за сдвига).

Answer 1

Вы должны использовать Buffer.BlockCopy. Он обходит индексацию массива и выполняет быстрые копии памяти. Имейте в виду, что BlockCopy копирует данные в байтах, а не с точки зрения размера элемента массива, поэтому обязательно используйте sizeof(), чтобы учесть это.

Answer 2

Если вам действительно нужно создать новый сдвинутый массив, используйте Buffer.BlockCopy() (в примере я предположил массив int, то же самое работает для любого другого типа):

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

Answer 3

Просто сохраните индекс первого элемента массива.Когда вам нужно получить значение в смещенном массиве, просто добавьте его к индексу итерации.
Когда вам нужно сделать сдвиг, добавьте значение смещения к индексу первого элемента.

Answer 4

На основании ответа Джерри Пеннера :

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

Поддерживает круговое смещение влево и вправо и работает только для данного массива.

Answer 5

Не делайте копию вообще. Создайте легкие объекты, которые хранят ссылку на массив и значение сдвига. Затем используйте эти объекты, когда вам нужно получить значение.

Если вам нужно «сложить» пару сдвигов в одном массиве, оптимизируйте ситуацию, создав только один слой (добавьте сдвиг от переданного объекта).

Answer 6

Вы можете использовать что-то вроде этого, если вы не можете просто циклический индекс по модулю

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