¿Implementación de cambio de matriz rápida en C#?

Question

Necesito desplazar hacia la derecha y hacia la izquierda una matriz en N lugares.

Los elementos que salen en el lado donde cambio deben volver al otro lado.

Shift derecho 13:

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

Shift dejado por 15:

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

Esta operación sucede a millones de veces y debe ser muy rápido.

Mi implementación actual es la siguiente. Eche un vistazo y sugiera si hay alguna optimización que hacer.

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

Como un consejo sobre cuánto va a obtener cambiado (pero dudo que puede conducir a la optimización):

- 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. No se puede obtener el permiso de seguridad para ejecutar código inseguro:/

PS2: la matriz resultante debe pasarse como una matriz hacia adelante a una biblioteca diferente para su posterior procesamiento, por lo que no puedo simplemente envolver y reindexar.

PS3: Prefiero trabajar en la misma matriz ya que el método usa ref, y hacer eso en una nueva matriz y luego copiar de nuevo tomaría mucho tiempo (estoy usando la matriz 'temp' para la parte que se cae debido al cambio).

Answer 1

En su lugar, debe usar Buffer.BlockCopy. Pasa por alto la indexación de la matriz y realiza copias de memoria rápidas. Tenga en cuenta que BlockCopy copia los datos en bytes, no en términos del tamaño del elemento de la matriz, así que asegúrese de usar sizeof() para dar cuenta de eso.

Answer 2

Simplemente guarde el índice del primer elemento de la matriz. Cuando necesite obtener valor en una matriz desplazada, simplemente agréguela a su índice de iteración.
Cuando necesite hacer un cambio, agregue el valor de desplazamiento al índice del primer elemento.

Answer 3

usted podría utilizar algo como esto si usted no puede simplemente índice de circular con un módulo

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

Answer 4

No hacer la copia en absoluto. Cree objetos livianos que almacenen la referencia a la matriz y el valor de desplazamiento. Luego use esos objetos cuando necesite recuperar el valor.

Si necesita "apilar" un par de turnos en la misma matriz, optimice la situación creando solo una capa (agregue el desplazamiento del objeto pasado).

Answer 5

Si realmente tiene que crear una nueva, desplazado variedad utilizar Buffer.BlockCopy() (I asumido una matriz int en el ejemplo, mismas obras de cualquier otro tipo):

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 6

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

Es compatible con el desplazamiento circular hacia la izquierda y hacia la derecha y funciona solo en la matriz dada.