Transponer una matriz 2D

Question

¿Cómo se transpone eficientemente una matriz? ¿Hay bibliotecas para esto o qué algoritmo usarías?

Ej:

short src[W*H] = { 
    {1,2,3}, 
    {4,5,6} 
}; 
short dest[W*H]; 


rotate_90_clockwise(dest,src,W,H); //<-- magic in here, no need for in-place 

//dest is now: 

{ 
    {4, 1}, 
    {5, 2}, 
    {6, 3} 
}; 

(En mi caso específico es su variedad src datos de imágenes en bruto, y el destino es un uso de este dispositivo, y estoy incrustado en ARM en un conjunto de herramientas que no admite el montaje)

Answer 1

Hay bibliotecas para esto, en algunos casos. Y, notablemente, hay trucos que puede jugar con datos vectorizados (por ejemplo, cuatro elementos de 32 bits en un vector de 128 bits, pero esto también se aplica a cuatro bytes de 8 bits en un registro de 32 bits) para ir más rápido que el individuo acceso a los elementos.

Para una transposición, la idea estándar es que utilice instrucciones "shuffle", que le permiten crear un nuevo vector de datos a partir de dos vectores existentes, en cualquier orden. Usted trabaja con bloques 4x4 de la matriz de entrada. Así, empezando, tiene:

v0 = 1 2 3 4 
v1 = 5 6 7 8 
v2 = 9 A B C 
v3 = D E F 0 

A continuación, se aplican las instrucciones de reproducción aleatoria a los dos primeros vectores (entrelazado sus elementos extraños, A0B0 c0d0 -> ABCD, y el entrelazado sus incluso elementos, 0A0B 0C0D -> ABCD) , y para los dos últimos, para crear un nuevo conjunto de vectores con cada bloque de 2x2 transpuesta:

1 5 3 7 
2 6 4 8 
9 D B F 
A E C 0 

Por último, se aplican las instrucciones de reproducción aleatoria a la extraña pareja y la aún par (la combinación de sus primeros pares de elementos, AB00 CD00 -> ABCD, y sus últimos pares, 00AB 00CD -> ABCD), para obtener:

1 5 9 D 
2 6 A E 
3 7 B F 
4 8 C 0 

¡Y allí, 16 elementos transpuestos en ocho instrucciones!

Ahora, para bytes de 8 bits en registros de 32 bits, ARM no tiene exactamente instrucciones de mezcla, pero puede sintetizar lo que necesita con turnos y una instrucción SEL (seleccionar), y el segundo conjunto de combinaciones puede hacer en una instrucción con las instrucciones PKHBT (paquete halfword bottom top) y PKHTB (pack halfword top bottom).

Finalmente, si está utilizando un procesador ARM grande con vectorizaciones de NEON, puede hacer algo como esto con vectores de 16 elementos en bloques de 16x16.

Answer 2

una solución muy simple que funciona en o (1) es el ahorro de un booleano adicional para la matriz, decir si se trata de 'transposición' o no. A continuación, se accede a la matriz de acuerdo con este booleano (fila/col o col/row).

Por supuesto, que impedirá su utilización de caché.

Por lo tanto, si tiene muchas operaciones de transposición y pocos "cruces completos" (que, por cierto, también podrían reordenarse de acuerdo con el valor del booleano), esta es su mejor opción.

Answer 3

• Si la matriz es cuadrada o si no busca una transposición in-situ es muy fácil:

Básicamente iterar en las líneas y de intercambio cada artículos a juego con elementos de las columnas. Obtiene el elemento correspondiente intercambiando índices de fila y columna. Cuando haya tratado todas las columnas, la transposición habrá finalizado. También puede ir al revés e iterar en columnas.

Si desea aumentar el rendimiento puede copiar una línea completa en una matriz temporal y la columna de coincidencia total en otro, a continuación, vuelva a copiarlos. Debería ser un poco más rápido (incluso si esta estrategia implica una asignación de variable más) si utiliza una memoria para transferencias que involucran elementos más internos.

• Si la matriz no es cuadrada (como en su ejemplo) es realmente difícil hacerlo en el lugar. Como la transposición no cambia las necesidades de memoria, todavía parece posible hacerlo en el lugar, pero si lo hace descuidadamente terminará sobrescribiendo elementos de otra línea o columna.

Si la memoria no es un cuello de botella recomiendo usar una matriz temporal. Es realmente más fácil y probablemente sea más rápido de todos modos.

• El mejor método no es transponer en absoluto sino simplemente establecer un indicador en algún lugar que indique si se accede a los datos fila primero o columna primero. En la mayoría de los casos, los algoritmos que necesitan transposición se pueden reescribir para acceder a una matriz no transpuesta como si fuera. Para lograr esto solo tienes que volver a escribir algunas operaciones básicas como productos de matriz para aceptar matrices con una orientación u otra.

Pero en algunos casos entiendo que esto no será posible, normalmente si los datos están siendo preparados para que algún hardware o biblioteca existente pueda acceder a ellos.

Answer 4

Wikipedia tiene entire article en la transposición de matrices in situ. Para las matrices no cuadradas, es un problema no trivial, bastante interesante (si se usa menos de O (N x M) memoria, eso es). El artículo tiene enlaces a bastantes documentos con algoritmos, así como algunos códigos fuente.

Sin embargo, como dije en un comentario a su pregunta, su demostración es no de una transposición estándar, para la que se escribirán todos los algoritmos.

(Una función de transposición norma dará este resultado para sus datos de ejemplo :)

{ 
    {1, 4}, 
    {2, 5}, 
    {3, 6} 
}; 

Si sólo está haciendo esto para mostrar una imagen en una pantalla, es posible que el mejor fuera sólo hacer la transposición mientras copia la imagen en el búfer posterior, en lugar de transponerla en el lugar y luego hacer blitting.

Answer 5

Sólo una copia simple de la temperatura y la copia posterior, la transposición de la marcha, usando puntero paso a paso para evitar la multiplicación en el cálculo de la dirección, y el bucle interior desenrollada:

char temp[W*H]; 
char* ptemp = temp; 
memcpy(temp, array, sizeof(char)*W*H); 
for (i = 0; i < H; i++){ 
    char* parray = &array[i]; 
    for (j = 0; j+8 <= W; j += 8, ptemp += 8){ 
     *parray = ptemp[0]; parray += H; 
     *parray = ptemp[1]; parray += H; 
     *parray = ptemp[2]; parray += H; 
     *parray = ptemp[3]; parray += H; 
     *parray = ptemp[4]; parray += H; 
     *parray = ptemp[5]; parray += H; 
     *parray = ptemp[6]; parray += H; 
     *parray = ptemp[7]; parray += H; 
    } 
    for (; j < W; j++, parray += H){ 
     *parray = *ptemp++; 
    } 
} 

no sé cómo evitar el problema de la ubicación del caché debido a la naturaleza del problema.

Answer 6

La solución más eficiente aquí es rotar los datos mientras se copian desde la RAM al framebuffer. Girar la fuente en la RAM y luego copiar el resultado al framebuffer será, en el mejor de los casos, la mitad de la velocidad de la versión de copiar y girar. Entonces, la pregunta es, ¿es más eficiente leer de forma secuencial y escribir aleatoriamente o leer al azar y escribir secuencialmente?En el código, esto sería la elección entre:

// read sequential 
src = { image data } 
dest = framebuffer 
for (y = 0 ; y < H ; ++y) 
{ 
    for (x = 0 ; x < W ; ++x) 
    { 
    pixel = *src++ 
    dest [y,x] = pixel 
    } 
} 

o:

// write sequential 
src = { image data } 
dest = framebuffer 
for (x = 0 ; x < W ; ++x) 
{ 
    for (y = 0 ; y < H ; ++y) 
    { 
    pixel = src [x,y] 
    *dest++ = pixel 
    } 
} 

La respuesta a esto sólo se puede determinar mediante el perfilado del código.

Ahora, puede ser que tenga una GPU, en cuyo caso podría hacer rotaciones y será mucho más eficiente dejar que la GPU haga la rotación al ajustar la imagen a la pantalla.