Каков самый быстрый способ транспонировать матрицу в C++?

Это будет зависеть от вашего приложения, но в целом самый быстрый способ транспонировать матрицу-это инвертировать ваши координаты, когда вы смотрите вверх, тогда вам не нужно фактически перемещать какие-либо данные.

некоторые подробности о транспонировании 4x4 квадратных поплавковых (я буду обсуждать 32-разрядное целое число позже) матриц с оборудованием x86. Полезно начать здесь, чтобы транспонировать большие квадратные матрицы, такие как 8x8 или 16x16.

_MM_TRANSPOSE4_PS(r0, r1, r2, r3) реализуется по-разному в разных компиляторах. GCC и ICC (я не проверял Clang) используйте unpcklps, unpckhps, unpcklpd, unpckhpd в то время как MSVC использует только shufps. Мы можем объединить эти два подхода вместе.

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

один интересный наблюдение состоит в том, что две перетасовки могут быть преобразованы в одну перетасовку и две смеси (SSE4.1), как это.

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

это эффективно преобразуется 4 перетасовки в 2 перетасовки и 4 смеси. Это использует 2 больше инструкций, чем реализация GCC, ICC и MSVC. Преимущество заключается в том, что он снижает давление в портах, что может иметь преимущество в некоторых обстоятельствах. В настоящее время все перетасовки и распаковки могут идти только в один конкретный порт, тогда как смеси могут идти в любой из двух разных портов порты.

Я попытался использовать 8 перетасовок, таких как MSVC, и преобразовать их в 4 перетасовки + 8 смесей, но это не сработало. Я все еще должен был использовать 4 распаковывает.

я использовал эту же технику для транспонирования поплавка 8x8 (см. Ближе к концу этого ответа). https://stackoverflow.com/a/25627536/2542702. в этом ответе мне все еще пришлось использовать 8 распаковок, но я решил преобразовать 8 перетасовок в 4 перетасовки и 8 смесей.

для 32-разрядных целых чисел нет ничего как shufps (за исключением 128-битных перетасовок с AVX512), поэтому он может быть реализован только с распаковками, которые, как я думаю, не могут быть преобразованы в смеси (эффективно). С AVX512 vshufi32x4 эффективно действует как shufps за исключением 128-битных полос из 4 целых чисел вместо 32-битных поплавков, так что этот же метод может быть возможно с vshufi32x4 в некоторых случаях. С рыцарями приземления перетасовки в четыре раза медленнее (пропускная способность), чем смеси.

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

рассматривайте каждую строку как столбец, а каждый столбец как строку .. используйте j, i вместо 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;
}

транспонирование без каких-либо накладных расходов (класс не полный):

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

можно использовать так:

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

конечно, я не беспокоился об управлении памятью здесь, что является важной, но другой темой.

Я думаю, что самый быстрый способ не должен принимать выше, чем O (n^2) также таким образом вы можете использовать только O(1) пространство :
способ сделать это-поменять местами в парах , потому что когда вы транспонируете матрицу, то что вы делаете: M[i][j]=M[j][i], поэтому сохраните M[i][j] в temp, затем M[i][j]=M[j][i], и последний шаг : M[j][i]=temp. это может быть сделано за один проход, поэтому он должен занять O (n^2)

мой ответ транспонируется из Матрицы 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;
}