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

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

Некоторые подробности о транспонировании квадратов с плавающей запятой 4×4 (я расскажу о 32-битном целом позже) с аппаратным обеспечением x86. Здесь полезно начать с того, чтобы транспонировать большие квадратные матрицы, такие как 8×8 или 16×16.

_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 распаковки.

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

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

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

демо: 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] = темп. это может быть сделано за один проход, поэтому это должно занять O (n ^ 2)

мой ответ транспонирован из матрицы 3х3

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