¿Cuál es la forma más rápida de transponer una matriz en C ++?

Tengo una matriz (relativamente grande) que necesito transponer. Por ejemplo, supongamos que mi matriz es

abcdef ghijkl mnopqr 

Quiero que el resultado sea el siguiente:

 agm bhn c I o djp ekq flr 

¿Cuál es la forma más rápida de hacer esto?

Esta es una buena pregunta. Hay muchas razones por las que desearía transponer realmente la matriz en memoria en lugar de simplemente intercambiar coordenadas, por ejemplo, en la multiplicación de matrices y en la dispersión gaussiana.

Primero permítame enumerar una de las funciones que uso para la transposición ( EDITAR: vea al final de mi respuesta donde encontré una solución mucho más rápida )

 void transpose(float *src, float *dst, const int N, const int M) { #pragma omp parallel for for(int n = 0; n 

Ahora veamos por qué la transposición es útil. Considere la multiplicación de matrices C = A * B. Podríamos hacerlo de esta manera.

 for(int i=0; i 

De esta forma, sin embargo, tendrá muchas fallas en la memoria caché. Una solución mucho más rápida es tomar la transposición de B primero

 transpose(B); for(int i=0; i 

La multiplicación de la matriz es O (n ^ 3) y la transposición es O (n 2), por lo que tomar la transposición debería tener un efecto insignificante en el tiempo de cálculo (para n grande). En el bucle de multiplicación de la matriz, el mosaico es incluso más efectivo que tomar la transposición, pero eso es mucho más complicado.

Ojalá supiera una forma más rápida de hacer la transposición ( Editar: Encontré una solución más rápida, veré el final de mi respuesta ). Cuando Haswell / AVX2 salga en unas semanas tendrá una función de recostackción. No sé si eso será útil en este caso, pero podría obtener una imagen de la recostackción de una columna y escribir una fila. Tal vez hará que la transposición sea innecesaria.

Para manchas Gaussianas, lo que haces es untar horizontalmente y luego untar verticalmente. Pero untar verticalmente tiene el problema de caché así que lo que haces es

 Smear image horizontally transpose output Smear output horizontally transpose output 

Aquí hay un documento de Intel que explica que http://software.intel.com/en-us/articles/iir-gaussian-blur-filter-implementation-using-intel-advanced-vector-extensions

Por último, lo que realmente hago en la multiplicación de matrices (y en el borrado gaussiano) no es tomar exactamente la transposición sino tomar la transposición en anchos de cierto tamaño de vector (por ejemplo, 4 u 8 para SSE / AVX). Aquí está la función que uso

 void reorder_matrix(const float* A, float* B, const int N, const int M, const int vec_size) { #pragma omp parallel for for(int n=0; n 

EDITAR:

Intenté varias funciones para encontrar la transposición más rápida para matrices grandes. Al final, el resultado más rápido es utilizar el locking de bucle con block_size=16 ( Editar: Encontré una solución más rápida usando SSE y locking de bucle - ver más abajo ). Este código funciona para cualquier matriz NxM (es decir, la matriz no tiene que ser cuadrada).

 inline void transpose_scalar_block(float *A, float *B, const int lda, const int ldb, const int block_size) { #pragma omp parallel for for(int i=0; i 

Los valores lda y ldb son el ancho de la matriz. Estos deben ser múltiplos del tamaño del bloque. Para encontrar los valores y asignar la memoria para, por ejemplo, una matriz de 3000x1001, hago algo como esto

 #define ROUND_UP(x, s) (((x)+((s)-1)) & -(s)) const int n = 3000; const int m = 1001; int lda = ROUND_UP(m, 16); int ldb = ROUND_UP(n, 16); float *A = (float*)_mm_malloc(sizeof(float)*lda*ldb, 64); float *B = (float*)_mm_malloc(sizeof(float)*lda*ldb, 64); 

Para 3000x1001, esto devuelve ldb = 3008 y lda = 1008

Editar:

Encontré una solución aún más rápida usando los intrínsecos de SSE:

 inline void transpose4x4_SSE(float *A, float *B, const int lda, const int ldb) { __m128 row1 = _mm_load_ps(&A[0*lda]); __m128 row2 = _mm_load_ps(&A[1*lda]); __m128 row3 = _mm_load_ps(&A[2*lda]); __m128 row4 = _mm_load_ps(&A[3*lda]); _MM_TRANSPOSE4_PS(row1, row2, row3, row4); _mm_store_ps(&B[0*ldb], row1); _mm_store_ps(&B[1*ldb], row2); _mm_store_ps(&B[2*ldb], row3); _mm_store_ps(&B[3*ldb], row4); } inline void transpose_block_SSE4x4(float *A, float *B, const int n, const int m, const int lda, const int ldb ,const int block_size) { #pragma omp parallel for for(int i=0; i 

Esto dependerá de su aplicación, pero en general la forma más rápida de transponer una matriz sería invertir sus coordenadas cuando realiza una búsqueda, entonces no tiene que mover realmente ningún dato.

Algunos detalles sobre la transposición de matrices flotantes de 4×4 cuadradas (voy a hablar de enteros de 32 bits más adelante) con hardware x86. Es útil comenzar aquí para transponer matrices cuadradas más grandes, como 8×8 o 16×16.

_MM_TRANSPOSE4_PS(r0, r1, r2, r3) se implementa de forma diferente por diferentes comstackdores. GCC e ICC (no he comprobado Clang) utilizan unpcklps, unpckhps, unpcklpd, unpckhpd mientras que shufps solo usa shufps . De hecho, podemos combinar estos dos enfoques juntos de esta manera.

 t0 = _mm_unpacklo_ps(r0, r1); t1 = _mm_unpackhi_ps(r0, r1); t2 = _mm_unpacklo_ps(r2, r3); t3 = _mm_unpackhi_ps(r2, r3); r0 = _mm_shuffle_ps(t0,t2, 0x44); r1 = _mm_shuffle_ps(t0,t2, 0xEE); r2 = _mm_shuffle_ps(t1,t3, 0x44); r3 = _mm_shuffle_ps(t1,t3, 0xEE); 

Una observación interesante es que dos mezclas se pueden convertir a una mezcla aleatoria y dos mezclas (SSE4.1) como esta.

 t0 = _mm_unpacklo_ps(r0, r1); t1 = _mm_unpackhi_ps(r0, r1); t2 = _mm_unpacklo_ps(r2, r3); t3 = _mm_unpackhi_ps(r2, r3); v = _mm_shuffle_ps(t0,t2, 0x4E); r0 = _mm_blend_ps(t0,v, 0xC); r1 = _mm_blend_ps(t2,v, 0x3); v = _mm_shuffle_ps(t1,t3, 0x4E); r2 = _mm_blend_ps(t1,v, 0xC); r3 = _mm_blend_ps(t3,v, 0x3); 

Esto efectivamente convirtió 4 barajaduras en 2 barajaduras y 4 mezclas. Esto usa 2 instrucciones más que la implementación de GCC, ICC y MSVC. La ventaja es que reduce la presión del puerto que puede tener un beneficio en algunas circunstancias. Actualmente, todas las mezclas y desempaquetados pueden ir solo a un puerto en particular, mientras que las mezclas pueden ir a cualquiera de los dos puertos diferentes.

Traté de usar 8 mezclas como MSVC y convertir eso en 4 mezclas + 8 mezclas, pero no funcionó. Todavía tuve que usar 4 desempaquetados.

Usé esta misma técnica para una transposición de flotación de 8×8 (mira hacia el final de esa respuesta). https://stackoverflow.com/a/25627536/2542702 . En esa respuesta, todavía tenía que usar 8 desempaquetados, pero logré convertir 8 barajaduras en 4 combinaciones y 8 combinaciones.

Para enteros de 32 bits no hay nada como shufps (excepto para shufps de 128 bits con AVX512) por lo que solo se puede implementar con desempaquetados que no creo que se puedan convertir en mezclas (de manera eficiente). Con AVX512 vshufi32x4 actúa de forma efectiva como shufps excepto por los carriles de 128 bits de 4 enteros en lugar de los flotadores de 32 bits, por lo que esta misma técnica podría ser posible con vshufi32x4 en algunos casos. Con Knights Landing, las mezclas son cuatro veces más lentas (rendimiento) que las mezclas.

 template  void transpose( std::vector< std::vector > a, std::vector< std::vector > b, int width, int height) { for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { b[j][i] = a[i][j]; } } } 

Considere cada fila como una columna, y cada columna como una fila … use j, i en lugar de i, j

demo: http://ideone.com/lvsxKZ

 #include  using namespace std; int main () { char A [3][3] = { { 'a', 'b', 'c' }, { 'd', 'e', 'f' }, { 'g', 'h', 'i' } }; cout << "A = " << endl << endl; // print matrix A for (int i=0; i<3; i++) { for (int j=0; j<3; j++) cout << A[i][j]; cout << endl; } cout << endl << "A transpose = " << endl << endl; // print A transpose for (int i=0; i<3; i++) { for (int j=0; j<3; j++) cout << A[j][i]; cout << endl; } return 0; } 

transposición sin ningún tipo de sobrecarga (clase no completa):

 class Matrix{ double *data; //suppose this will point to data double _get1(int i, int j){return data[i*M+j];} //used to access normally double _get2(int i, int j){return data[j*N+i];} //used when transposed public: int M, N; //dimensions double (*get_p)(int, int); //functor to access elements Matrix(int _M,int _N):M(_M), N(_N){ //allocate data get_p=&Matrix::_get1; // initialised with normal access } double get(int i, int j){ //there should be a way to directly use get_p to call. but i think even this //doesnt incur overhead because it is inline and the compiler should be intelligent //enough to remove the extra call return (this->*get_p)(i,j); } void transpose(){ //twice transpose gives the original if(get_p==&Matrix::get1) get_p=&Matrix::_get2; else get_p==&Matrix::_get1; swap(M,N); } } 

se puede usar así:

 Matrix M(100,200); double x=M.get(17,45); M.transpose(); x=M.get(17,45); // = original M(45,17) 

por supuesto, no me molesté con la administración de memoria aquí, que es un tema crucial pero diferente.

Creo que la manera más rápida no debería tomar más que O (n ^ 2) también de esta manera puedes usar solo O (1) espacio:
la forma de hacerlo es intercambiar en pares porque cuando transpone una matriz, entonces lo que hace es: M [i] [j] = M [j] [i], así que almacene M [i] [j] en temperatura, luego M [i] [j] = M [j] [i], y el último paso: M [j] [i] = temp. esto podría hacerse por un pase, por lo que debería tomar O (n ^ 2)

mi respuesta está transpuesta de matriz 3×3

  #include #include main() { int a[3][3]; int b[3]; cout<<"You must give us an array 3x3 and then we will give you Transposed it "<>a[i][j]; } } cout<<"Matrix you entered is :"<