programacion - matriz transpuesta c++ ejemplos

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

Question

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

a b c d e f
g h i j k l
m n o p q r 

Quiero que el resultado sea el siguiente:

a g m
b h n
c I o
d j p
e k q
f l r

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

Answer 1

Algunos detalles sobre la transposición de matrices flotantes de 4x4 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 8x8 o 16x16.

_MM_TRANSPOSE4_PS(r0, r1, r2, r3) se implementa de forma diferente por diferentes compiladores. 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 8x8 (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.

Answer 2

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

Answer 3

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)

Answer 4

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<N*M; n++) {
        int i = n/N;
        int j = n%N;
        dst[n] = src[M*j + i];
    }
}

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<N; i++) {
    for(int j=0; j<K; j++) {
        float tmp = 0;
        for(int l=0; l<M; l++) {
            tmp += A[M*i+l]*B[K*l+j];
        }
        C[K*i + j] = tmp;
    }
}

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<N; i++) {
    for(int j=0; j<K; j++) {
        float tmp = 0;
        for(int l=0; l<M; l++) {
            tmp += A[M*i+l]*B[K*j+l];
        }
        C[K*i + j] = tmp;
    }
}
transpose(B);

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 recopilación. No sé si eso será útil en este caso, pero podría obtener una imagen de la recopilació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<M*N; n++) {
        int k = vec_size*(n/N/vec_size);
        int i = (n/vec_size)%N;
        int j = n%vec_size;
        B[n] = A[M*i + k + j];
    }
}

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 bloqueo de bucle con block_size=16 ( Editar: Encontré una solución más rápida usando SSE y bloqueo 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<block_size; i++) {
        for(int j=0; j<block_size; j++) {
            B[j*ldb + i] = A[i*lda +j];
        }
    }
}

inline void transpose_block(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<n; i+=block_size) {
        for(int j=0; j<m; j+=block_size) {
            transpose_scalar_block(&A[i*lda +j], &B[j*ldb + i], lda, ldb, block_size);
        }
    }
}

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<n; i+=block_size) {
        for(int j=0; j<m; j+=block_size) {
            int max_i2 = i+block_size < n ? i + block_size : n;
            int max_j2 = j+block_size < m ? j + block_size : m;
            for(int i2=i; i2<max_i2; i2+=4) {
                for(int j2=j; j2<max_j2; j2+=4) {
                    transpose4x4_SSE(&A[i2*lda +j2], &B[j2*ldb + i2], lda, ldb);
                }
            }
        }
    }
}

Answer 5

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.

Answer 6

mi respuesta está transpuesta de matriz 3x3

 #include<iostream.h>

#include<math.h>


main()
{
int a[3][3];
int b[3];
cout<<"You must give us an array 3x3 and then we will give you Transposed it "<<endl;
for(int i=0;i<3;i++)
{
    for(int j=0;j<3;j++)
{
cout<<"Enter a["<<i<<"]["<<j<<"]: ";

cin>>a[i][j];

}

}
cout<<"Matrix you entered is :"<<endl;

 for (int e = 0 ; e < 3 ; e++ )

{
    for ( int f = 0 ; f < 3 ; f++ )

        cout << a[e][f] << "/t";


    cout << endl;

    }

 cout<<"/nTransposed of matrix you entered is :"<<endl;
 for (int c = 0 ; c < 3 ; c++ )
{
    for ( int d = 0 ; d < 3 ; d++ )
        cout << a[d][c] << "/t";

    cout << endl;
    }

return 0;
}

Answer 7

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.

Answer 8

template <class T>
void transpose( std::vector< std::vector<T> > a,
std::vector< std::vector<T> > 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];
        }
    }
}