Мне нужно сдвинуть вправо и влево массив по 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 для часть, которая выпадает из-за смещения).
Вместо этого вы должны использовать Buffer.BlockCopy. Он обходит индексирование массива и выполняет быстрые копии памяти. Имейте в виду, BlockCopy копирует данные в байтах, а не в терминах размера элемента массива, поэтому не забудьте использовать sizeof() для учета этого.
Просто сохраните индекс первого элемента массива. Когда вам нужно получить значение в смещенном массиве, просто добавьте его в свой индекс итерации.
Когда вам нужно сделать сдвиг, добавьте значение сдвига в индекс первого элемента.
Если вам действительно нужно создать новый, сменный массив, используйте 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));
Не делайте копию вообще. Создавайте легкие объекты, которые хранят ссылку на массив и значение сдвига. Затем используйте эти объекты, когда вам нужно получить значение.
Если вам нужно "складывать" пару смен в одном массиве, оптимизируйте ситуацию, когда создаю только один слой (добавьте смещение от объекта, переданного в).
На основе ответ Джерри Пеннера:
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);
}
Он поддерживает круговое смещение влево и вправо и работает только с данным массивом.
Вы можете использовать что-то вроде этого, если вы не можете использовать только круговой индекс с модулем
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;
}